6
$\begingroup$

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$

  • 1
    $n \equiv 5 \mod 42$ gives another family of solutions, so your final sentence is not correct.2011-12-21

3 Answers 3

9

$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$.

3

$ 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$.

2

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.$