Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
1  
$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

3 Answers 3

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

share|improve this answer

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.