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$
  • $\begingroup$ Welcome to MSE. I suggest that you add proof-explanation to the tags of your question. $\endgroup$ – José Carlos Santos Sep 28 at 9:38
  • $\begingroup$ @JoséCarlosSantos : Thanks a lot , Done $\endgroup$ – beerzil charlemagne Sep 28 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$ – Isky Mathews Sep 29 at 20:44
  • $\begingroup$ Is that your only question? $\endgroup$ – Isky Mathews Sep 29 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 at 22:05
3
$\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$
  • $\begingroup$ Take a bow. I will never forget this generosity of yours . Thanks a ton $\endgroup$ – beerzil charlemagne Oct 9 at 19:23
  • $\begingroup$ Sorry about this, but if the answer is to your satisfaction could you accept my answer? Many apologies. $\endgroup$ – Isky Mathews Oct 9 at 20:26
  • $\begingroup$ Done, Sir. Sorry for delay in replying $\endgroup$ – beerzil charlemagne Oct 12 at 7:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.