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?



marked as duplicate by Stefan4024, Adam Hughes, Alex Mathers, Shailesh, Joey Zou Sep 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.

  • $\begingroup$ On the other side the generalization follows immediately from the Fermat's Little Theorem. $\endgroup$ – Stefan4024 Sep 20 '16 at 19:10
  • $\begingroup$ I didn't see there a proof of this general theorem. $\endgroup$ – 76david76 Sep 20 '16 at 19:11
  • $\begingroup$ How is that immediately? $\endgroup$ – 76david76 Sep 20 '16 at 19:12
  • 1
    $\begingroup$ $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$ $\endgroup$ – Stefan4024 Sep 20 '16 at 19:12
  • $\begingroup$ So it's like multiplying by $1^k$, right. $\endgroup$ – 76david76 Sep 20 '16 at 19:14

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


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