0
$\begingroup$

Assuming $p$ is prime, how do I show that $a^p \equiv a \pmod p$ for all $a$ (where $a$, $p$ $\in \mathbb Z$)?

I think I can handle the case where $p$ doesn't divide $a$, because then I can use Fermat's theorem, so I'd say that $a^{p - 1} \equiv 1 \pmod p$ then multiply by $a$ on both sides. But Fermat's theorem does not apply in the case that $p$ divides $a$, as $\gcd(a, p) \neq 1$.

I'm thinking maybe that since $a = kp$ for some $k$, $a^p \equiv (kp)^p \pmod p$, but I'm not sure how to show that this is congruent to $kp \pmod p$.

$\endgroup$
2
$\begingroup$

If $p$ divides $a$, both sides are congruent to $0$ modulo $p$.

$\endgroup$
  • $\begingroup$ Whelp, that was pretty stupid of me. Thanks! $\endgroup$ – Trent Bing Mar 12 '14 at 6:18
  • 1
    $\begingroup$ haha sure. overthinking happens to me too. :p $\endgroup$ – Guy Mar 12 '14 at 6:20
  • 1
    $\begingroup$ It doesn't help that I'm trying to math at 2 in the morning... $\endgroup$ – Trent Bing Mar 12 '14 at 6:21
  • 1
    $\begingroup$ Go to sleep if you don't have a test. If you have a test, then GO TO SLEEP. Sleep is important for cognitive brain functioning. $\endgroup$ – Guy Mar 12 '14 at 6:25
  • $\begingroup$ But I've got only one problem left! $\endgroup$ – Trent Bing Mar 12 '14 at 6:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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