Find all $n\in \mathbb{Z}^+ : 7|5^{6n}+5^n+2$

Question

Question: We want to find all $n\in \mathbb{Z}^+$ such that $7|5^{6n}+5^n+2$.

Answer: We have that $7|5^{6n}+5^n+2 \iff 5^{6n}+5^n+2 \equiv 0 \bmod 7$.

But $\phi(7)=6\wedge\text{gcd}(5,7)=1$ and we can apply Fermat's theorem, so $5^6 \equiv1 \bmod 7\implies 5^{6n}\equiv1 \bmod 7 $. So, we have to find all positive integers $n$ such that $$5^n+3\equiv0 \bmod 7 \iff 5^n \equiv 4 \bmod 7 \iff 2\cdot 5^n\equiv1 \bmod 7$$

I stuck in this point. Any help please?

Thank you in advance.

Answer 1

As you've noticed $\phi(7) = 6$, so you need to plug $1,2,3,4,5,6$ in place of $n$, as afterwards the value modulo $7$ will start repeating modulo $\phi(7)=6$. Checking all cases will give you whether there is a solution or not for the equation.

Eventually you should be able to find that $n$ is of the form $6k+2$

Answer 2

By Fermat's Little Theorem, $5^6\equiv1\pmod7$. Therefore, $$ 5^{6n}+5^n+2\equiv5^n+3\pmod7 $$ So the question is asking for which $n$ is $5^n\equiv4\pmod7$. Checking $n=0,1,2,\dots,6$, we get that only $n=2$ works. Thus, by Fermat's Little Theorem, $$ n\equiv2\pmod6 $$

Answer 3

From $5^n \equiv 4 (\bmod{7})$ write $(-2)^n \equiv 4 (\bmod{7})$ so that $(-2)^{n-2} \equiv 1 (\bmod{7}).$ The order of $-2 (\bmod{7})$ is $6$, so $6\mid n-2$. Therefore $n =6k+2$ for any integer $k$.