## Help with proof of theorem related to Fermat's.

Hello everyone, I have been trying to teach myself number theory and I am stuck trying to prove a (I am sure) very easy to prove theorem related to that of Fermat's.

The theorem I am to prove states:

Let $$e$$ be the lowest number (natural) such that $$a^e \equiv 1 (\bmod \ p)$$ for $$p$$ prime such that $$p$$ does not divide $$a$$. Prove that $$p-1$$ is a multiple of $$e$$.

This theorem came after the proof of Fermat's Theorem, which I will also write for the sake of completeness.

Let $$p$$ be a prime and let $$a$$ be an integer such that $$p$$ does not divide $$a$$ it follows that:
$$a^{p-1} \equiv 1 (\bmod \ p)$$

The book I am reading from (What is mathemathics? by Richard Courant and Herbert Robbins) suggests that I use the fact that $$a^{p-1} \equiv a^e \equiv 1 (\bmod \ p)$$ and that I divide $$p-1$$ by $$e$$ to get $$p-1 = ke + r$$
where r is the residue.

I've given it some thought but I kinda blow at math and I've done no useful advances, I was wondering if anyone could provide some more more insight.
 PhysOrg.com science news on PhysOrg.com >> New language discovery reveals linguistic insights>> US official: Solar plane to help ground energy use (Update)>> Four microphones, computer algorithm enough to produce 3-D model of simple, convex room
 Given that $$a^{p-1} = a^{ke+r} \equiv a^e \equiv 1 \pmod p$$ you are to prove that r=0. Consider that $$a^{ke+r} = a^{ke} a^r = (a^{e})^k a^r$$ (now, doing some more work, where can you get at?) and remember that r
 Okay, here's what I've thought: We know that $$a^{p-1} = a^{ke+r} = (a^e)^k a^r \equiv a^e \equiv 1 (\bmod \ p)$$ We also know that $$a^e \equiv 1 (\bmod \ p)$$, we can infer from this that $$(a^e)^n \equiv 1(\bmod p)$$ for any integer n, thus the only way for $$(a^e)^k a^r \equiv a^e \equiv 1 (\bmod \ p)$$ to be true is to have $$a^r \equiv 1 (\bmod \ p)$$ which can only happen if $$r=0$$ since we were supposing $$e$$ was the lowest power of $$a$$ that was congruent to 1 modulo $$p$$. So we conclude that $$p-1 = ke + r = ke + 0 = ke$$ and thus e must be a factor of $$p-1$$. Tell me if I screwed up somewhere along the way.

## Help with proof of theorem related to Fermat's.

Looks accurate and well presented to me.

 Tags fermat, help needed, proof, theorem

 Similar discussions for: Help with proof of theorem related to Fermat's. Thread Forum Replies Linear & Abstract Algebra 20 Linear & Abstract Algebra 7 General Math 14 Linear & Abstract Algebra 5 General Math 65