Mixing
Chinese Remainder Theorem: four square roots of 1 modulo N
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
Given an odd composite number $N$, where $N$ is not a prime power, I read the following in a Wikipedia article:
As a consequence of the Chinese remainder theorem, the number $1$ has at
least four distinct square roots modulo $N$, two of them being $1$ and $-1$.
The square roots of $1$ and $-1$ are obvious to me. What I don't understand is why there are necessarily two others.
Can anyone prove how this result follows from the Chinese remainder theorem?
number-theory modular-arithmetic chinese-remainder-theorem
asked Jul 19 at 15:46
Jean-Jacq du Plessis
585
add a comment |Â
up vote
3
down vote
favorite
Given an odd composite number $N$, where $N$ is not a prime power, I read the following in a Wikipedia article:
As a consequence of the Chinese remainder theorem, the number $1$ has at
least four distinct square roots modulo $N$, two of them being $1$ and $-1$.
The square roots of $1$ and $-1$ are obvious to me. What I don't understand is why there are necessarily two others.
Can anyone prove how this result follows from the Chinese remainder theorem?
number-theory modular-arithmetic chinese-remainder-theorem
asked Jul 19 at 15:46
Jean-Jacq du Plessis
585
The correct statement is that $N$ should be the product of two (distinct) odd primes
– Lubin
Jul 19 at 15:53
1
@gammatester Sorry, there was a detail I missed: N is not a prime power (edited now)
– Jean-Jacq du Plessis
Jul 19 at 15:55
Good. now you use CRT, to find something that’s like $1$ at one prime, $-1$ at another.
– Lubin
Jul 19 at 15:56
"The correct statement is that N should be the product of two (distinct) odd primes" Actually "N is the product of two relatively prime odd numbers other than one". They don't need to be prime. Just odd, and relatively prime to each other.
– fleablood
Jul 19 at 20:00
And N doesn't need to be odd. It just needs to be the product of two relatively prime numbers larger than $2$.
– fleablood
Jul 19 at 20:03
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
Given an odd composite number $N$, where $N$ is not a prime power, I read the following in a Wikipedia article:
As a consequence of the Chinese remainder theorem, the number $1$ has at
least four distinct square roots modulo $N$, two of them being $1$ and $-1$.
The square roots of $1$ and $-1$ are obvious to me. What I don't understand is why there are necessarily two others.
Can anyone prove how this result follows from the Chinese remainder theorem?
number-theory modular-arithmetic chinese-remainder-theorem
asked Jul 19 at 15:46
Jean-Jacq du Plessis
585
Given an odd composite number $N$, where $N$ is not a prime power, I read the following in a Wikipedia article:
As a consequence of the Chinese remainder theorem, the number $1$ has at
least four distinct square roots modulo $N$, two of them being $1$ and $-1$.
The square roots of $1$ and $-1$ are obvious to me. What I don't understand is why there are necessarily two others.
Can anyone prove how this result follows from the Chinese remainder theorem?
number-theory modular-arithmetic chinese-remainder-theorem
asked Jul 19 at 15:46
Jean-Jacq du Plessis
585
edited Jul 19 at 15:54
asked Jul 19 at 15:46
Jean-Jacq du Plessis
585
asked Jul 19 at 15:46
Jean-Jacq du Plessis
585
asked Jul 19 at 15:46
Jean-Jacq du Plessis
585
585
The correct statement is that $N$ should be the product of two (distinct) odd primes
– Lubin
Jul 19 at 15:53
1
@gammatester Sorry, there was a detail I missed: N is not a prime power (edited now)
– Jean-Jacq du Plessis
Jul 19 at 15:55
Good. now you use CRT, to find something that’s like $1$ at one prime, $-1$ at another.
– Lubin
Jul 19 at 15:56
"The correct statement is that N should be the product of two (distinct) odd primes" Actually "N is the product of two relatively prime odd numbers other than one". They don't need to be prime. Just odd, and relatively prime to each other.
– fleablood
Jul 19 at 20:00
And N doesn't need to be odd. It just needs to be the product of two relatively prime numbers larger than $2$.
– fleablood
Jul 19 at 20:03
add a comment |Â
The correct statement is that $N$ should be the product of two (distinct) odd primes
– Lubin
Jul 19 at 15:53
1
@gammatester Sorry, there was a detail I missed: N is not a prime power (edited now)
– Jean-Jacq du Plessis
Jul 19 at 15:55
Good. now you use CRT, to find something that’s like $1$ at one prime, $-1$ at another.
– Lubin
Jul 19 at 15:56
"The correct statement is that N should be the product of two (distinct) odd primes" Actually "N is the product of two relatively prime odd numbers other than one". They don't need to be prime. Just odd, and relatively prime to each other.
– fleablood
Jul 19 at 20:00
And N doesn't need to be odd. It just needs to be the product of two relatively prime numbers larger than $2$.
– fleablood
Jul 19 at 20:03
The correct statement is that $N$ should be the product of two (distinct) odd primes
– Lubin
Jul 19 at 15:53
The correct statement is that $N$ should be the product of two (distinct) odd primes
– Lubin
Jul 19 at 15:53
1
1
@gammatester Sorry, there was a detail I missed: N is not a prime power (edited now)
– Jean-Jacq du Plessis
Jul 19 at 15:55
@gammatester Sorry, there was a detail I missed: N is not a prime power (edited now)
– Jean-Jacq du Plessis
Jul 19 at 15:55
Good. now you use CRT, to find something that’s like $1$ at one prime, $-1$ at another.
– Lubin
Jul 19 at 15:56
Good. now you use CRT, to find something that’s like $1$ at one prime, $-1$ at another.
– Lubin
Jul 19 at 15:56
"The correct statement is that N should be the product of two (distinct) odd primes" Actually "N is the product of two relatively prime odd numbers other than one". They don't need to be prime. Just odd, and relatively prime to each other.
– fleablood
Jul 19 at 20:00
"The correct statement is that N should be the product of two (distinct) odd primes" Actually "N is the product of two relatively prime odd numbers other than one". They don't need to be prime. Just odd, and relatively prime to each other.
– fleablood
Jul 19 at 20:00
And N doesn't need to be odd. It just needs to be the product of two relatively prime numbers larger than $2$.
– fleablood
Jul 19 at 20:03
And N doesn't need to be odd. It just needs to be the product of two relatively prime numbers larger than $2$.
– fleablood
Jul 19 at 20:03
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
3
down vote
accepted
This follows very simply from the observation that if you have two coprime moduli, $p$ and $q$, then
$$begincases
xequiv a bmod p \
xequiv a bmod q \
endcases
qquad implies xequiv a bmod pq
$$
as a special case of the CRT. (I would like to write the paired equivalence as $xunderset(p,q)equiv (a,a)$)
Then apply this here with
$$begincases
x^2equiv 1 bmod p \
x^2equiv 1 bmod q \
endcases
qquad implies x^2equiv 1 bmod pq
$$
... or $x^2underset(p,q)equiv (1,1)implies x^2= 1 bmod pq$
Then with $p,q>2$ (so that $-1notequiv1$), we can see that $x^2underset(p,q)equiv (1,1)$ will hold for each of $xunderset(p,q)equiv (1,1),$ $(1,-1),(-1,1),$ $(-1,-1)$. These will each produce different roots of $1bmod pq$ with the final values of $xbmod pq$ determined through the CRT
As an example of how this works out, $21underset(5,11)equiv (1,-1)$ so $21^2underset(5,11)equiv (1,1)$ and thus $21^2equiv 1 bmod 55$.
answered Jul 19 at 16:41
Joffan
31.9k43169
I'm not sure I understand your notation in your last sentence. How is $x$ congruent to an ordered pair (or a set of them)?
– Jean-Jacq du Plessis
Jul 19 at 16:55
It's not clear to me that introducing the 'special case' of the CRT really does much here when you need the theorem's full power (or at least most of the it) to then turn e.g. $(-1, 1)$ into a single residue class mod $pq$.
– Steven Stadnicki
Jul 19 at 17:09
@StevenStadnicki To find the roots, I agree, but I'm just aiming to demonstrate their existence.
– Joffan
Jul 19 at 17:24
I don't understand how the implication that $x^2 equiv 1 mod pq$ works for, say, $(1,-1)$, since you're picking different $x's$. I'm probably misinterpreting your meaning, because I don't see how the argument implies the existence of square roots.
– Jean-Jacq du Plessis
Jul 19 at 17:36
1
Since $xequiv -1 bmod q$, clearly $xnot equiv 1 bmod pq$. And since $xequiv 1 bmod p$, clearly $xnot equiv -1 bmod pq$ (and I should point out the restriction that $p,q>2$)
– Joffan
Jul 19 at 18:07
 |Â
show 4 more comments
up vote
4
down vote
If $N$ is divisible by two distinct odd primes (say $p, q$), besides $1, -1$, you can also choose $i$ such that $i equiv 1 mod p^nu_p(N), i equiv -1 mod q^nu_q(N), i equiv 0 mod fracnp^nu_p(N)q^nu_q(N)$ and $j$ such that $j i equiv -1 mod p^nu_p(N), i equiv 1 mod q^nu_q(N), i equiv 0 mod fracnp^nu_p(n)q^nu_q(N)$.
In general if $N$ is divisible by atleast $m$ odd primes, then there are exactly $2^m$ numbers whose square is congruent to $1$ modulo $N$.
Here $nu_p(m)$ denotes the highest power of $p$ dividing $m$ (for example, $nu_3(27) = 3$, $nu_3(18) = 2$, $nu_3(10) = 0$)
answered Jul 19 at 15:58
alxchen
402320
Your line with "at least" and "exactly" seems contradictory to me. Maybe "at least" should change? Also, I'm not sure where you're going with $ji equiv -1 mod p^v_p(N)$. Would you mind explaining what that implies?
– Jean-Jacq du Plessis
Jul 19 at 16:32
add a comment |Â
up vote
0
down vote
Let $N = mn$ with $mn$ relatively prime and both odd.
Then among the equivalence classes $mod N$:
by CRT for each of the following systems of equation there is exactly one solution:
- $x equiv 1 mod m$ and $xequiv 1 mod m$. (In this case $x equiv
1 mod mn$). $y equiv 1 mod m$ and $y equiv -1 mod m$.
$w equiv -1 mod m$ and $wequiv 1mod m$
- $u equiv -1mod m$ and $wequiv -1 mod m$.(this is $u equiv -1
mod mn$).
These are four distinct values $mod mn$.
Now all four of these values have the properties that:
- $x^2 equiv y^2 equiv z^2 equiv u^2 equiv 1 mod m$ and $x^2 equiv y^2 equiv z^2 equiv u^2 equiv 1 mod n$.
By CRT there is exactly one solution $mod mn$ to that:
$x^2 equiv y^2equiv z^2 equiv u^2 equiv 1 mod mn$.
answered Jul 19 at 19:56
fleablood
60.4k22575
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
This follows very simply from the observation that if you have two coprime moduli, $p$ and $q$, then
$$begincases
xequiv a bmod p \
xequiv a bmod q \
endcases
qquad implies xequiv a bmod pq
$$
as a special case of the CRT. (I would like to write the paired equivalence as $xunderset(p,q)equiv (a,a)$)
Then apply this here with
$$begincases
x^2equiv 1 bmod p \
x^2equiv 1 bmod q \
endcases
qquad implies x^2equiv 1 bmod pq
$$
... or $x^2underset(p,q)equiv (1,1)implies x^2= 1 bmod pq$
Then with $p,q>2$ (so that $-1notequiv1$), we can see that $x^2underset(p,q)equiv (1,1)$ will hold for each of $xunderset(p,q)equiv (1,1),$ $(1,-1),(-1,1),$ $(-1,-1)$. These will each produce different roots of $1bmod pq$ with the final values of $xbmod pq$ determined through the CRT
As an example of how this works out, $21underset(5,11)equiv (1,-1)$ so $21^2underset(5,11)equiv (1,1)$ and thus $21^2equiv 1 bmod 55$.
answered Jul 19 at 16:41
Joffan
31.9k43169
I'm not sure I understand your notation in your last sentence. How is $x$ congruent to an ordered pair (or a set of them)?
– Jean-Jacq du Plessis
Jul 19 at 16:55
It's not clear to me that introducing the 'special case' of the CRT really does much here when you need the theorem's full power (or at least most of the it) to then turn e.g. $(-1, 1)$ into a single residue class mod $pq$.
– Steven Stadnicki
Jul 19 at 17:09
@StevenStadnicki To find the roots, I agree, but I'm just aiming to demonstrate their existence.
– Joffan
Jul 19 at 17:24
I don't understand how the implication that $x^2 equiv 1 mod pq$ works for, say, $(1,-1)$, since you're picking different $x's$. I'm probably misinterpreting your meaning, because I don't see how the argument implies the existence of square roots.
– Jean-Jacq du Plessis
Jul 19 at 17:36
1
Since $xequiv -1 bmod q$, clearly $xnot equiv 1 bmod pq$. And since $xequiv 1 bmod p$, clearly $xnot equiv -1 bmod pq$ (and I should point out the restriction that $p,q>2$)
– Joffan
Jul 19 at 18:07
 |Â
show 4 more comments
up vote
3
down vote
accepted
This follows very simply from the observation that if you have two coprime moduli, $p$ and $q$, then
$$begincases
xequiv a bmod p \
xequiv a bmod q \
endcases
qquad implies xequiv a bmod pq
$$
as a special case of the CRT. (I would like to write the paired equivalence as $xunderset(p,q)equiv (a,a)$)
Then apply this here with
$$begincases
x^2equiv 1 bmod p \
x^2equiv 1 bmod q \
endcases
qquad implies x^2equiv 1 bmod pq
$$
... or $x^2underset(p,q)equiv (1,1)implies x^2= 1 bmod pq$
Then with $p,q>2$ (so that $-1notequiv1$), we can see that $x^2underset(p,q)equiv (1,1)$ will hold for each of $xunderset(p,q)equiv (1,1),$ $(1,-1),(-1,1),$ $(-1,-1)$. These will each produce different roots of $1bmod pq$ with the final values of $xbmod pq$ determined through the CRT
As an example of how this works out, $21underset(5,11)equiv (1,-1)$ so $21^2underset(5,11)equiv (1,1)$ and thus $21^2equiv 1 bmod 55$.
answered Jul 19 at 16:41
Joffan
31.9k43169
I'm not sure I understand your notation in your last sentence. How is $x$ congruent to an ordered pair (or a set of them)?
– Jean-Jacq du Plessis
Jul 19 at 16:55
It's not clear to me that introducing the 'special case' of the CRT really does much here when you need the theorem's full power (or at least most of the it) to then turn e.g. $(-1, 1)$ into a single residue class mod $pq$.
– Steven Stadnicki
Jul 19 at 17:09
@StevenStadnicki To find the roots, I agree, but I'm just aiming to demonstrate their existence.
– Joffan
Jul 19 at 17:24
I don't understand how the implication that $x^2 equiv 1 mod pq$ works for, say, $(1,-1)$, since you're picking different $x's$. I'm probably misinterpreting your meaning, because I don't see how the argument implies the existence of square roots.
– Jean-Jacq du Plessis
Jul 19 at 17:36
1
Since $xequiv -1 bmod q$, clearly $xnot equiv 1 bmod pq$. And since $xequiv 1 bmod p$, clearly $xnot equiv -1 bmod pq$ (and I should point out the restriction that $p,q>2$)
– Joffan
Jul 19 at 18:07
 |Â
show 4 more comments
up vote
3
down vote
accepted
up vote
3
down vote
accepted
This follows very simply from the observation that if you have two coprime moduli, $p$ and $q$, then
$$begincases
xequiv a bmod p \
xequiv a bmod q \
endcases
qquad implies xequiv a bmod pq
$$
as a special case of the CRT. (I would like to write the paired equivalence as $xunderset(p,q)equiv (a,a)$)
Then apply this here with
$$begincases
x^2equiv 1 bmod p \
x^2equiv 1 bmod q \
endcases
qquad implies x^2equiv 1 bmod pq
$$
... or $x^2underset(p,q)equiv (1,1)implies x^2= 1 bmod pq$
Then with $p,q>2$ (so that $-1notequiv1$), we can see that $x^2underset(p,q)equiv (1,1)$ will hold for each of $xunderset(p,q)equiv (1,1),$ $(1,-1),(-1,1),$ $(-1,-1)$. These will each produce different roots of $1bmod pq$ with the final values of $xbmod pq$ determined through the CRT
As an example of how this works out, $21underset(5,11)equiv (1,-1)$ so $21^2underset(5,11)equiv (1,1)$ and thus $21^2equiv 1 bmod 55$.
answered Jul 19 at 16:41
Joffan
31.9k43169
This follows very simply from the observation that if you have two coprime moduli, $p$ and $q$, then
$$begincases
xequiv a bmod p \
xequiv a bmod q \
endcases
qquad implies xequiv a bmod pq
$$
as a special case of the CRT. (I would like to write the paired equivalence as $xunderset(p,q)equiv (a,a)$)
Then apply this here with
$$begincases
x^2equiv 1 bmod p \
x^2equiv 1 bmod q \
endcases
qquad implies x^2equiv 1 bmod pq
$$
... or $x^2underset(p,q)equiv (1,1)implies x^2= 1 bmod pq$
Then with $p,q>2$ (so that $-1notequiv1$), we can see that $x^2underset(p,q)equiv (1,1)$ will hold for each of $xunderset(p,q)equiv (1,1),$ $(1,-1),(-1,1),$ $(-1,-1)$. These will each produce different roots of $1bmod pq$ with the final values of $xbmod pq$ determined through the CRT
As an example of how this works out, $21underset(5,11)equiv (1,-1)$ so $21^2underset(5,11)equiv (1,1)$ and thus $21^2equiv 1 bmod 55$.
answered Jul 19 at 16:41
Joffan
31.9k43169
edited Jul 19 at 19:26
answered Jul 19 at 16:41
Joffan
31.9k43169
answered Jul 19 at 16:41
Joffan
31.9k43169
answered Jul 19 at 16:41
Joffan
31.9k43169
31.9k43169
I'm not sure I understand your notation in your last sentence. How is $x$ congruent to an ordered pair (or a set of them)?
– Jean-Jacq du Plessis
Jul 19 at 16:55
It's not clear to me that introducing the 'special case' of the CRT really does much here when you need the theorem's full power (or at least most of the it) to then turn e.g. $(-1, 1)$ into a single residue class mod $pq$.
– Steven Stadnicki
Jul 19 at 17:09
@StevenStadnicki To find the roots, I agree, but I'm just aiming to demonstrate their existence.
– Joffan
Jul 19 at 17:24
I don't understand how the implication that $x^2 equiv 1 mod pq$ works for, say, $(1,-1)$, since you're picking different $x's$. I'm probably misinterpreting your meaning, because I don't see how the argument implies the existence of square roots.
– Jean-Jacq du Plessis
Jul 19 at 17:36
1
Since $xequiv -1 bmod q$, clearly $xnot equiv 1 bmod pq$. And since $xequiv 1 bmod p$, clearly $xnot equiv -1 bmod pq$ (and I should point out the restriction that $p,q>2$)
– Joffan
Jul 19 at 18:07
 |Â
show 4 more comments
I'm not sure I understand your notation in your last sentence. How is $x$ congruent to an ordered pair (or a set of them)?
– Jean-Jacq du Plessis
Jul 19 at 16:55
It's not clear to me that introducing the 'special case' of the CRT really does much here when you need the theorem's full power (or at least most of the it) to then turn e.g. $(-1, 1)$ into a single residue class mod $pq$.
– Steven Stadnicki
Jul 19 at 17:09
@StevenStadnicki To find the roots, I agree, but I'm just aiming to demonstrate their existence.
– Joffan
Jul 19 at 17:24
I don't understand how the implication that $x^2 equiv 1 mod pq$ works for, say, $(1,-1)$, since you're picking different $x's$. I'm probably misinterpreting your meaning, because I don't see how the argument implies the existence of square roots.
– Jean-Jacq du Plessis
Jul 19 at 17:36
1
Since $xequiv -1 bmod q$, clearly $xnot equiv 1 bmod pq$. And since $xequiv 1 bmod p$, clearly $xnot equiv -1 bmod pq$ (and I should point out the restriction that $p,q>2$)
– Joffan
Jul 19 at 18:07
I'm not sure I understand your notation in your last sentence. How is $x$ congruent to an ordered pair (or a set of them)?
– Jean-Jacq du Plessis
Jul 19 at 16:55
I'm not sure I understand your notation in your last sentence. How is $x$ congruent to an ordered pair (or a set of them)?
– Jean-Jacq du Plessis
Jul 19 at 16:55
It's not clear to me that introducing the 'special case' of the CRT really does much here when you need the theorem's full power (or at least most of the it) to then turn e.g. $(-1, 1)$ into a single residue class mod $pq$.
– Steven Stadnicki
Jul 19 at 17:09
It's not clear to me that introducing the 'special case' of the CRT really does much here when you need the theorem's full power (or at least most of the it) to then turn e.g. $(-1, 1)$ into a single residue class mod $pq$.
– Steven Stadnicki
Jul 19 at 17:09
@StevenStadnicki To find the roots, I agree, but I'm just aiming to demonstrate their existence.
– Joffan
Jul 19 at 17:24
@StevenStadnicki To find the roots, I agree, but I'm just aiming to demonstrate their existence.
– Joffan
Jul 19 at 17:24
I don't understand how the implication that $x^2 equiv 1 mod pq$ works for, say, $(1,-1)$, since you're picking different $x's$. I'm probably misinterpreting your meaning, because I don't see how the argument implies the existence of square roots.
– Jean-Jacq du Plessis
Jul 19 at 17:36
I don't understand how the implication that $x^2 equiv 1 mod pq$ works for, say, $(1,-1)$, since you're picking different $x's$. I'm probably misinterpreting your meaning, because I don't see how the argument implies the existence of square roots.
– Jean-Jacq du Plessis
Jul 19 at 17:36
1
1
Since $xequiv -1 bmod q$, clearly $xnot equiv 1 bmod pq$. And since $xequiv 1 bmod p$, clearly $xnot equiv -1 bmod pq$ (and I should point out the restriction that $p,q>2$)
– Joffan
Jul 19 at 18:07
Since $xequiv -1 bmod q$, clearly $xnot equiv 1 bmod pq$. And since $xequiv 1 bmod p$, clearly $xnot equiv -1 bmod pq$ (and I should point out the restriction that $p,q>2$)
– Joffan
Jul 19 at 18:07
 |Â
show 4 more comments
up vote
4
down vote
If $N$ is divisible by two distinct odd primes (say $p, q$), besides $1, -1$, you can also choose $i$ such that $i equiv 1 mod p^nu_p(N), i equiv -1 mod q^nu_q(N), i equiv 0 mod fracnp^nu_p(N)q^nu_q(N)$ and $j$ such that $j i equiv -1 mod p^nu_p(N), i equiv 1 mod q^nu_q(N), i equiv 0 mod fracnp^nu_p(n)q^nu_q(N)$.
In general if $N$ is divisible by atleast $m$ odd primes, then there are exactly $2^m$ numbers whose square is congruent to $1$ modulo $N$.
Here $nu_p(m)$ denotes the highest power of $p$ dividing $m$ (for example, $nu_3(27) = 3$, $nu_3(18) = 2$, $nu_3(10) = 0$)
answered Jul 19 at 15:58
alxchen
402320
Your line with "at least" and "exactly" seems contradictory to me. Maybe "at least" should change? Also, I'm not sure where you're going with $ji equiv -1 mod p^v_p(N)$. Would you mind explaining what that implies?
– Jean-Jacq du Plessis
Jul 19 at 16:32
add a comment |Â
up vote
4
down vote
If $N$ is divisible by two distinct odd primes (say $p, q$), besides $1, -1$, you can also choose $i$ such that $i equiv 1 mod p^nu_p(N), i equiv -1 mod q^nu_q(N), i equiv 0 mod fracnp^nu_p(N)q^nu_q(N)$ and $j$ such that $j i equiv -1 mod p^nu_p(N), i equiv 1 mod q^nu_q(N), i equiv 0 mod fracnp^nu_p(n)q^nu_q(N)$.
In general if $N$ is divisible by atleast $m$ odd primes, then there are exactly $2^m$ numbers whose square is congruent to $1$ modulo $N$.
Here $nu_p(m)$ denotes the highest power of $p$ dividing $m$ (for example, $nu_3(27) = 3$, $nu_3(18) = 2$, $nu_3(10) = 0$)
answered Jul 19 at 15:58
alxchen
402320
Your line with "at least" and "exactly" seems contradictory to me. Maybe "at least" should change? Also, I'm not sure where you're going with $ji equiv -1 mod p^v_p(N)$. Would you mind explaining what that implies?
– Jean-Jacq du Plessis
Jul 19 at 16:32
add a comment |Â
up vote
4
down vote
up vote
4
down vote
If $N$ is divisible by two distinct odd primes (say $p, q$), besides $1, -1$, you can also choose $i$ such that $i equiv 1 mod p^nu_p(N), i equiv -1 mod q^nu_q(N), i equiv 0 mod fracnp^nu_p(N)q^nu_q(N)$ and $j$ such that $j i equiv -1 mod p^nu_p(N), i equiv 1 mod q^nu_q(N), i equiv 0 mod fracnp^nu_p(n)q^nu_q(N)$.
In general if $N$ is divisible by atleast $m$ odd primes, then there are exactly $2^m$ numbers whose square is congruent to $1$ modulo $N$.
Here $nu_p(m)$ denotes the highest power of $p$ dividing $m$ (for example, $nu_3(27) = 3$, $nu_3(18) = 2$, $nu_3(10) = 0$)
answered Jul 19 at 15:58
alxchen
402320
If $N$ is divisible by two distinct odd primes (say $p, q$), besides $1, -1$, you can also choose $i$ such that $i equiv 1 mod p^nu_p(N), i equiv -1 mod q^nu_q(N), i equiv 0 mod fracnp^nu_p(N)q^nu_q(N)$ and $j$ such that $j i equiv -1 mod p^nu_p(N), i equiv 1 mod q^nu_q(N), i equiv 0 mod fracnp^nu_p(n)q^nu_q(N)$.
In general if $N$ is divisible by atleast $m$ odd primes, then there are exactly $2^m$ numbers whose square is congruent to $1$ modulo $N$.
Here $nu_p(m)$ denotes the highest power of $p$ dividing $m$ (for example, $nu_3(27) = 3$, $nu_3(18) = 2$, $nu_3(10) = 0$)
answered Jul 19 at 15:58
alxchen
402320
edited Jul 19 at 16:14
answered Jul 19 at 15:58
alxchen
402320
answered Jul 19 at 15:58
alxchen
402320
answered Jul 19 at 15:58
alxchen
402320
402320
Your line with "at least" and "exactly" seems contradictory to me. Maybe "at least" should change? Also, I'm not sure where you're going with $ji equiv -1 mod p^v_p(N)$. Would you mind explaining what that implies?
– Jean-Jacq du Plessis
Jul 19 at 16:32
add a comment |Â
Your line with "at least" and "exactly" seems contradictory to me. Maybe "at least" should change? Also, I'm not sure where you're going with $ji equiv -1 mod p^v_p(N)$. Would you mind explaining what that implies?
– Jean-Jacq du Plessis
Jul 19 at 16:32
Your line with "at least" and "exactly" seems contradictory to me. Maybe "at least" should change? Also, I'm not sure where you're going with $ji equiv -1 mod p^v_p(N)$. Would you mind explaining what that implies?
– Jean-Jacq du Plessis
Jul 19 at 16:32
Your line with "at least" and "exactly" seems contradictory to me. Maybe "at least" should change? Also, I'm not sure where you're going with $ji equiv -1 mod p^v_p(N)$. Would you mind explaining what that implies?
– Jean-Jacq du Plessis
Jul 19 at 16:32
add a comment |Â
up vote
0
down vote
Let $N = mn$ with $mn$ relatively prime and both odd.
Then among the equivalence classes $mod N$:
by CRT for each of the following systems of equation there is exactly one solution:
- $x equiv 1 mod m$ and $xequiv 1 mod m$. (In this case $x equiv
1 mod mn$). $y equiv 1 mod m$ and $y equiv -1 mod m$.
$w equiv -1 mod m$ and $wequiv 1mod m$
- $u equiv -1mod m$ and $wequiv -1 mod m$.(this is $u equiv -1
mod mn$).
These are four distinct values $mod mn$.
Now all four of these values have the properties that:
- $x^2 equiv y^2 equiv z^2 equiv u^2 equiv 1 mod m$ and $x^2 equiv y^2 equiv z^2 equiv u^2 equiv 1 mod n$.
By CRT there is exactly one solution $mod mn$ to that:
$x^2 equiv y^2equiv z^2 equiv u^2 equiv 1 mod mn$.
answered Jul 19 at 19:56
fleablood
60.4k22575
add a comment |Â
up vote
0
down vote
Let $N = mn$ with $mn$ relatively prime and both odd.
Then among the equivalence classes $mod N$:
by CRT for each of the following systems of equation there is exactly one solution:
- $x equiv 1 mod m$ and $xequiv 1 mod m$. (In this case $x equiv
1 mod mn$). $y equiv 1 mod m$ and $y equiv -1 mod m$.
$w equiv -1 mod m$ and $wequiv 1mod m$
- $u equiv -1mod m$ and $wequiv -1 mod m$.(this is $u equiv -1
mod mn$).
These are four distinct values $mod mn$.
Now all four of these values have the properties that:
- $x^2 equiv y^2 equiv z^2 equiv u^2 equiv 1 mod m$ and $x^2 equiv y^2 equiv z^2 equiv u^2 equiv 1 mod n$.
By CRT there is exactly one solution $mod mn$ to that:
$x^2 equiv y^2equiv z^2 equiv u^2 equiv 1 mod mn$.
answered Jul 19 at 19:56
fleablood
60.4k22575
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Let $N = mn$ with $mn$ relatively prime and both odd.
Then among the equivalence classes $mod N$:
by CRT for each of the following systems of equation there is exactly one solution:
- $x equiv 1 mod m$ and $xequiv 1 mod m$. (In this case $x equiv
1 mod mn$). $y equiv 1 mod m$ and $y equiv -1 mod m$.
$w equiv -1 mod m$ and $wequiv 1mod m$
- $u equiv -1mod m$ and $wequiv -1 mod m$.(this is $u equiv -1
mod mn$).
These are four distinct values $mod mn$.
Now all four of these values have the properties that:
- $x^2 equiv y^2 equiv z^2 equiv u^2 equiv 1 mod m$ and $x^2 equiv y^2 equiv z^2 equiv u^2 equiv 1 mod n$.
By CRT there is exactly one solution $mod mn$ to that:
$x^2 equiv y^2equiv z^2 equiv u^2 equiv 1 mod mn$.
answered Jul 19 at 19:56
fleablood
60.4k22575
Let $N = mn$ with $mn$ relatively prime and both odd.
Then among the equivalence classes $mod N$:
by CRT for each of the following systems of equation there is exactly one solution:
- $x equiv 1 mod m$ and $xequiv 1 mod m$. (In this case $x equiv
1 mod mn$). $y equiv 1 mod m$ and $y equiv -1 mod m$.
$w equiv -1 mod m$ and $wequiv 1mod m$
- $u equiv -1mod m$ and $wequiv -1 mod m$.(this is $u equiv -1
mod mn$).
These are four distinct values $mod mn$.
Now all four of these values have the properties that:
- $x^2 equiv y^2 equiv z^2 equiv u^2 equiv 1 mod m$ and $x^2 equiv y^2 equiv z^2 equiv u^2 equiv 1 mod n$.
By CRT there is exactly one solution $mod mn$ to that:
$x^2 equiv y^2equiv z^2 equiv u^2 equiv 1 mod mn$.
answered Jul 19 at 19:56
fleablood
60.4k22575
answered Jul 19 at 19:56
fleablood
60.4k22575
answered Jul 19 at 19:56
fleablood
60.4k22575
answered Jul 19 at 19:56
fleablood
60.4k22575
60.4k22575
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%2f2856758%2fchinese-remainder-theorem-four-square-roots-of-1-modulo-n%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
The correct statement is that $N$ should be the product of two (distinct) odd primes
– Lubin
Jul 19 at 15:53
1
@gammatester Sorry, there was a detail I missed: N is not a prime power (edited now)
– Jean-Jacq du Plessis
Jul 19 at 15:55
Good. now you use CRT, to find something that’s like $1$ at one prime, $-1$ at another.
– Lubin
Jul 19 at 15:56
"The correct statement is that N should be the product of two (distinct) odd primes" Actually "N is the product of two relatively prime odd numbers other than one". They don't need to be prime. Just odd, and relatively prime to each other.
– fleablood
Jul 19 at 20:00
And N doesn't need to be odd. It just needs to be the product of two relatively prime numbers larger than $2$.
– fleablood
Jul 19 at 20:03