Mixing
Number of elements in a multiplicative group
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Given $n$ the square of a prime odd number. How many elements $bar x
∈$ $Z^*_n$ with $bar x ^2$ = $bar 1$?
Given $n$ the product of two distinct prime numbers. How many elements
$bar x ∈$ $Z^*_n$ with $bar x ^2$ = $bar 1$?
Not knowing the value of $n$, how can I find out that cardinality? Is there any theorem that I should follow to induce $n$?
abstract-algebra group-theory
asked Jul 17 at 14:39
CptPackage
417
add a comment |Â
up vote
1
down vote
favorite
Given $n$ the square of a prime odd number. How many elements $bar x
∈$ $Z^*_n$ with $bar x ^2$ = $bar 1$?
Given $n$ the product of two distinct prime numbers. How many elements
$bar x ∈$ $Z^*_n$ with $bar x ^2$ = $bar 1$?
Not knowing the value of $n$, how can I find out that cardinality? Is there any theorem that I should follow to induce $n$?
abstract-algebra group-theory
asked Jul 17 at 14:39
CptPackage
417
4
I think that if you work it out by hand for a few specific $n$, you'll see a pattern and realize the answer to your question.
– Mike Pierce
Jul 17 at 14:50
Euler's generalization of Fermat's Little Theorem is certainly relevant here.
– hardmath
Jul 17 at 14:55
@hardmath I know there is a relation between them but actually don't know how to connect the points.
– CptPackage
Jul 17 at 15:59
I'm going to suggest you check the definition of "multiplicative group" $mathbb Z_n^*$ and the well-known characterization of which ones are cyclic. You can also approach this problem using logic of the Chinese Remainder Thm., noting that $x^2 equiv 1 bmod p$ is a polynomial equation over a field when $p$ is prime.
– hardmath
Jul 17 at 16:54
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Given $n$ the square of a prime odd number. How many elements $bar x
∈$ $Z^*_n$ with $bar x ^2$ = $bar 1$?
Given $n$ the product of two distinct prime numbers. How many elements
$bar x ∈$ $Z^*_n$ with $bar x ^2$ = $bar 1$?
Not knowing the value of $n$, how can I find out that cardinality? Is there any theorem that I should follow to induce $n$?
abstract-algebra group-theory
asked Jul 17 at 14:39
CptPackage
417
Given $n$ the square of a prime odd number. How many elements $bar x
∈$ $Z^*_n$ with $bar x ^2$ = $bar 1$?
Given $n$ the product of two distinct prime numbers. How many elements
$bar x ∈$ $Z^*_n$ with $bar x ^2$ = $bar 1$?
Not knowing the value of $n$, how can I find out that cardinality? Is there any theorem that I should follow to induce $n$?
abstract-algebra group-theory
asked Jul 17 at 14:39
CptPackage
417
asked Jul 17 at 14:39
CptPackage
417
asked Jul 17 at 14:39
CptPackage
417
asked Jul 17 at 14:39
CptPackage
417
417
4
I think that if you work it out by hand for a few specific $n$, you'll see a pattern and realize the answer to your question.
– Mike Pierce
Jul 17 at 14:50
Euler's generalization of Fermat's Little Theorem is certainly relevant here.
– hardmath
Jul 17 at 14:55
@hardmath I know there is a relation between them but actually don't know how to connect the points.
– CptPackage
Jul 17 at 15:59
I'm going to suggest you check the definition of "multiplicative group" $mathbb Z_n^*$ and the well-known characterization of which ones are cyclic. You can also approach this problem using logic of the Chinese Remainder Thm., noting that $x^2 equiv 1 bmod p$ is a polynomial equation over a field when $p$ is prime.
– hardmath
Jul 17 at 16:54
add a comment |Â
4
I think that if you work it out by hand for a few specific $n$, you'll see a pattern and realize the answer to your question.
– Mike Pierce
Jul 17 at 14:50
Euler's generalization of Fermat's Little Theorem is certainly relevant here.
– hardmath
Jul 17 at 14:55
@hardmath I know there is a relation between them but actually don't know how to connect the points.
– CptPackage
Jul 17 at 15:59
I'm going to suggest you check the definition of "multiplicative group" $mathbb Z_n^*$ and the well-known characterization of which ones are cyclic. You can also approach this problem using logic of the Chinese Remainder Thm., noting that $x^2 equiv 1 bmod p$ is a polynomial equation over a field when $p$ is prime.
– hardmath
Jul 17 at 16:54
4
4
I think that if you work it out by hand for a few specific $n$, you'll see a pattern and realize the answer to your question.
– Mike Pierce
Jul 17 at 14:50
I think that if you work it out by hand for a few specific $n$, you'll see a pattern and realize the answer to your question.
– Mike Pierce
Jul 17 at 14:50
Euler's generalization of Fermat's Little Theorem is certainly relevant here.
– hardmath
Jul 17 at 14:55
Euler's generalization of Fermat's Little Theorem is certainly relevant here.
– hardmath
Jul 17 at 14:55
@hardmath I know there is a relation between them but actually don't know how to connect the points.
– CptPackage
Jul 17 at 15:59
@hardmath I know there is a relation between them but actually don't know how to connect the points.
– CptPackage
Jul 17 at 15:59
I'm going to suggest you check the definition of "multiplicative group" $mathbb Z_n^*$ and the well-known characterization of which ones are cyclic. You can also approach this problem using logic of the Chinese Remainder Thm., noting that $x^2 equiv 1 bmod p$ is a polynomial equation over a field when $p$ is prime.
– hardmath
Jul 17 at 16:54
I'm going to suggest you check the definition of "multiplicative group" $mathbb Z_n^*$ and the well-known characterization of which ones are cyclic. You can also approach this problem using logic of the Chinese Remainder Thm., noting that $x^2 equiv 1 bmod p$ is a polynomial equation over a field when $p$ is prime.
– hardmath
Jul 17 at 16:54
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
3
down vote
For the first question: Let $n = p^2$. We're interested in $x$ such that $x^1 equiv 1 pmod p^2$. That is $p^2 | x^2 - 1$. We see that this is then equivalent to $p^2 | (x - 1)(x + 1)$. We have three cases:
$p|(x - 1)$ and $p|(x + 1)$:
If $p|(x - 1)$ and $p|(x + 1)$ then $p|(x + 1 - (x -1 )) = 2$. Since $p$ is an odd prime, this is not possible, so this case cannot happen.
$p^2|(x - 1)$:
In this case $x equiv 1 pmod p^2$.
$p^2|(x + 1)$:
In this case $x equiv p^2-1 pmod p^2$.
Thus if $n = p^2$ for an odd prime there are exactly two solutions to $x^2 equiv 1 pmod n$, namely $1$ and $p^2 - 1$.
Next suppose $n = pq$ for distinct primes $p$ and $q$. Again we can arrive at the equation $pq|(x + 1)(x - 1)$. We then have four cases:
$p|(x + 1)$, $q|(x - 1)$:
In this case we have $x + 1 = kp$ and $x - 1 = mq$. That is $x equiv 1 pmod q$ and $x equiv -1 pmod p$. Note that by the Chinese Remainder Theorem, this has a unique solution modulo $pq$.
$p|(x - 1)$, $q|(x + 1)$:
As above this congruence has a unique solution modulo $pq$ by the Chinese Remainder Theorem.
$pq|(x + 1)$:
In this case $x equiv pq - 1 pmodpq$
$pq|(x - 1)$:
In this case $x equiv 1 pmodpq$
Next note that one $x$ cannot satisfy any two of the cases above. This is because if such an $x$ did exist then $p|(x + 1)$, $p|(x - 1)$ and $q|(x + 1)$ and $q|(x - 1)$. As in part one, this would for $p = q = 2$, which is a contradiction. Thus there are exactly 4 solutions to $x^2 equiv 1 pmod n$ if $n$ is the product of two distinct primes.
answered Jul 17 at 16:51
Sean Haight
574418
add a comment |Â
up vote
0
down vote
$U(p^2)$ is cyclic and so $x^2=1$ has exactly two solutions.
$U(pq) cong U(p) times U(q)$ is a product of two cyclic groups and so $x^2=1$ has exactly four solutions.
answered Jul 17 at 17:42
lhf
156k9160367
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
For the first question: Let $n = p^2$. We're interested in $x$ such that $x^1 equiv 1 pmod p^2$. That is $p^2 | x^2 - 1$. We see that this is then equivalent to $p^2 | (x - 1)(x + 1)$. We have three cases:
$p|(x - 1)$ and $p|(x + 1)$:
If $p|(x - 1)$ and $p|(x + 1)$ then $p|(x + 1 - (x -1 )) = 2$. Since $p$ is an odd prime, this is not possible, so this case cannot happen.
$p^2|(x - 1)$:
In this case $x equiv 1 pmod p^2$.
$p^2|(x + 1)$:
In this case $x equiv p^2-1 pmod p^2$.
Thus if $n = p^2$ for an odd prime there are exactly two solutions to $x^2 equiv 1 pmod n$, namely $1$ and $p^2 - 1$.
Next suppose $n = pq$ for distinct primes $p$ and $q$. Again we can arrive at the equation $pq|(x + 1)(x - 1)$. We then have four cases:
$p|(x + 1)$, $q|(x - 1)$:
In this case we have $x + 1 = kp$ and $x - 1 = mq$. That is $x equiv 1 pmod q$ and $x equiv -1 pmod p$. Note that by the Chinese Remainder Theorem, this has a unique solution modulo $pq$.
$p|(x - 1)$, $q|(x + 1)$:
As above this congruence has a unique solution modulo $pq$ by the Chinese Remainder Theorem.
$pq|(x + 1)$:
In this case $x equiv pq - 1 pmodpq$
$pq|(x - 1)$:
In this case $x equiv 1 pmodpq$
Next note that one $x$ cannot satisfy any two of the cases above. This is because if such an $x$ did exist then $p|(x + 1)$, $p|(x - 1)$ and $q|(x + 1)$ and $q|(x - 1)$. As in part one, this would for $p = q = 2$, which is a contradiction. Thus there are exactly 4 solutions to $x^2 equiv 1 pmod n$ if $n$ is the product of two distinct primes.
answered Jul 17 at 16:51
Sean Haight
574418
add a comment |Â
up vote
3
down vote
For the first question: Let $n = p^2$. We're interested in $x$ such that $x^1 equiv 1 pmod p^2$. That is $p^2 | x^2 - 1$. We see that this is then equivalent to $p^2 | (x - 1)(x + 1)$. We have three cases:
$p|(x - 1)$ and $p|(x + 1)$:
If $p|(x - 1)$ and $p|(x + 1)$ then $p|(x + 1 - (x -1 )) = 2$. Since $p$ is an odd prime, this is not possible, so this case cannot happen.
$p^2|(x - 1)$:
In this case $x equiv 1 pmod p^2$.
$p^2|(x + 1)$:
In this case $x equiv p^2-1 pmod p^2$.
Thus if $n = p^2$ for an odd prime there are exactly two solutions to $x^2 equiv 1 pmod n$, namely $1$ and $p^2 - 1$.
Next suppose $n = pq$ for distinct primes $p$ and $q$. Again we can arrive at the equation $pq|(x + 1)(x - 1)$. We then have four cases:
$p|(x + 1)$, $q|(x - 1)$:
In this case we have $x + 1 = kp$ and $x - 1 = mq$. That is $x equiv 1 pmod q$ and $x equiv -1 pmod p$. Note that by the Chinese Remainder Theorem, this has a unique solution modulo $pq$.
$p|(x - 1)$, $q|(x + 1)$:
As above this congruence has a unique solution modulo $pq$ by the Chinese Remainder Theorem.
$pq|(x + 1)$:
In this case $x equiv pq - 1 pmodpq$
$pq|(x - 1)$:
In this case $x equiv 1 pmodpq$
Next note that one $x$ cannot satisfy any two of the cases above. This is because if such an $x$ did exist then $p|(x + 1)$, $p|(x - 1)$ and $q|(x + 1)$ and $q|(x - 1)$. As in part one, this would for $p = q = 2$, which is a contradiction. Thus there are exactly 4 solutions to $x^2 equiv 1 pmod n$ if $n$ is the product of two distinct primes.
answered Jul 17 at 16:51
Sean Haight
574418
add a comment |Â
up vote
3
down vote
up vote
3
down vote
For the first question: Let $n = p^2$. We're interested in $x$ such that $x^1 equiv 1 pmod p^2$. That is $p^2 | x^2 - 1$. We see that this is then equivalent to $p^2 | (x - 1)(x + 1)$. We have three cases:
$p|(x - 1)$ and $p|(x + 1)$:
If $p|(x - 1)$ and $p|(x + 1)$ then $p|(x + 1 - (x -1 )) = 2$. Since $p$ is an odd prime, this is not possible, so this case cannot happen.
$p^2|(x - 1)$:
In this case $x equiv 1 pmod p^2$.
$p^2|(x + 1)$:
In this case $x equiv p^2-1 pmod p^2$.
Thus if $n = p^2$ for an odd prime there are exactly two solutions to $x^2 equiv 1 pmod n$, namely $1$ and $p^2 - 1$.
Next suppose $n = pq$ for distinct primes $p$ and $q$. Again we can arrive at the equation $pq|(x + 1)(x - 1)$. We then have four cases:
$p|(x + 1)$, $q|(x - 1)$:
In this case we have $x + 1 = kp$ and $x - 1 = mq$. That is $x equiv 1 pmod q$ and $x equiv -1 pmod p$. Note that by the Chinese Remainder Theorem, this has a unique solution modulo $pq$.
$p|(x - 1)$, $q|(x + 1)$:
As above this congruence has a unique solution modulo $pq$ by the Chinese Remainder Theorem.
$pq|(x + 1)$:
In this case $x equiv pq - 1 pmodpq$
$pq|(x - 1)$:
In this case $x equiv 1 pmodpq$
Next note that one $x$ cannot satisfy any two of the cases above. This is because if such an $x$ did exist then $p|(x + 1)$, $p|(x - 1)$ and $q|(x + 1)$ and $q|(x - 1)$. As in part one, this would for $p = q = 2$, which is a contradiction. Thus there are exactly 4 solutions to $x^2 equiv 1 pmod n$ if $n$ is the product of two distinct primes.
answered Jul 17 at 16:51
Sean Haight
574418
For the first question: Let $n = p^2$. We're interested in $x$ such that $x^1 equiv 1 pmod p^2$. That is $p^2 | x^2 - 1$. We see that this is then equivalent to $p^2 | (x - 1)(x + 1)$. We have three cases:
$p|(x - 1)$ and $p|(x + 1)$:
If $p|(x - 1)$ and $p|(x + 1)$ then $p|(x + 1 - (x -1 )) = 2$. Since $p$ is an odd prime, this is not possible, so this case cannot happen.
$p^2|(x - 1)$:
In this case $x equiv 1 pmod p^2$.
$p^2|(x + 1)$:
In this case $x equiv p^2-1 pmod p^2$.
Thus if $n = p^2$ for an odd prime there are exactly two solutions to $x^2 equiv 1 pmod n$, namely $1$ and $p^2 - 1$.
Next suppose $n = pq$ for distinct primes $p$ and $q$. Again we can arrive at the equation $pq|(x + 1)(x - 1)$. We then have four cases:
$p|(x + 1)$, $q|(x - 1)$:
In this case we have $x + 1 = kp$ and $x - 1 = mq$. That is $x equiv 1 pmod q$ and $x equiv -1 pmod p$. Note that by the Chinese Remainder Theorem, this has a unique solution modulo $pq$.
$p|(x - 1)$, $q|(x + 1)$:
As above this congruence has a unique solution modulo $pq$ by the Chinese Remainder Theorem.
$pq|(x + 1)$:
In this case $x equiv pq - 1 pmodpq$
$pq|(x - 1)$:
In this case $x equiv 1 pmodpq$
Next note that one $x$ cannot satisfy any two of the cases above. This is because if such an $x$ did exist then $p|(x + 1)$, $p|(x - 1)$ and $q|(x + 1)$ and $q|(x - 1)$. As in part one, this would for $p = q = 2$, which is a contradiction. Thus there are exactly 4 solutions to $x^2 equiv 1 pmod n$ if $n$ is the product of two distinct primes.
answered Jul 17 at 16:51
Sean Haight
574418
answered Jul 17 at 16:51
Sean Haight
574418
answered Jul 17 at 16:51
Sean Haight
574418
answered Jul 17 at 16:51
Sean Haight
574418
574418
add a comment |Â
add a comment |Â
up vote
0
down vote
$U(p^2)$ is cyclic and so $x^2=1$ has exactly two solutions.
$U(pq) cong U(p) times U(q)$ is a product of two cyclic groups and so $x^2=1$ has exactly four solutions.
answered Jul 17 at 17:42
lhf
156k9160367
add a comment |Â
up vote
0
down vote
$U(p^2)$ is cyclic and so $x^2=1$ has exactly two solutions.
$U(pq) cong U(p) times U(q)$ is a product of two cyclic groups and so $x^2=1$ has exactly four solutions.
answered Jul 17 at 17:42
lhf
156k9160367
add a comment |Â
up vote
0
down vote
up vote
0
down vote
$U(p^2)$ is cyclic and so $x^2=1$ has exactly two solutions.
$U(pq) cong U(p) times U(q)$ is a product of two cyclic groups and so $x^2=1$ has exactly four solutions.
answered Jul 17 at 17:42
lhf
156k9160367
$U(p^2)$ is cyclic and so $x^2=1$ has exactly two solutions.
$U(pq) cong U(p) times U(q)$ is a product of two cyclic groups and so $x^2=1$ has exactly four solutions.
answered Jul 17 at 17:42
lhf
156k9160367
answered Jul 17 at 17:42
lhf
156k9160367
answered Jul 17 at 17:42
lhf
156k9160367
answered Jul 17 at 17:42
lhf
156k9160367
156k9160367
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%2f2854564%2fnumber-of-elements-in-a-multiplicative-group%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
4
I think that if you work it out by hand for a few specific $n$, you'll see a pattern and realize the answer to your question.
– Mike Pierce
Jul 17 at 14:50
Euler's generalization of Fermat's Little Theorem is certainly relevant here.
– hardmath
Jul 17 at 14:55
@hardmath I know there is a relation between them but actually don't know how to connect the points.
– CptPackage
Jul 17 at 15:59
I'm going to suggest you check the definition of "multiplicative group" $mathbb Z_n^*$ and the well-known characterization of which ones are cyclic. You can also approach this problem using logic of the Chinese Remainder Thm., noting that $x^2 equiv 1 bmod p$ is a polynomial equation over a field when $p$ is prime.
– hardmath
Jul 17 at 16:54