Help with proof of theorem related to Fermat's.

[SrEstroncio]

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.

 

[dodo]

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

 

[SrEstroncio]

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 <br /> (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.

 

[dodo]

Looks accurate and well presented to me.