2
$\begingroup$

I am going through number theory from the following book :

https://www.saylor.org/site/wp-content/uploads/2013/05/An-Introductory-in-Elementary-Number-Theory.pdf

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 ?

$\endgroup$
6
  • $\begingroup$ Welcome to MSE. I suggest that you add proof-explanation to the tags of your question. $\endgroup$ Sep 28, 2019 at 9:38
  • $\begingroup$ @JoséCarlosSantos : Thanks a lot , Done $\endgroup$ Sep 28, 2019 at 10:31
  • $\begingroup$ I'm quite ready to answer this question, as I'm familiar with this proof, but what exactly is your question? You ask if 1 and (p-1) are "in the list of $m$"? The answer is yes - do you know what "a|b" means? 1|(p-1) and (p-1)|(p-1) so they appear in the sum. $\endgroup$ Sep 29, 2019 at 20:44
  • $\begingroup$ Is that your only question? $\endgroup$ Sep 29, 2019 at 20:44
  • $\begingroup$ The main point to show $\Bbb{F}_p^\times$ is cyclic is to say that all its elements are roots of $x^{p-1}-1$ but since $x^d-1$ has at most $d$ roots they are not all roots of $x^d-1$ for any $d< p-1$, thus there is some $a$ which is a root of $x^{p-1}-1$ but not of any $x^d-1,d < p-1$ and $a$ is a primitive root. $\endgroup$
    – reuns
    Sep 29, 2019 at 22:05

1 Answer 1

8
$\begingroup$

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$, i.e. we already know that $a^p=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!

$\endgroup$
3
  • $\begingroup$ Take a bow. I will never forget this generosity of yours . Thanks a ton $\endgroup$ Oct 9, 2019 at 19:23
  • $\begingroup$ Sorry about this, but if the answer is to your satisfaction could you accept my answer? Many apologies. $\endgroup$ Oct 9, 2019 at 20:26
  • $\begingroup$ Done, Sir. Sorry for delay in replying $\endgroup$ Oct 12, 2019 at 7:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .