I am going through number theory from the following book :
On page 96, the proof is given that every prime number $p$ has a primitive root modulo $p$.
The proof proceeds with establishing the equality of two summatory functions: in particular the sum of number of elements of order $m$ where $m$ is a number which divides $p – 1 $ for some prime number $p$ and the sum of the number of elements coprime to $m$ where $m|(p-1)$.
On page 93 (theorem 58), the proof that "if a prime, $p$, is known to have a primitive root(s), then it will have $ \phi (p – 1) $ " is given .
However, for the proof for existence of primitive roots for prime numbers, I am unable to understand the strategy behind the proof. How does equating these two summatory functions lead to existence of a primitive root ?
I went through the following question centered around the same point but it is focusing on a different part of the proof.
Proof that every prime has a primitive root. .
The proof, as in the book, is as follows :
Proof: Let $p$ be a prime and let $m$ be a positive integer such that:
$p−1=mk$ for some integer k. Let $F(m)$ be the number of positive integers of order $m$ modulo $p$ that are less than $p$. The order modulo $p$ of an integer not divisible by $p$ divides $p − 1$, it follows that:
$$p-1=\sum_{m|p-1}F(m)
$$
By theorem 42 we know that:
$$p-1=\sum_{m|p-1}\phi(m)
$$
By Lemma 11, $F(m)\leq \phi(m)$ when $m\mid(p−1)$. Together with:
$$\sum_{m|p-1}F(m)=\sum_{m|p-1}\phi(m)
$$
we see that $F(m)=\phi(m)$ for each positive divisor $m$ of $p−1$. Thus we conclude that $F(m)=\phi(m)$. As a result, we see that there are $p−1$ incongruent integers of order $p−1$ modulo $p$. Thus $p$ has $\phi(p−1)$ primitive roots.
Are $ 1 $ and $ p -1 $ also being considered in the list of $m $ ? How is this idea in the proof working ?
Best Answer
While I'm still not quite sure what you're asking, I shall go through each section of the proof in a lot of detail with the hope that this will help. Again, I'm sorry if I go over a lot of things you already know but I just don't know quite what part you're having difficulty with.
The order of an element $a$ modulo our prime $p$, as a reminder, is the smallest positive exponent $i$ s.t. $a^i=1$ modulo $p$. General proof strategy, then, is as follows:
We define a function $F(m)$ as the number of elements of order $m$ modulo $p$. So as an example, if we look modulo $5$, we see that $4^2=1$ (so 4 is an element of order 2) and every other element is either 1 (so has order 1) or has order greater than 2 (as $2^2=3^2=4\neq 1$). So, modulo 5, $F(2)=1$.
We then remember that the order of an element must divide the number of non-zero elements modulo $p$.
Why is this? (feel free to skip this if you know it already) Firstly, we know by Fermat's Little Theorem that $a^{p-1}=1$ modulo $p$ for every non-zero element $a$ modulo $p$. Then, if the order of an element $a$ is $e$, we can long divide $p-1$ by $e$ so that $$p-1=e\times n+b, 0\leq b<e$$ Then we get that, modulo $p$, $$1=a^{p-1}=a^{e\times n+b}=a^{e\times n}a^b=(a^{e})^na^b=(1)^na^b=a^b$$ so $a^b=1$ but we know that $b<e$ and $e$ is the smallest positive exponent for which $a^e=1$ so $b$ cannot be positive! But we also know that $0\leq b$ so $b=0$ and so $p-1=e\times n$ so $e|p-1$.
So the order of an element must divide $p-1$. But, obviously, every element has some order (given that orders are bounded above by $p-1$, i.e. we already know that $a^{p-1}=1$ modulo $p$ for every nonzero element $a$). So thus $$\sum_{k|(p-1)}F(k)=(p-1)$$This sum really doesn't say much - the number of elements that have some order is the number of nonzero elements.
Next, the proof whips out a famous identity which it says you've already seen the proof of. There are a number of other proofs online (some completely elementarily, some using the FTA, some using the multiplicative nature of the sum) but I won't give one here - you apparently have one in your textbook. The identity is the following:
$$n = \sum_{k|n}\phi(k)$$
for a natural number $n$ and we particularly care about this result when $n=(p-1)$. Now the proof says that you already know, from some previous section, that $F(k) \leq \phi(k)$ and since $$\sum_{k|n}\phi(k)=\sum_{k|(p-1)}F(k)$$ we deduce that $F(k)=\phi(k)$ for each divisor $k$. Why is this?
Suppose that any of these inequalities is strict, i.e. $F(k)<\phi(k)$ for some $k$ in the sum. Then, even if $F(n)=\phi(n)$ for every other divisor of $(p-1)$, we would have that $$\sum_{k|n}\phi(k)<\sum_{k|(p-1)}F(k)$$ which is a contradiction.
Then if $F(k)=\phi(k)$ for each divisor $k$ of $(p-1)$ and $\phi(k)\geq 1$ for each $k$, we know that $F(p-1)=\phi(p-1) \geq 1$, i.e. there is at least one element of order $(p-1)$ (a primitive root!) and we're done!
ADDENDUM:
Just because I'm not personally such a fan of using $F(m)\leq \phi(m)$ without explaining it (given that it's arguably the most important part of the proof) and that I can't find anybody else on this forum explaining this fact, I'm going to give my own explanation here. You don't have to read this but I strongly suggest it, as I think this is very nice:
Consider the polynomial $x^d-1$ for a divisor $d$ of $(p-1)$ and suppose, hypothetically, it had some root $u$ modulo $p$. Then we can notice that $u,u^2,u^3,...,u^d$ are all roots also.
Why? $(u^k)^d-1=(u^d)^k-1=1^k-1=0$.
But notice that $x^d-1$ is a polynomial of degree $d$ and so, by Lagrange's Theorem, can have at most $d$ roots (the proof of L's theorem literally replicates polynomial division in modular arithmetic so we don't worry about it here - you may already know a proof!). But if it can have at most $d$ roots and $u,...,u^d$ are all roots, then $u,...,u^d$ are the only roots of this equation!
But every element of order $d$ must be a root of $x^d-1$ by definition so every element of order $d$ is a power of $u$. (NOTE: not every root of $x^d-1$ is an element of order $d$ - if $u^k$ had order $d/2$, it would still be a root of the equation)
But which powers of $u$ have order $d$ given that $u^d-1=0$? Well, all the powers of $u$ whose order is $coprime$ with $d$ (for the same EXACT reason as used in the proof that if there is 1 primitive root modulo $p$ then there are $\phi(p-1)$ many, a theorem whose proof you say you understand).
So if every element of order $d$ is a power of $u$ and there are exactly $\phi(d)$ many powers of $u$ of order $d$, then there are $\phi(d)$ many elements of order $d$.
So, if we call the number of elements of order $d$ "$N_d$", then we have just shown that $N_d=0$ OR $N_d=\phi(d)$, i.e. $N_d \leq \phi(d)$ as required.
===========================================================================
Phew! That took a long time to write, so I hope it's helpful. Don't be scared to ask for further clarification if necessary!