# Solve the congruence $10^{n+1} - 9n - 10 \equiv 0$ (mod 7)

Can anyone give a method for solving the congruence: $10^{n+1} - 9n - 10 \equiv 0$ (mod 7), where $n$ is a natural number? I am told that you have to perform the Euclidean algorithm twice on $n$ before attempting to use Fermat's Little Theorem, but why is this necessary? Why not just one application of the algorithm?

well, because you have $n$ the unknown in the base and in power. lets start solving it first $\phi(7)=6$ where $\phi(n)$ is the Euler phi function, and because $n$ is in the power and in the base we will have a $7*6=42$ cycle or period over $n$ since its $6$ cycle for the $n$ in the power and $7$ in the base,by brute force we get that the values for $n = \{0,22,26,31,39,41\}$ will work and so for the general solution to $n$ is :
$$n = 42 k +\{0,22,26,31,39,41\}$$ where $k$ is a non negative integer.
• @Will why six ? because of Fermat's little theorem which says that $a^{\phi(n)} = 1 \mod n$ which means that every $\phi(n)$(sometimes its one of $\phi(n)$ divisors) which means at most after $\phi(n)$ for any $n$ we cycle again (return the same sequence as before ) for example : {1,2,4,1,2,4,1,2,4,..} is a 3-cycle sequence and because $\phi(7)=6$ we will need 6-cycle to return to the same sequence mod 7 – Ahmad Mar 15 '17 at 10:56