When does one Fibonacci number divide another? Let $F_0 = 0$, $F_1 = 1$, and for $n\\geq 2$, $F_n = F_{n-1} + F_{n-2}$. It is well known that for $F_m > 1$ This last result was used in Yuri Matijasevi\\u{c}\'s solution of Hilbert\'s 10th problem. Using simple combinatorial arguments, we derive previuosly unknown necessary and sufficient conditions for the following question: For any $L \\geq 1$ When does $F_m^L$ divide $F_n$? Our method allows us to answer this same question for any Lucas sequence of the first kind, defined by $U_0 = 0$, $U_1 = 1$, and for $n\\geq 2$, $U_n = aU_{n-1} + bU_{n-2}$. This talk is based on joint work with Harvey Mudd College undergraduate Jeremy Rouse, while attending the 10th International Conference on Applications of Fibonacci Numbers.