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

Question

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?

Answer 1

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.

hope its what you are looking for.