Mixing
Proof that every prime has a primitive root.
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
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_p-1F(m)
$$
By theorem 42 we know that:
$$p-1=sum_p-1phi(m)
$$
By Lemma 11,F(m)≤Æ(m) when m|(p−1). Together with:
$$sum_p-1F(m)=sum_p-1phi(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_p-1F(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
number-theory elementary-number-theory modular-arithmetic
asked Jul 23 at 13:51
Spasoje Durovic
113
add a comment |Â
up vote
1
down vote
favorite
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_p-1F(m)
$$
By theorem 42 we know that:
$$p-1=sum_p-1phi(m)
$$
By Lemma 11,F(m)≤Æ(m) when m|(p−1). Together with:
$$sum_p-1F(m)=sum_p-1phi(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_p-1F(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
number-theory elementary-number-theory modular-arithmetic
asked Jul 23 at 13:51
Spasoje Durovic
113
Try this for some small prime like $5$ or $7$ and you'll see.
– saulspatz
Jul 23 at 13:57
The nonzero elements of the $p$-element field form a group under multiplication of order $p-1$; thus the multiplicative order must be a divisor of $p-1$.
– egreg
Jul 23 at 14:10
Recall how you defined $F(m)$, "Let $F(m)$ be the number of positive integers of order $mbmod p$ that are less than $p$." What's the order of the group?
– sharding4
Jul 23 at 14:29
Nice proof actually. Another proof is a corollary of the (much longer) result that if $(F, +,0,times, 1)$ is a finite field then the group $(Fbackslash 0, times, 1)$ is cyclic.
– DanielWainfleet
Jul 23 at 15:03
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
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_p-1F(m)
$$
By theorem 42 we know that:
$$p-1=sum_p-1phi(m)
$$
By Lemma 11,F(m)≤Æ(m) when m|(p−1). Together with:
$$sum_p-1F(m)=sum_p-1phi(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_p-1F(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
number-theory elementary-number-theory modular-arithmetic
asked Jul 23 at 13:51
Spasoje Durovic
113
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_p-1F(m)
$$
By theorem 42 we know that:
$$p-1=sum_p-1phi(m)
$$
By Lemma 11,F(m)≤Æ(m) when m|(p−1). Together with:
$$sum_p-1F(m)=sum_p-1phi(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_p-1F(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
number-theory elementary-number-theory modular-arithmetic
asked Jul 23 at 13:51
Spasoje Durovic
113
asked Jul 23 at 13:51
Spasoje Durovic
113
asked Jul 23 at 13:51
Spasoje Durovic
113
asked Jul 23 at 13:51
Spasoje Durovic
113
113
Try this for some small prime like $5$ or $7$ and you'll see.
– saulspatz
Jul 23 at 13:57
The nonzero elements of the $p$-element field form a group under multiplication of order $p-1$; thus the multiplicative order must be a divisor of $p-1$.
– egreg
Jul 23 at 14:10
Recall how you defined $F(m)$, "Let $F(m)$ be the number of positive integers of order $mbmod p$ that are less than $p$." What's the order of the group?
– sharding4
Jul 23 at 14:29
Nice proof actually. Another proof is a corollary of the (much longer) result that if $(F, +,0,times, 1)$ is a finite field then the group $(Fbackslash 0, times, 1)$ is cyclic.
– DanielWainfleet
Jul 23 at 15:03
add a comment |Â
Try this for some small prime like $5$ or $7$ and you'll see.
– saulspatz
Jul 23 at 13:57
The nonzero elements of the $p$-element field form a group under multiplication of order $p-1$; thus the multiplicative order must be a divisor of $p-1$.
– egreg
Jul 23 at 14:10
Recall how you defined $F(m)$, "Let $F(m)$ be the number of positive integers of order $mbmod p$ that are less than $p$." What's the order of the group?
– sharding4
Jul 23 at 14:29
Nice proof actually. Another proof is a corollary of the (much longer) result that if $(F, +,0,times, 1)$ is a finite field then the group $(Fbackslash 0, times, 1)$ is cyclic.
– DanielWainfleet
Jul 23 at 15:03
Try this for some small prime like $5$ or $7$ and you'll see.
– saulspatz
Jul 23 at 13:57
Try this for some small prime like $5$ or $7$ and you'll see.
– saulspatz
Jul 23 at 13:57
The nonzero elements of the $p$-element field form a group under multiplication of order $p-1$; thus the multiplicative order must be a divisor of $p-1$.
– egreg
Jul 23 at 14:10
The nonzero elements of the $p$-element field form a group under multiplication of order $p-1$; thus the multiplicative order must be a divisor of $p-1$.
– egreg
Jul 23 at 14:10
Recall how you defined $F(m)$, "Let $F(m)$ be the number of positive integers of order $mbmod p$ that are less than $p$." What's the order of the group?
– sharding4
Jul 23 at 14:29
Recall how you defined $F(m)$, "Let $F(m)$ be the number of positive integers of order $mbmod p$ that are less than $p$." What's the order of the group?
– sharding4
Jul 23 at 14:29
Nice proof actually. Another proof is a corollary of the (much longer) result that if $(F, +,0,times, 1)$ is a finite field then the group $(Fbackslash 0, times, 1)$ is cyclic.
– DanielWainfleet
Jul 23 at 15:03
Nice proof actually. Another proof is a corollary of the (much longer) result that if $(F, +,0,times, 1)$ is a finite field then the group $(Fbackslash 0, times, 1)$ is cyclic.
– DanielWainfleet
Jul 23 at 15:03
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
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^inftyF(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_p-1F(m)$$
answered Jul 23 at 14:48
Jaap Scherphuis
3,153214
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
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^inftyF(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_p-1F(m)$$
answered Jul 23 at 14:48
Jaap Scherphuis
3,153214
add a comment |Â
up vote
2
down vote
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^inftyF(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_p-1F(m)$$
answered Jul 23 at 14:48
Jaap Scherphuis
3,153214
add a comment |Â
up vote
2
down vote
up vote
2
down vote
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^inftyF(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_p-1F(m)$$
answered Jul 23 at 14:48
Jaap Scherphuis
3,153214
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^inftyF(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_p-1F(m)$$
answered Jul 23 at 14:48
Jaap Scherphuis
3,153214
answered Jul 23 at 14:48
Jaap Scherphuis
3,153214
answered Jul 23 at 14:48
Jaap Scherphuis
3,153214
answered Jul 23 at 14:48
Jaap Scherphuis
3,153214
3,153214
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2860396%2fproof-that-every-prime-has-a-primitive-root%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Try this for some small prime like $5$ or $7$ and you'll see.
– saulspatz
Jul 23 at 13:57
The nonzero elements of the $p$-element field form a group under multiplication of order $p-1$; thus the multiplicative order must be a divisor of $p-1$.
– egreg
Jul 23 at 14:10
Recall how you defined $F(m)$, "Let $F(m)$ be the number of positive integers of order $mbmod p$ that are less than $p$." What's the order of the group?
– sharding4
Jul 23 at 14:29
Nice proof actually. Another proof is a corollary of the (much longer) result that if $(F, +,0,times, 1)$ is a finite field then the group $(Fbackslash 0, times, 1)$ is cyclic.
– DanielWainfleet
Jul 23 at 15:03