Lifting the exponent is a popular result in elementary number theory. It basically says that if and , then for an odd prime coprime to and for ,
Theorem 1. (Lifting the exponent) .
Here, as usual, means that but .
Theorem 2. .
Proof. We proceed by induction on . The base case is clear. Suppose that the assertion holds for . We want to show that , that is,
By hypothesis, . So we need to show that .
Let . We want to show that .
Since , we have . Hence , i.e. . Hence . Let for some . Then
If this is , then , which is impossible by unique factorisation as and are coprime.
Corollary. Let be the Fibonacci sequence. Then
(Refer to this post for notation.)
Proof. Take (with and ) and let . We proceed by induction on . Suppose for some . By hypothesis, so . Then , so , i.e. . Hence which implies , a contradiction.