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 [tex]e[/tex] be the lowest number (natural) such that [tex] a^e \equiv 1 (\bmod \ p) [/tex] for [tex] p [/tex] prime such that [tex] p [/tex] does not divide [tex] a [/tex]. Prove that [tex] p-1 [/tex] is a multiple of [tex] e [/tex].

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

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

The book I am reading from (What is mathemathics? by Richard Courant and Herbert Robbins) suggests that I use the fact that [tex] a^{p-1} \equiv a^e \equiv 1 (\bmod \ p) [/tex] and that I divide [tex] p-1 [/tex] by [tex] e [/tex] to get [tex] p-1 = ke + r [/tex]
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
[tex]a^{p-1} = a^{ke+r} \equiv a^e \equiv 1 \pmod p[/tex]
you are to prove that r=0. Consider that
[tex]a^{ke+r} = a^{ke} a^r = (a^{e})^k a^r[/tex]
(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
[tex] a^{p-1} = a^{ke+r} = (a^e)^k a^r \equiv a^e \equiv 1 (\bmod \ p) [/tex]
We also know that
[tex] a^e \equiv 1 (\bmod \ p) [/tex],
we can infer from this that [tex]
(a^e)^n \equiv 1(\bmod p) [/tex] for any integer n, thus the only way for
[tex] (a^e)^k a^r \equiv a^e \equiv 1 (\bmod \ p) [/tex]
to be true is to have
[tex] a^r \equiv 1 (\bmod \ p) [/tex]
which can only happen if [tex] r=0 [/tex] since we were supposing [tex] e [/tex] was the lowest power of [tex] a [/tex] that was congruent to 1 modulo [tex] p [/tex].
So we conclude that
[tex] p-1 = ke + r = ke + 0 = ke [/tex] and thus e must be a factor of [tex] p-1 [/tex].

Tell me if I screwed up somewhere along the way.

dodo

Looks accurate and well presented to me.