# Find $n\geq1$ such that 7 divides $n^n-3$

Find $n\geq1$ such that 7 divides $n^n-3$.

Here is what I found:

$n\equiv 0 \mod7, n^n\equiv 0 \mod7,n^n-3\equiv -3 \mod7$ no solution.

$n\equiv 1 \mod7, n^n\equiv 1 \mod7,n^n-3\equiv -2 \mod7$ no solution.

$n\equiv 2 \mod7, n^n\equiv 2^n \mod7, n^n-3\equiv 2^n-3 \mod7$. Is $2^n\equiv 3 \mod7$ possible?

$n=7k+2,..., 2^{7k+2}\equiv 2^{k+2} \mod7$. Is $2^{k+2}\equiv 3 \mod7$ possible?

Studying $k$ modulo 6: $2^{6q+2}\equiv 4 \mod7, 2^{6q+3}\equiv 1 \mod7, 2^{6q+4}\equiv 2 \mod7, 2^{6q+5}\equiv 4 \mod7, 2^{6q+6}\equiv 1 \mod7, 2^{6q+7}\equiv 2 \mod7$

The congruence is never 3 so there is no solution for $n\equiv 2 \mod7$.

$n\equiv -2 \mod7,..., n=42q+5$

$n\equiv-1 \mod7, n^n-3\equiv (-1)^n-3 \mod7$: no solution.

$n\equiv 3 \mod7, n^n-3 \equiv 3^n-3 \mod7$. Is $3^n\equiv 3 \mod 7$ possible?

$n=7k+3,..., 3^{7k+3}\equiv -3^k \mod7$. Is $3^k \equiv 4 \mod 7$ possible?

Studying $k$ modulo 6:

$3^{6q} \equiv 1 \mod7, 3^{6q+1} \equiv 3 \mod7, 3^{6q+2} \equiv 2 \mod7, 3^{6q+3} \equiv -1 \mod7, 3^{6q+4} \equiv 4 \mod7 , 3^{6q+5} \equiv -2 \mod7$ So $n=7k+3=7(6q+4)+3=42q+31$ is a solution.

$n\equiv -3 \mod7$,..., there is no solution.

$42q+31 \equiv 3 \mod 7, (42q+31)^{42q+31} \equiv 3^{42q+31} \mod 7 \equiv 3 \mod7$ OK

$42q+5 \equiv 4 \mod7, (42q+5)^{42q+5} \equiv 5^{42q+5} \mod 7 \equiv 3 \mod7$ OK

So 7 divides $n^n-3$ if and only if $n\equiv 31 \mod 42$ or $n\equiv 5 \mod 42$

-
$n \equiv 5 \mod 42$ gives another family of solutions, so your final sentence is not correct. – Mikko Korhonen Dec 21 '11 at 10:58

$n^n - 3$ is divisible by $7$ if and only if $n \equiv 5\mod 42$ or $n \equiv 31 \mod 42$.

If $n \equiv 5 \mod 42$, then $n \equiv 5 \mod 7$. Thus $n^n \equiv 5^n \equiv 5^{n-5} \cdot 5^5 \equiv 5^5 \equiv 3 \mod 7$, because $n-5$ is divisible by $6$.

If $n \equiv 31 \mod 42$, then $n \equiv 31 \equiv 3 \mod 7$. As before, $n^n \equiv 3^n \equiv 3^{n-31} \cdot 3^{31} \equiv 3^{31} \equiv 3 \mod 7$.

For the converse, suppose that $n^n \equiv 3 \mod 7$. It is clear that $n \not\equiv 0 \mod 7$ and $n \not\equiv 1 \mod 7$. Possible powers of $2$ and $4$ modulo $7$ are $1$, $2$ and $4$, so $n \not\equiv 2 \mod 7$ and $n \not\equiv 4 \mod 7$. Similarly the possible powers of $6$ modulo $7$ are $1$ and $6$, so $n \not\equiv 6 \mod 7$.

Thus there are two possibilities: $n \equiv 3 \mod 7$ or $n \equiv 5 \mod 7$.

If $n \equiv 3 \mod 7$, then $n^n \equiv 3^n \mod 7$ and $3^n \equiv 3 \mod 7$. Thus $3^{n-1} \equiv 1 \mod 7$, and so $6$ divides $n-1$. Thus $n \equiv 1 \mod 6$. Then $7n \equiv 7 \mod 42$ and $6n \equiv 18 \mod 42$, and so $n \equiv 31 \mod 42$.

If $n \equiv 5 \mod 7$, then $n^n \equiv 5^n \mod 7$ and $5^n \equiv 3 \equiv 5^5 \mod 7$. Thus $5^{n-5} \equiv 1 \mod 7$, and $6$ divides $n-5$. With the same argument as before, $n \equiv 5 \mod 42$.

-

$$5^5-3=2\cdot 7\cdot 233$$ Other solutions are $$n=31, 47, 73, 89, 115, 131, 157, 173, 199, 215, 241, 257, 283, 299, 325$$ All of them are odd and congruent to $3$ or $5$ modulo $7$.

-

Since the question only asks (at least the way I read it) to find some $n\geq 1$ such that $n^n-3\equiv 0 \bmod 7$, you can exploit the fact that a power $a^b \bmod 7$ only depends on the class of $a\bmod 7$ and the class of $b\bmod 6$.

Thus, if you pick $n\equiv 3 \bmod 7$ such that $n\equiv 1 \bmod 6$, then: $$n^n\equiv 3^n \equiv 3^{1+6k} \equiv 3\cdot (3^6)^k \equiv 3 \bmod 7,$$ as desired. Hence, by the Chinese remainder theorem, any $n\equiv 31 \bmod 42$ will work.

For instance, $$3^{31}-3 = 617673396283944=2^3\cdot 3\cdot 7\cdot 11^2\cdot 13\cdot 31\cdot 61 \cdot 271\cdot 4561.$$

-