0
$\begingroup$

The proof was given as:

  1. Let $p\in\mathbb{N}^{+}$
  2. Let $a\in\mathbb{N}$
  3. Let $p$ be prime
  4. We know that $p\,\vert\,a^p-a$ by proposition of Chapter 1
  5. Therefore $a^p-a\equiv 0\pmod p$ by Definition 8.4.1
  6. Therefore $a^p\equiv a\pmod p$ by Proposition 8.4.7

Q.E.D.

But how do I get from 4 to 5 and 5 to 6?

Is 4 to 5 trying to say, since $p$ divides $(a^p - a)$ then the remainder is always 0? Then 5 - 6, how do I just move the $a$ over?

1 (original question)

  • 0
    Step 4. is critical. If you understand that, you know the essence. Step 5. and 6. are trivial by definition of $\equiv$, and goes exactly as you wrote at the end.2012-11-30

1 Answers 1

6

The step from 4 to 5 is just the definition of congruence. By definition $a\equiv b\pmod m$ means that $m\mid a-b$, so if you know from step 4 that $p\mid a^p-a$, then you know that $p\mid(a^p-a)-0$ and hence by definition that $a^p-a\equiv 0\pmod p$. In fact step 5 is unnecessary, since you can go directly from 4 to 6: if you know that $p\mid a^p-a$, then you know that $a^p\equiv a\pmod p$ by the definition of congruence.

However, you getting from 5 to 6 is also completely straightforward. More generally,

$a\equiv b\pmod m\quad\text{iff}\quad a-b\equiv 0\pmod m\;.$

By definition $a\equiv b\pmod m$ means that $m\mid a-b$, but that’s certainly true if and only if $m\mid(a-b)-0$, which means exactly that $a-b\equiv 0\pmod m$.