Mixing
number of square roots of unity modulo a prime power
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Let $pgeq 3$ be a prime number and let $kgeq 1$ be some integer.
Is it always true that if $x^2equiv 1pmodp^k$ then $xequivpm1pmodp^k$ ?
For $k=1$ it is true since $x^2-1inmathbbF_p[x]$ is a degree $2$ polynomial with two distinct roots $-1,1$ and so any other root in $mathbbF_p$ must be one of them.
I know that there exists a primitive root modulo $p^k$.
number-theory primitive-roots
asked Jul 14 at 20:04
user554578
1707
add a comment |Â
up vote
2
down vote
favorite
Let $pgeq 3$ be a prime number and let $kgeq 1$ be some integer.
Is it always true that if $x^2equiv 1pmodp^k$ then $xequivpm1pmodp^k$ ?
For $k=1$ it is true since $x^2-1inmathbbF_p[x]$ is a degree $2$ polynomial with two distinct roots $-1,1$ and so any other root in $mathbbF_p$ must be one of them.
I know that there exists a primitive root modulo $p^k$.
number-theory primitive-roots
asked Jul 14 at 20:04
user554578
1707
1
Then you know that you can write each $xneq 0$ as $g^m$. When is $g^2m = 1$?
– Daniel Fischer♦
Jul 14 at 20:12
when $varphi(p^k)|2m$, so $2m=ellvarphi(p^k)$ and if $ell$ is even then $varphi(p^k)|m$ so $g^mequiv 1pmodp^k$ but what about odd $ell$? @DanielFischer
– user554578
Jul 14 at 20:19
You can restrict your attention to $0 leqslant m < varphi(p^k)$, then $2m < 2varphi(p^k)$ and $varphi(p^k) mid 2m$ if and only if $2m = 0$ or $2m = varphi(p^k)$.
– Daniel Fischer♦
Jul 14 at 20:24
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Let $pgeq 3$ be a prime number and let $kgeq 1$ be some integer.
Is it always true that if $x^2equiv 1pmodp^k$ then $xequivpm1pmodp^k$ ?
For $k=1$ it is true since $x^2-1inmathbbF_p[x]$ is a degree $2$ polynomial with two distinct roots $-1,1$ and so any other root in $mathbbF_p$ must be one of them.
I know that there exists a primitive root modulo $p^k$.
number-theory primitive-roots
asked Jul 14 at 20:04
user554578
1707
Let $pgeq 3$ be a prime number and let $kgeq 1$ be some integer.
Is it always true that if $x^2equiv 1pmodp^k$ then $xequivpm1pmodp^k$ ?
For $k=1$ it is true since $x^2-1inmathbbF_p[x]$ is a degree $2$ polynomial with two distinct roots $-1,1$ and so any other root in $mathbbF_p$ must be one of them.
I know that there exists a primitive root modulo $p^k$.
number-theory primitive-roots
asked Jul 14 at 20:04
user554578
1707
asked Jul 14 at 20:04
user554578
1707
asked Jul 14 at 20:04
user554578
1707
asked Jul 14 at 20:04
user554578
1707
1707
1
Then you know that you can write each $xneq 0$ as $g^m$. When is $g^2m = 1$?
– Daniel Fischer♦
Jul 14 at 20:12
when $varphi(p^k)|2m$, so $2m=ellvarphi(p^k)$ and if $ell$ is even then $varphi(p^k)|m$ so $g^mequiv 1pmodp^k$ but what about odd $ell$? @DanielFischer
– user554578
Jul 14 at 20:19
You can restrict your attention to $0 leqslant m < varphi(p^k)$, then $2m < 2varphi(p^k)$ and $varphi(p^k) mid 2m$ if and only if $2m = 0$ or $2m = varphi(p^k)$.
– Daniel Fischer♦
Jul 14 at 20:24
add a comment |Â
1
Then you know that you can write each $xneq 0$ as $g^m$. When is $g^2m = 1$?
– Daniel Fischer♦
Jul 14 at 20:12
when $varphi(p^k)|2m$, so $2m=ellvarphi(p^k)$ and if $ell$ is even then $varphi(p^k)|m$ so $g^mequiv 1pmodp^k$ but what about odd $ell$? @DanielFischer
– user554578
Jul 14 at 20:19
You can restrict your attention to $0 leqslant m < varphi(p^k)$, then $2m < 2varphi(p^k)$ and $varphi(p^k) mid 2m$ if and only if $2m = 0$ or $2m = varphi(p^k)$.
– Daniel Fischer♦
Jul 14 at 20:24
1
1
Then you know that you can write each $xneq 0$ as $g^m$. When is $g^2m = 1$?
– Daniel Fischer♦
Jul 14 at 20:12
Then you know that you can write each $xneq 0$ as $g^m$. When is $g^2m = 1$?
– Daniel Fischer♦
Jul 14 at 20:12
when $varphi(p^k)|2m$, so $2m=ellvarphi(p^k)$ and if $ell$ is even then $varphi(p^k)|m$ so $g^mequiv 1pmodp^k$ but what about odd $ell$? @DanielFischer
– user554578
Jul 14 at 20:19
when $varphi(p^k)|2m$, so $2m=ellvarphi(p^k)$ and if $ell$ is even then $varphi(p^k)|m$ so $g^mequiv 1pmodp^k$ but what about odd $ell$? @DanielFischer
– user554578
Jul 14 at 20:19
You can restrict your attention to $0 leqslant m < varphi(p^k)$, then $2m < 2varphi(p^k)$ and $varphi(p^k) mid 2m$ if and only if $2m = 0$ or $2m = varphi(p^k)$.
– Daniel Fischer♦
Jul 14 at 20:24
You can restrict your attention to $0 leqslant m < varphi(p^k)$, then $2m < 2varphi(p^k)$ and $varphi(p^k) mid 2m$ if and only if $2m = 0$ or $2m = varphi(p^k)$.
– Daniel Fischer♦
Jul 14 at 20:24
add a comment |Â
4 Answers
4
active
oldest
votes
up vote
1
down vote
accepted
We know that $$p^k mid a^2-1=(a-1)(a+1)$$we prove that it is impossible that $$p mid a-1\p mid a+1$$but this is obvious since$$p mid (a+1)-(a-1)=2$$which is a contradiction for $p>2$ therefore either $pnotmid a-1$ or $pnotmid a+1$ which means that either $p mid a-1$ or $p mid a+1$
edited Jul 14 at 20:22
WimC
23.7k22860
answered Jul 14 at 20:13
Mostafa Ayaz
8,6573630
But this gives us that $aequiv 1pmodp$ or $aequiv -1pmodp$ and not necessarily modulo $p^k$. Ah, you say that it must be that $p|a-1$ xor $p|a+1$ and so $p^k|a-1$ xor $p^k|a+1$ ?
– user554578
Jul 14 at 20:23
No. Since $p^k|(a-1)(a+1)$ and $a-1$ and $a+1$ cannot have both common factor $p$ at least one should be coprime with $p$ and the other one must absorb all the power of $p$ say, $p^k$
– Mostafa Ayaz
Jul 14 at 20:25
Thank you very much!
– user554578
Jul 14 at 20:27
You're welcome!
– Mostafa Ayaz
Jul 14 at 20:28
add a comment |Â
up vote
0
down vote
Another way to say that there exists a primitive root modulo $p^k$ is to say that $U(p^k)$ is cyclic. Since it has even order, it has exactly one subgroup of order $2$: the set of all elements such that $x^2=1$.
answered Jul 14 at 20:31
lhf
156k9160367
add a comment |Â
up vote
0
down vote
Another approach using induction (inspired by Hensel’s lemma). Assume $p neq 2$. For $k=1$ the statement holds. Now if $k > 1$ and $a^2equiv 1 pmodp^k$ then also $a^2equiv 1 pmod p^k-1$. So by induction $a equiv pm 1 pmodp^k-1$, that is, $a = pm 1 + m p^k-1$ for some integer $m$. Then $$1 equiv a^2 = 1 pm 2 m p^k-1 + m^2 p^2k-2equiv 1 pm 2 m p^k-1 pmodp^k.$$ This means (since $p neq 2$) that $p mid m$. Then $a = pm 1 + m p^k-1equiv pm 1 pmodp^k$.
answered Jul 14 at 20:56
WimC
23.7k22860
add a comment |Â
up vote
0
down vote
We know that $1$ and $-1$ are roots of $1bmod p^k$.
Let $g$ be a primitive root $bmod p^k$ and $m:=phi(p^k)$ be its order. Then considering $(g^i)^2$ with $iin [1..m]$ we note that only $i=m/2$ and $i=m$ give $(g^i)^2equiv 1 bmod p^k$. Thus there are only two roots of $1 bmod p^k$.
answered Jul 14 at 21:59
Joffan
31.9k43169
add a comment |Â
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
We know that $$p^k mid a^2-1=(a-1)(a+1)$$we prove that it is impossible that $$p mid a-1\p mid a+1$$but this is obvious since$$p mid (a+1)-(a-1)=2$$which is a contradiction for $p>2$ therefore either $pnotmid a-1$ or $pnotmid a+1$ which means that either $p mid a-1$ or $p mid a+1$
edited Jul 14 at 20:22
WimC
23.7k22860
answered Jul 14 at 20:13
Mostafa Ayaz
8,6573630
But this gives us that $aequiv 1pmodp$ or $aequiv -1pmodp$ and not necessarily modulo $p^k$. Ah, you say that it must be that $p|a-1$ xor $p|a+1$ and so $p^k|a-1$ xor $p^k|a+1$ ?
– user554578
Jul 14 at 20:23
No. Since $p^k|(a-1)(a+1)$ and $a-1$ and $a+1$ cannot have both common factor $p$ at least one should be coprime with $p$ and the other one must absorb all the power of $p$ say, $p^k$
– Mostafa Ayaz
Jul 14 at 20:25
Thank you very much!
– user554578
Jul 14 at 20:27
You're welcome!
– Mostafa Ayaz
Jul 14 at 20:28
add a comment |Â
up vote
1
down vote
accepted
We know that $$p^k mid a^2-1=(a-1)(a+1)$$we prove that it is impossible that $$p mid a-1\p mid a+1$$but this is obvious since$$p mid (a+1)-(a-1)=2$$which is a contradiction for $p>2$ therefore either $pnotmid a-1$ or $pnotmid a+1$ which means that either $p mid a-1$ or $p mid a+1$
edited Jul 14 at 20:22
WimC
23.7k22860
answered Jul 14 at 20:13
Mostafa Ayaz
8,6573630
But this gives us that $aequiv 1pmodp$ or $aequiv -1pmodp$ and not necessarily modulo $p^k$. Ah, you say that it must be that $p|a-1$ xor $p|a+1$ and so $p^k|a-1$ xor $p^k|a+1$ ?
– user554578
Jul 14 at 20:23
No. Since $p^k|(a-1)(a+1)$ and $a-1$ and $a+1$ cannot have both common factor $p$ at least one should be coprime with $p$ and the other one must absorb all the power of $p$ say, $p^k$
– Mostafa Ayaz
Jul 14 at 20:25
Thank you very much!
– user554578
Jul 14 at 20:27
You're welcome!
– Mostafa Ayaz
Jul 14 at 20:28
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
We know that $$p^k mid a^2-1=(a-1)(a+1)$$we prove that it is impossible that $$p mid a-1\p mid a+1$$but this is obvious since$$p mid (a+1)-(a-1)=2$$which is a contradiction for $p>2$ therefore either $pnotmid a-1$ or $pnotmid a+1$ which means that either $p mid a-1$ or $p mid a+1$
edited Jul 14 at 20:22
WimC
23.7k22860
answered Jul 14 at 20:13
Mostafa Ayaz
8,6573630
We know that $$p^k mid a^2-1=(a-1)(a+1)$$we prove that it is impossible that $$p mid a-1\p mid a+1$$but this is obvious since$$p mid (a+1)-(a-1)=2$$which is a contradiction for $p>2$ therefore either $pnotmid a-1$ or $pnotmid a+1$ which means that either $p mid a-1$ or $p mid a+1$
edited Jul 14 at 20:22
WimC
23.7k22860
answered Jul 14 at 20:13
Mostafa Ayaz
8,6573630
edited Jul 14 at 20:22
WimC
23.7k22860
edited Jul 14 at 20:22
WimC
23.7k22860
edited Jul 14 at 20:22
WimC
23.7k22860
23.7k22860
answered Jul 14 at 20:13
Mostafa Ayaz
8,6573630
answered Jul 14 at 20:13
Mostafa Ayaz
8,6573630
answered Jul 14 at 20:13
Mostafa Ayaz
8,6573630
8,6573630
But this gives us that $aequiv 1pmodp$ or $aequiv -1pmodp$ and not necessarily modulo $p^k$. Ah, you say that it must be that $p|a-1$ xor $p|a+1$ and so $p^k|a-1$ xor $p^k|a+1$ ?
– user554578
Jul 14 at 20:23
No. Since $p^k|(a-1)(a+1)$ and $a-1$ and $a+1$ cannot have both common factor $p$ at least one should be coprime with $p$ and the other one must absorb all the power of $p$ say, $p^k$
– Mostafa Ayaz
Jul 14 at 20:25
Thank you very much!
– user554578
Jul 14 at 20:27
You're welcome!
– Mostafa Ayaz
Jul 14 at 20:28
add a comment |Â
But this gives us that $aequiv 1pmodp$ or $aequiv -1pmodp$ and not necessarily modulo $p^k$. Ah, you say that it must be that $p|a-1$ xor $p|a+1$ and so $p^k|a-1$ xor $p^k|a+1$ ?
– user554578
Jul 14 at 20:23
No. Since $p^k|(a-1)(a+1)$ and $a-1$ and $a+1$ cannot have both common factor $p$ at least one should be coprime with $p$ and the other one must absorb all the power of $p$ say, $p^k$
– Mostafa Ayaz
Jul 14 at 20:25
Thank you very much!
– user554578
Jul 14 at 20:27
You're welcome!
– Mostafa Ayaz
Jul 14 at 20:28
But this gives us that $aequiv 1pmodp$ or $aequiv -1pmodp$ and not necessarily modulo $p^k$. Ah, you say that it must be that $p|a-1$ xor $p|a+1$ and so $p^k|a-1$ xor $p^k|a+1$ ?
– user554578
Jul 14 at 20:23
But this gives us that $aequiv 1pmodp$ or $aequiv -1pmodp$ and not necessarily modulo $p^k$. Ah, you say that it must be that $p|a-1$ xor $p|a+1$ and so $p^k|a-1$ xor $p^k|a+1$ ?
– user554578
Jul 14 at 20:23
No. Since $p^k|(a-1)(a+1)$ and $a-1$ and $a+1$ cannot have both common factor $p$ at least one should be coprime with $p$ and the other one must absorb all the power of $p$ say, $p^k$
– Mostafa Ayaz
Jul 14 at 20:25
No. Since $p^k|(a-1)(a+1)$ and $a-1$ and $a+1$ cannot have both common factor $p$ at least one should be coprime with $p$ and the other one must absorb all the power of $p$ say, $p^k$
– Mostafa Ayaz
Jul 14 at 20:25
Thank you very much!
– user554578
Jul 14 at 20:27
Thank you very much!
– user554578
Jul 14 at 20:27
You're welcome!
– Mostafa Ayaz
Jul 14 at 20:28
You're welcome!
– Mostafa Ayaz
Jul 14 at 20:28
add a comment |Â
up vote
0
down vote
Another way to say that there exists a primitive root modulo $p^k$ is to say that $U(p^k)$ is cyclic. Since it has even order, it has exactly one subgroup of order $2$: the set of all elements such that $x^2=1$.
answered Jul 14 at 20:31
lhf
156k9160367
add a comment |Â
up vote
0
down vote
Another way to say that there exists a primitive root modulo $p^k$ is to say that $U(p^k)$ is cyclic. Since it has even order, it has exactly one subgroup of order $2$: the set of all elements such that $x^2=1$.
answered Jul 14 at 20:31
lhf
156k9160367
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Another way to say that there exists a primitive root modulo $p^k$ is to say that $U(p^k)$ is cyclic. Since it has even order, it has exactly one subgroup of order $2$: the set of all elements such that $x^2=1$.
answered Jul 14 at 20:31
lhf
156k9160367
Another way to say that there exists a primitive root modulo $p^k$ is to say that $U(p^k)$ is cyclic. Since it has even order, it has exactly one subgroup of order $2$: the set of all elements such that $x^2=1$.
answered Jul 14 at 20:31
lhf
156k9160367
answered Jul 14 at 20:31
lhf
156k9160367
answered Jul 14 at 20:31
lhf
156k9160367
answered Jul 14 at 20:31
lhf
156k9160367
156k9160367
add a comment |Â
add a comment |Â
up vote
0
down vote
Another approach using induction (inspired by Hensel’s lemma). Assume $p neq 2$. For $k=1$ the statement holds. Now if $k > 1$ and $a^2equiv 1 pmodp^k$ then also $a^2equiv 1 pmod p^k-1$. So by induction $a equiv pm 1 pmodp^k-1$, that is, $a = pm 1 + m p^k-1$ for some integer $m$. Then $$1 equiv a^2 = 1 pm 2 m p^k-1 + m^2 p^2k-2equiv 1 pm 2 m p^k-1 pmodp^k.$$ This means (since $p neq 2$) that $p mid m$. Then $a = pm 1 + m p^k-1equiv pm 1 pmodp^k$.
answered Jul 14 at 20:56
WimC
23.7k22860
add a comment |Â
up vote
0
down vote
Another approach using induction (inspired by Hensel’s lemma). Assume $p neq 2$. For $k=1$ the statement holds. Now if $k > 1$ and $a^2equiv 1 pmodp^k$ then also $a^2equiv 1 pmod p^k-1$. So by induction $a equiv pm 1 pmodp^k-1$, that is, $a = pm 1 + m p^k-1$ for some integer $m$. Then $$1 equiv a^2 = 1 pm 2 m p^k-1 + m^2 p^2k-2equiv 1 pm 2 m p^k-1 pmodp^k.$$ This means (since $p neq 2$) that $p mid m$. Then $a = pm 1 + m p^k-1equiv pm 1 pmodp^k$.
answered Jul 14 at 20:56
WimC
23.7k22860
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Another approach using induction (inspired by Hensel’s lemma). Assume $p neq 2$. For $k=1$ the statement holds. Now if $k > 1$ and $a^2equiv 1 pmodp^k$ then also $a^2equiv 1 pmod p^k-1$. So by induction $a equiv pm 1 pmodp^k-1$, that is, $a = pm 1 + m p^k-1$ for some integer $m$. Then $$1 equiv a^2 = 1 pm 2 m p^k-1 + m^2 p^2k-2equiv 1 pm 2 m p^k-1 pmodp^k.$$ This means (since $p neq 2$) that $p mid m$. Then $a = pm 1 + m p^k-1equiv pm 1 pmodp^k$.
answered Jul 14 at 20:56
WimC
23.7k22860
Another approach using induction (inspired by Hensel’s lemma). Assume $p neq 2$. For $k=1$ the statement holds. Now if $k > 1$ and $a^2equiv 1 pmodp^k$ then also $a^2equiv 1 pmod p^k-1$. So by induction $a equiv pm 1 pmodp^k-1$, that is, $a = pm 1 + m p^k-1$ for some integer $m$. Then $$1 equiv a^2 = 1 pm 2 m p^k-1 + m^2 p^2k-2equiv 1 pm 2 m p^k-1 pmodp^k.$$ This means (since $p neq 2$) that $p mid m$. Then $a = pm 1 + m p^k-1equiv pm 1 pmodp^k$.
answered Jul 14 at 20:56
WimC
23.7k22860
answered Jul 14 at 20:56
WimC
23.7k22860
answered Jul 14 at 20:56
WimC
23.7k22860
answered Jul 14 at 20:56
WimC
23.7k22860
23.7k22860
add a comment |Â
add a comment |Â
up vote
0
down vote
We know that $1$ and $-1$ are roots of $1bmod p^k$.
Let $g$ be a primitive root $bmod p^k$ and $m:=phi(p^k)$ be its order. Then considering $(g^i)^2$ with $iin [1..m]$ we note that only $i=m/2$ and $i=m$ give $(g^i)^2equiv 1 bmod p^k$. Thus there are only two roots of $1 bmod p^k$.
answered Jul 14 at 21:59
Joffan
31.9k43169
add a comment |Â
up vote
0
down vote
We know that $1$ and $-1$ are roots of $1bmod p^k$.
Let $g$ be a primitive root $bmod p^k$ and $m:=phi(p^k)$ be its order. Then considering $(g^i)^2$ with $iin [1..m]$ we note that only $i=m/2$ and $i=m$ give $(g^i)^2equiv 1 bmod p^k$. Thus there are only two roots of $1 bmod p^k$.
answered Jul 14 at 21:59
Joffan
31.9k43169
add a comment |Â
up vote
0
down vote
up vote
0
down vote
We know that $1$ and $-1$ are roots of $1bmod p^k$.
Let $g$ be a primitive root $bmod p^k$ and $m:=phi(p^k)$ be its order. Then considering $(g^i)^2$ with $iin [1..m]$ we note that only $i=m/2$ and $i=m$ give $(g^i)^2equiv 1 bmod p^k$. Thus there are only two roots of $1 bmod p^k$.
answered Jul 14 at 21:59
Joffan
31.9k43169
We know that $1$ and $-1$ are roots of $1bmod p^k$.
Let $g$ be a primitive root $bmod p^k$ and $m:=phi(p^k)$ be its order. Then considering $(g^i)^2$ with $iin [1..m]$ we note that only $i=m/2$ and $i=m$ give $(g^i)^2equiv 1 bmod p^k$. Thus there are only two roots of $1 bmod p^k$.
answered Jul 14 at 21:59
Joffan
31.9k43169
answered Jul 14 at 21:59
Joffan
31.9k43169
answered Jul 14 at 21:59
Joffan
31.9k43169
answered Jul 14 at 21:59
Joffan
31.9k43169
31.9k43169
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%2f2851910%2fnumber-of-square-roots-of-unity-modulo-a-prime-power%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
1
Then you know that you can write each $xneq 0$ as $g^m$. When is $g^2m = 1$?
– Daniel Fischer♦
Jul 14 at 20:12
when $varphi(p^k)|2m$, so $2m=ellvarphi(p^k)$ and if $ell$ is even then $varphi(p^k)|m$ so $g^mequiv 1pmodp^k$ but what about odd $ell$? @DanielFischer
– user554578
Jul 14 at 20:19
You can restrict your attention to $0 leqslant m < varphi(p^k)$, then $2m < 2varphi(p^k)$ and $varphi(p^k) mid 2m$ if and only if $2m = 0$ or $2m = varphi(p^k)$.
– Daniel Fischer♦
Jul 14 at 20:24