So I encountered this proof on a Number Theory book, I will link the pdf at the end of the post (proof at page 96), it says: "Every prime has a primitive root,
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)≤φ(m) when m|(p−1). Together with:
$$\sum_{m|p-1}F(m)=\sum_{m|p-1}\phi(m)
$$
we see that F(m)=φ(m) for each positive divisor m of p−1. Thus we conclude that F(m)=φ(m). As a result, we see that there are p−1 incongruent integers of order p−1 modulo p. Thus p has φ(p−1) primitive roots.
The part that i don't understand is near the beginning, when he says "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)
$$" How does he conclude that? I understand that the order of the integer must divide p-1 but how does that imply that the summation actually evaluates at p-1?…
Link of the book's pdf: https://www.saylor.org/site/wp-content/uploads/2013/05/An-Introductory-in-Elementary-Number-Theory.pdf
Best Answer
There are $p-1$ positive integers less than $p$, namely $1, 2, ..., p-1$.
Each of these will have some multiplicative order modulo $p$. So if we count all those of order $1$, all those of order $2$, all those of order $3$, etc then the total count is $p-1$. There are $F(1)$ of order $1$, $F(2)$ of order $2$, etc, so:
$$p-1=\sum_{m=1}^{\infty}F(m)$$
However, we know their orders will divide $p-1$, so almost all the terms in this sum will be zero. Only those with $m|(p-1)$ will contribute to the sum. We therefore have:
$$p-1=\sum_{m|p-1}F(m)$$