# prove that $n^{13}-n\equiv 0\mod(2730)$ by generalizing Fermat's little theorem. [duplicate]

This question already has an answer here:

When I saw this problem, it came to me that Fermat's little theorem that says:$$a^p\equiv a\mod(p)$$can also been said in general: $$a^{1+(p-1)k}\equiv a\mod(p)$$ Ad since $13$ can be written as:$$1+(2-1)12=13\\1+(3-1)6=13\\1+(5-1)3=13\\1+(7-1)2=13\\1+(13-1)1=13$$Therefor $$n^{13}\equiv n\mod(2\cdot3\cdot5\cdot7\cdot13=2730)$$ But I didn't find a way to prove this generalization $a^{1+(p-1)k}\equiv a\mod(p)$. Maybe someone can help me prove it?

Thanks.

## marked as duplicate by Stefan4024, Adam Hughes, Alex Mathers, Shailesh, Joey ZouSep 21 '16 at 1:32

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• On the other side the generalization follows immediately from the Fermat's Little Theorem. – Stefan4024 Sep 20 '16 at 19:10
• I didn't see there a proof of this general theorem. – 76david76 Sep 20 '16 at 19:11
• How is that immediately? – 76david76 Sep 20 '16 at 19:12
• $a^{p-1} \equiv 1 \pmod p$ by Fermat's Little Theorem. This means that: $a^{1 + (p-1)k} \equiv a \cdot (a^{p-1})^k \equiv a \cdot 1^k \equiv a \pmod p$ – Stefan4024 Sep 20 '16 at 19:12
• So it's like multiplying by $1^k$, right. – 76david76 Sep 20 '16 at 19:14

## 1 Answer

If $a \equiv 0\mod p$: Done.

If $a$ is not divisible by $p$, Fermat's Little Theorem can be written as: $a^{p-1} \equiv 1 \mod p$. And so:

$$a^{1+(p-1)k} = a.(a^{p-1})^k \equiv a(1)^k \equiv a\mod p.$$