Let $p$ be prime and let $r$ be a positive integer. How many generators does $mathbbZ_p^r$ have?
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
Can someone please help me understand this solution?
Let $p$ be prime and let $r$ be a positive integer. How many generators does $mathbbZ_p^r$ have?
I do not understand the part that is underlined in red. Why $p^r-p$? Because then $gcd(p^r,p^r-p)=pneq 1$?
prime-numbers proof-explanation cyclic-groups
asked Aug 13 at 5:06
numericalorange
1,266110
add a comment |Â
up vote
3
down vote
favorite
Can someone please help me understand this solution?
Let $p$ be prime and let $r$ be a positive integer. How many generators does $mathbbZ_p^r$ have?
I do not understand the part that is underlined in red. Why $p^r-p$? Because then $gcd(p^r,p^r-p)=pneq 1$?
prime-numbers proof-explanation cyclic-groups
asked Aug 13 at 5:06
numericalorange
1,266110
They are listing the multiples of $p$ smaller than $p^r$. The part that you should not understand is "$x$ divides $p^r$ if and only if $x$ divides $p$", which is wrong.
– user583185
Aug 13 at 5:13
1
The solution should say: These elements are not relatively prime to $p^r$. Note that if $x=p^ka$, for $k>0$, then $nx=p^k(na)$, therefore it cannot generate $1$. Therefore, the elements that don't generate $mathbbZ_p^r$ are those that are multiples of $p$ smaller than $p^r$. Those are $p,2p,3p,...,p^r-p$...
– user583185
Aug 13 at 5:21
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
Can someone please help me understand this solution?
Let $p$ be prime and let $r$ be a positive integer. How many generators does $mathbbZ_p^r$ have?
I do not understand the part that is underlined in red. Why $p^r-p$? Because then $gcd(p^r,p^r-p)=pneq 1$?
prime-numbers proof-explanation cyclic-groups
asked Aug 13 at 5:06
numericalorange
1,266110
Can someone please help me understand this solution?
Let $p$ be prime and let $r$ be a positive integer. How many generators does $mathbbZ_p^r$ have?
I do not understand the part that is underlined in red. Why $p^r-p$? Because then $gcd(p^r,p^r-p)=pneq 1$?
prime-numbers proof-explanation cyclic-groups
asked Aug 13 at 5:06
numericalorange
1,266110
asked Aug 13 at 5:06
numericalorange
1,266110
asked Aug 13 at 5:06
numericalorange
1,266110
asked Aug 13 at 5:06
numericalorange
1,266110
1,266110
They are listing the multiples of $p$ smaller than $p^r$. The part that you should not understand is "$x$ divides $p^r$ if and only if $x$ divides $p$", which is wrong.
– user583185
Aug 13 at 5:13
1
The solution should say: These elements are not relatively prime to $p^r$. Note that if $x=p^ka$, for $k>0$, then $nx=p^k(na)$, therefore it cannot generate $1$. Therefore, the elements that don't generate $mathbbZ_p^r$ are those that are multiples of $p$ smaller than $p^r$. Those are $p,2p,3p,...,p^r-p$...
– user583185
Aug 13 at 5:21
add a comment |Â
They are listing the multiples of $p$ smaller than $p^r$. The part that you should not understand is "$x$ divides $p^r$ if and only if $x$ divides $p$", which is wrong.
– user583185
Aug 13 at 5:13
1
The solution should say: These elements are not relatively prime to $p^r$. Note that if $x=p^ka$, for $k>0$, then $nx=p^k(na)$, therefore it cannot generate $1$. Therefore, the elements that don't generate $mathbbZ_p^r$ are those that are multiples of $p$ smaller than $p^r$. Those are $p,2p,3p,...,p^r-p$...
– user583185
Aug 13 at 5:21
They are listing the multiples of $p$ smaller than $p^r$. The part that you should not understand is "$x$ divides $p^r$ if and only if $x$ divides $p$", which is wrong.
– user583185
Aug 13 at 5:13
They are listing the multiples of $p$ smaller than $p^r$. The part that you should not understand is "$x$ divides $p^r$ if and only if $x$ divides $p$", which is wrong.
– user583185
Aug 13 at 5:13
1
1
The solution should say: These elements are not relatively prime to $p^r$. Note that if $x=p^ka$, for $k>0$, then $nx=p^k(na)$, therefore it cannot generate $1$. Therefore, the elements that don't generate $mathbbZ_p^r$ are those that are multiples of $p$ smaller than $p^r$. Those are $p,2p,3p,...,p^r-p$...
– user583185
Aug 13 at 5:21
The solution should say: These elements are not relatively prime to $p^r$. Note that if $x=p^ka$, for $k>0$, then $nx=p^k(na)$, therefore it cannot generate $1$. Therefore, the elements that don't generate $mathbbZ_p^r$ are those that are multiples of $p$ smaller than $p^r$. Those are $p,2p,3p,...,p^r-p$...
– user583185
Aug 13 at 5:21
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
3
down vote
accepted
$x in mathbbZ_p^r$ is not a generator of $mathbbZ_p^r$ iff its order is strictly smaller, that is, iff its order is a proper divisor of $p^r$ (this follows from Lagrange's Theorem). So, to count the number of non-generators of $mathbbZ_p^r$, we need to count the number of proper divisors of $p^r$. This is because an element $x in mathbbZ_p^r$ has order properly dividing $p^r$ iff $x$ is relatively prime to $p^r$ (show this!).
The proper divisors of $p^r$ are nothing but all the multiples of $p$ that are strictly smaller than $p^r$. These are nothing but
$$
p, 2p, 3p,dots,(p-1)p, p^2, (p+1)p,dots,(2p-1)p,2p^2,(2p+1)p,dots,(p^r-1-1)p.
$$
Observe that this list is nothing but the set of all multiples of $p$, from $1 cdot p$ to $(p^r-1-1) cdot p$. The next multiple of $p$ is $p^r-1 cdot p = p^r$, but we wanted all proper divisors, so we have omitted this last one.
Part of your confusion might stem from the fact that the statement
Note that for $x in mathbbZ$, $x$ divides $p^r$ if and only if $x$ divides $p$.
is incorrect. For instance, $p^r$ divides $p^r$, but $p^r$ does not divide $p$ if $r > 1$.
answered Aug 13 at 5:20
Brahadeesh
3,95431549
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
$x in mathbbZ_p^r$ is not a generator of $mathbbZ_p^r$ iff its order is strictly smaller, that is, iff its order is a proper divisor of $p^r$ (this follows from Lagrange's Theorem). So, to count the number of non-generators of $mathbbZ_p^r$, we need to count the number of proper divisors of $p^r$. This is because an element $x in mathbbZ_p^r$ has order properly dividing $p^r$ iff $x$ is relatively prime to $p^r$ (show this!).
The proper divisors of $p^r$ are nothing but all the multiples of $p$ that are strictly smaller than $p^r$. These are nothing but
$$
p, 2p, 3p,dots,(p-1)p, p^2, (p+1)p,dots,(2p-1)p,2p^2,(2p+1)p,dots,(p^r-1-1)p.
$$
Observe that this list is nothing but the set of all multiples of $p$, from $1 cdot p$ to $(p^r-1-1) cdot p$. The next multiple of $p$ is $p^r-1 cdot p = p^r$, but we wanted all proper divisors, so we have omitted this last one.
Part of your confusion might stem from the fact that the statement
Note that for $x in mathbbZ$, $x$ divides $p^r$ if and only if $x$ divides $p$.
is incorrect. For instance, $p^r$ divides $p^r$, but $p^r$ does not divide $p$ if $r > 1$.
answered Aug 13 at 5:20
Brahadeesh
3,95431549
add a comment |Â
up vote
3
down vote
accepted
$x in mathbbZ_p^r$ is not a generator of $mathbbZ_p^r$ iff its order is strictly smaller, that is, iff its order is a proper divisor of $p^r$ (this follows from Lagrange's Theorem). So, to count the number of non-generators of $mathbbZ_p^r$, we need to count the number of proper divisors of $p^r$. This is because an element $x in mathbbZ_p^r$ has order properly dividing $p^r$ iff $x$ is relatively prime to $p^r$ (show this!).
The proper divisors of $p^r$ are nothing but all the multiples of $p$ that are strictly smaller than $p^r$. These are nothing but
$$
p, 2p, 3p,dots,(p-1)p, p^2, (p+1)p,dots,(2p-1)p,2p^2,(2p+1)p,dots,(p^r-1-1)p.
$$
Observe that this list is nothing but the set of all multiples of $p$, from $1 cdot p$ to $(p^r-1-1) cdot p$. The next multiple of $p$ is $p^r-1 cdot p = p^r$, but we wanted all proper divisors, so we have omitted this last one.
Part of your confusion might stem from the fact that the statement
Note that for $x in mathbbZ$, $x$ divides $p^r$ if and only if $x$ divides $p$.
is incorrect. For instance, $p^r$ divides $p^r$, but $p^r$ does not divide $p$ if $r > 1$.
answered Aug 13 at 5:20
Brahadeesh
3,95431549
add a comment |Â
up vote
3
down vote
accepted
up vote
3
down vote
accepted
$x in mathbbZ_p^r$ is not a generator of $mathbbZ_p^r$ iff its order is strictly smaller, that is, iff its order is a proper divisor of $p^r$ (this follows from Lagrange's Theorem). So, to count the number of non-generators of $mathbbZ_p^r$, we need to count the number of proper divisors of $p^r$. This is because an element $x in mathbbZ_p^r$ has order properly dividing $p^r$ iff $x$ is relatively prime to $p^r$ (show this!).
The proper divisors of $p^r$ are nothing but all the multiples of $p$ that are strictly smaller than $p^r$. These are nothing but
$$
p, 2p, 3p,dots,(p-1)p, p^2, (p+1)p,dots,(2p-1)p,2p^2,(2p+1)p,dots,(p^r-1-1)p.
$$
Observe that this list is nothing but the set of all multiples of $p$, from $1 cdot p$ to $(p^r-1-1) cdot p$. The next multiple of $p$ is $p^r-1 cdot p = p^r$, but we wanted all proper divisors, so we have omitted this last one.
Part of your confusion might stem from the fact that the statement
Note that for $x in mathbbZ$, $x$ divides $p^r$ if and only if $x$ divides $p$.
is incorrect. For instance, $p^r$ divides $p^r$, but $p^r$ does not divide $p$ if $r > 1$.
answered Aug 13 at 5:20
Brahadeesh
3,95431549
$x in mathbbZ_p^r$ is not a generator of $mathbbZ_p^r$ iff its order is strictly smaller, that is, iff its order is a proper divisor of $p^r$ (this follows from Lagrange's Theorem). So, to count the number of non-generators of $mathbbZ_p^r$, we need to count the number of proper divisors of $p^r$. This is because an element $x in mathbbZ_p^r$ has order properly dividing $p^r$ iff $x$ is relatively prime to $p^r$ (show this!).
The proper divisors of $p^r$ are nothing but all the multiples of $p$ that are strictly smaller than $p^r$. These are nothing but
$$
p, 2p, 3p,dots,(p-1)p, p^2, (p+1)p,dots,(2p-1)p,2p^2,(2p+1)p,dots,(p^r-1-1)p.
$$
Observe that this list is nothing but the set of all multiples of $p$, from $1 cdot p$ to $(p^r-1-1) cdot p$. The next multiple of $p$ is $p^r-1 cdot p = p^r$, but we wanted all proper divisors, so we have omitted this last one.
Part of your confusion might stem from the fact that the statement
Note that for $x in mathbbZ$, $x$ divides $p^r$ if and only if $x$ divides $p$.
is incorrect. For instance, $p^r$ divides $p^r$, but $p^r$ does not divide $p$ if $r > 1$.
answered Aug 13 at 5:20
Brahadeesh
3,95431549
edited Aug 13 at 21:36
answered Aug 13 at 5:20
Brahadeesh
3,95431549
answered Aug 13 at 5:20
Brahadeesh
3,95431549
answered Aug 13 at 5:20
Brahadeesh
3,95431549
3,95431549
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%2f2881016%2flet-p-be-prime-and-let-r-be-a-positive-integer-how-many-generators-does-m%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
They are listing the multiples of $p$ smaller than $p^r$. The part that you should not understand is "$x$ divides $p^r$ if and only if $x$ divides $p$", which is wrong.
– user583185
Aug 13 at 5:13
1
The solution should say: These elements are not relatively prime to $p^r$. Note that if $x=p^ka$, for $k>0$, then $nx=p^k(na)$, therefore it cannot generate $1$. Therefore, the elements that don't generate $mathbbZ_p^r$ are those that are multiples of $p$ smaller than $p^r$. Those are $p,2p,3p,...,p^r-p$...
– user583185
Aug 13 at 5:21