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.

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)

share|improve this question
    
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. –  Berci Nov 30 '12 at 10:31

1 Answer 1

up vote 5 down vote accepted

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

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.