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