Mixing
Prove that $left|left 1leq xleq p^2 : p^2midleft(x^p-1-1right)right right|=p-1$
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Let $p$ be a prime number and to simplify things lets denote
$$
A=left 1leq xleq p^2 : p^2midleft(x^p-1-1right)right
$$
and we have to show that $left|Aright|=p-1$.
For every $xin A$ we know that $p^2midleft(x^p-1-1right)$
which means $x^p-1-1=kp$ for some $kinmathbbZ$, and as this is
a polynomial of degree $p-1$ it has at most $p-1$ solutions. Therefore $left|Aright|leq p-1$.
How can we show there are exactly $p-1$ solutions in $A$?
elementary-number-theory prime-numbers
asked Jul 15 at 7:06
Jon
500413
add a comment |Â
up vote
1
down vote
favorite
Let $p$ be a prime number and to simplify things lets denote
$$
A=left 1leq xleq p^2 : p^2midleft(x^p-1-1right)right
$$
and we have to show that $left|Aright|=p-1$.
For every $xin A$ we know that $p^2midleft(x^p-1-1right)$
which means $x^p-1-1=kp$ for some $kinmathbbZ$, and as this is
a polynomial of degree $p-1$ it has at most $p-1$ solutions. Therefore $left|Aright|leq p-1$.
How can we show there are exactly $p-1$ solutions in $A$?
elementary-number-theory prime-numbers
asked Jul 15 at 7:06
Jon
500413
Have you covered the fact that the multiplicative group $BbbZ_p^2^*$ is cyclic of order $p(p-1)$? Probably not (because the question would then be formulated differently), but I'm checking because some answerers may want to use that result :-)
– Jyrki Lahtonen
Jul 15 at 7:36
@JyrkiLahtonen We have covered cyclic groups and I know $BbbZ_p^2^*$ is cyclic of order $p(p-1)$
– Jon
Jul 15 at 7:44
In a cyclic group of order $n$ the equation $x^d=1$ has exactly $gcd(n,d)$ solutions.
– Jyrki Lahtonen
Jul 15 at 7:49
@JyrkiLahtonen Where can i see a proof of that?
– Jon
Jul 15 at 7:52
I would expect texts covering cyclic groups to cover that also. Sketch: without loss of generality we can assume that the group is the additive group $BbbZ_n$. A coset $overlinea$ satisfies $doverlinea=overline0$ if and only if $a$ is a multiple of $n/d$. There are $d$ choices of $a$ in the range $0le a<n$.
– Jyrki Lahtonen
Jul 15 at 7:57
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Let $p$ be a prime number and to simplify things lets denote
$$
A=left 1leq xleq p^2 : p^2midleft(x^p-1-1right)right
$$
and we have to show that $left|Aright|=p-1$.
For every $xin A$ we know that $p^2midleft(x^p-1-1right)$
which means $x^p-1-1=kp$ for some $kinmathbbZ$, and as this is
a polynomial of degree $p-1$ it has at most $p-1$ solutions. Therefore $left|Aright|leq p-1$.
How can we show there are exactly $p-1$ solutions in $A$?
elementary-number-theory prime-numbers
asked Jul 15 at 7:06
Jon
500413
Let $p$ be a prime number and to simplify things lets denote
$$
A=left 1leq xleq p^2 : p^2midleft(x^p-1-1right)right
$$
and we have to show that $left|Aright|=p-1$.
For every $xin A$ we know that $p^2midleft(x^p-1-1right)$
which means $x^p-1-1=kp$ for some $kinmathbbZ$, and as this is
a polynomial of degree $p-1$ it has at most $p-1$ solutions. Therefore $left|Aright|leq p-1$.
How can we show there are exactly $p-1$ solutions in $A$?
elementary-number-theory prime-numbers
asked Jul 15 at 7:06
Jon
500413
asked Jul 15 at 7:06
Jon
500413
asked Jul 15 at 7:06
Jon
500413
asked Jul 15 at 7:06
Jon
500413
500413
Have you covered the fact that the multiplicative group $BbbZ_p^2^*$ is cyclic of order $p(p-1)$? Probably not (because the question would then be formulated differently), but I'm checking because some answerers may want to use that result :-)
– Jyrki Lahtonen
Jul 15 at 7:36
@JyrkiLahtonen We have covered cyclic groups and I know $BbbZ_p^2^*$ is cyclic of order $p(p-1)$
– Jon
Jul 15 at 7:44
In a cyclic group of order $n$ the equation $x^d=1$ has exactly $gcd(n,d)$ solutions.
– Jyrki Lahtonen
Jul 15 at 7:49
@JyrkiLahtonen Where can i see a proof of that?
– Jon
Jul 15 at 7:52
I would expect texts covering cyclic groups to cover that also. Sketch: without loss of generality we can assume that the group is the additive group $BbbZ_n$. A coset $overlinea$ satisfies $doverlinea=overline0$ if and only if $a$ is a multiple of $n/d$. There are $d$ choices of $a$ in the range $0le a<n$.
– Jyrki Lahtonen
Jul 15 at 7:57
add a comment |Â
Have you covered the fact that the multiplicative group $BbbZ_p^2^*$ is cyclic of order $p(p-1)$? Probably not (because the question would then be formulated differently), but I'm checking because some answerers may want to use that result :-)
– Jyrki Lahtonen
Jul 15 at 7:36
@JyrkiLahtonen We have covered cyclic groups and I know $BbbZ_p^2^*$ is cyclic of order $p(p-1)$
– Jon
Jul 15 at 7:44
In a cyclic group of order $n$ the equation $x^d=1$ has exactly $gcd(n,d)$ solutions.
– Jyrki Lahtonen
Jul 15 at 7:49
@JyrkiLahtonen Where can i see a proof of that?
– Jon
Jul 15 at 7:52
I would expect texts covering cyclic groups to cover that also. Sketch: without loss of generality we can assume that the group is the additive group $BbbZ_n$. A coset $overlinea$ satisfies $doverlinea=overline0$ if and only if $a$ is a multiple of $n/d$. There are $d$ choices of $a$ in the range $0le a<n$.
– Jyrki Lahtonen
Jul 15 at 7:57
Have you covered the fact that the multiplicative group $BbbZ_p^2^*$ is cyclic of order $p(p-1)$? Probably not (because the question would then be formulated differently), but I'm checking because some answerers may want to use that result :-)
– Jyrki Lahtonen
Jul 15 at 7:36
Have you covered the fact that the multiplicative group $BbbZ_p^2^*$ is cyclic of order $p(p-1)$? Probably not (because the question would then be formulated differently), but I'm checking because some answerers may want to use that result :-)
– Jyrki Lahtonen
Jul 15 at 7:36
@JyrkiLahtonen We have covered cyclic groups and I know $BbbZ_p^2^*$ is cyclic of order $p(p-1)$
– Jon
Jul 15 at 7:44
@JyrkiLahtonen We have covered cyclic groups and I know $BbbZ_p^2^*$ is cyclic of order $p(p-1)$
– Jon
Jul 15 at 7:44
In a cyclic group of order $n$ the equation $x^d=1$ has exactly $gcd(n,d)$ solutions.
– Jyrki Lahtonen
Jul 15 at 7:49
In a cyclic group of order $n$ the equation $x^d=1$ has exactly $gcd(n,d)$ solutions.
– Jyrki Lahtonen
Jul 15 at 7:49
@JyrkiLahtonen Where can i see a proof of that?
– Jon
Jul 15 at 7:52
@JyrkiLahtonen Where can i see a proof of that?
– Jon
Jul 15 at 7:52
I would expect texts covering cyclic groups to cover that also. Sketch: without loss of generality we can assume that the group is the additive group $BbbZ_n$. A coset $overlinea$ satisfies $doverlinea=overline0$ if and only if $a$ is a multiple of $n/d$. There are $d$ choices of $a$ in the range $0le a<n$.
– Jyrki Lahtonen
Jul 15 at 7:57
I would expect texts covering cyclic groups to cover that also. Sketch: without loss of generality we can assume that the group is the additive group $BbbZ_n$. A coset $overlinea$ satisfies $doverlinea=overline0$ if and only if $a$ is a multiple of $n/d$. There are $d$ choices of $a$ in the range $0le a<n$.
– Jyrki Lahtonen
Jul 15 at 7:57
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
Let's fix an integer $a$ in ther range $1le a<p$. By Little Fermat we know that $a^p-1equiv1pmod p$. We use this to study the number of solutions $xin A$ such that $xequiv apmod p$.
So let $x=a+kp$ for some $k$, $0le k<p$. The binomial theorem tells us that
$$
beginaligned
x^p-1&=(a+kp)^p-1\
&=a^p-1+binom p-11a^p-2kp+sum_i=2^p-1binom p-1ia^p-1-ik^ip^i.
endaligned
$$
Here all the terms in the last sum are divisible by $p^2$, so we get that
$$
(a+kp)^p-1equiv a^p-1+(p-1)a^p-2kppmodp^2.qquad(*)
$$
Little Fermat tells us that $a^p-1=1+s_ap$ for some integer $s_a$. Therefore $(*)$ tells us that $(a+kp)^p-1$ is congruent to $1$ modulo $p^2$ if and only if
$$s_a+(p-1)a^p-2kequiv0pmod p.qquad(**)$$
Here the coefficient $(p-1)a^p-2$ is not divisible by $p$ so by the basic theory of linear congruences $(**)$ is satisfied for exactly one choice of $k$ in the range $0le k<p$.
The claim follows from this because $pmid ximplies x^p-1notequiv1pmod p.$
This is a standard fact covered in most textbooks, so I should not want any rep from this. Answering because my search-fu is weak today.
– Jyrki Lahtonen
Jul 15 at 7:52
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
Let's fix an integer $a$ in ther range $1le a<p$. By Little Fermat we know that $a^p-1equiv1pmod p$. We use this to study the number of solutions $xin A$ such that $xequiv apmod p$.
So let $x=a+kp$ for some $k$, $0le k<p$. The binomial theorem tells us that
$$
beginaligned
x^p-1&=(a+kp)^p-1\
&=a^p-1+binom p-11a^p-2kp+sum_i=2^p-1binom p-1ia^p-1-ik^ip^i.
endaligned
$$
Here all the terms in the last sum are divisible by $p^2$, so we get that
$$
(a+kp)^p-1equiv a^p-1+(p-1)a^p-2kppmodp^2.qquad(*)
$$
Little Fermat tells us that $a^p-1=1+s_ap$ for some integer $s_a$. Therefore $(*)$ tells us that $(a+kp)^p-1$ is congruent to $1$ modulo $p^2$ if and only if
$$s_a+(p-1)a^p-2kequiv0pmod p.qquad(**)$$
Here the coefficient $(p-1)a^p-2$ is not divisible by $p$ so by the basic theory of linear congruences $(**)$ is satisfied for exactly one choice of $k$ in the range $0le k<p$.
The claim follows from this because $pmid ximplies x^p-1notequiv1pmod p.$
This is a standard fact covered in most textbooks, so I should not want any rep from this. Answering because my search-fu is weak today.
– Jyrki Lahtonen
Jul 15 at 7:52
add a comment |Â
up vote
2
down vote
Let's fix an integer $a$ in ther range $1le a<p$. By Little Fermat we know that $a^p-1equiv1pmod p$. We use this to study the number of solutions $xin A$ such that $xequiv apmod p$.
So let $x=a+kp$ for some $k$, $0le k<p$. The binomial theorem tells us that
$$
beginaligned
x^p-1&=(a+kp)^p-1\
&=a^p-1+binom p-11a^p-2kp+sum_i=2^p-1binom p-1ia^p-1-ik^ip^i.
endaligned
$$
Here all the terms in the last sum are divisible by $p^2$, so we get that
$$
(a+kp)^p-1equiv a^p-1+(p-1)a^p-2kppmodp^2.qquad(*)
$$
Little Fermat tells us that $a^p-1=1+s_ap$ for some integer $s_a$. Therefore $(*)$ tells us that $(a+kp)^p-1$ is congruent to $1$ modulo $p^2$ if and only if
$$s_a+(p-1)a^p-2kequiv0pmod p.qquad(**)$$
Here the coefficient $(p-1)a^p-2$ is not divisible by $p$ so by the basic theory of linear congruences $(**)$ is satisfied for exactly one choice of $k$ in the range $0le k<p$.
The claim follows from this because $pmid ximplies x^p-1notequiv1pmod p.$
This is a standard fact covered in most textbooks, so I should not want any rep from this. Answering because my search-fu is weak today.
– Jyrki Lahtonen
Jul 15 at 7:52
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Let's fix an integer $a$ in ther range $1le a<p$. By Little Fermat we know that $a^p-1equiv1pmod p$. We use this to study the number of solutions $xin A$ such that $xequiv apmod p$.
So let $x=a+kp$ for some $k$, $0le k<p$. The binomial theorem tells us that
$$
beginaligned
x^p-1&=(a+kp)^p-1\
&=a^p-1+binom p-11a^p-2kp+sum_i=2^p-1binom p-1ia^p-1-ik^ip^i.
endaligned
$$
Here all the terms in the last sum are divisible by $p^2$, so we get that
$$
(a+kp)^p-1equiv a^p-1+(p-1)a^p-2kppmodp^2.qquad(*)
$$
Little Fermat tells us that $a^p-1=1+s_ap$ for some integer $s_a$. Therefore $(*)$ tells us that $(a+kp)^p-1$ is congruent to $1$ modulo $p^2$ if and only if
$$s_a+(p-1)a^p-2kequiv0pmod p.qquad(**)$$
Here the coefficient $(p-1)a^p-2$ is not divisible by $p$ so by the basic theory of linear congruences $(**)$ is satisfied for exactly one choice of $k$ in the range $0le k<p$.
The claim follows from this because $pmid ximplies x^p-1notequiv1pmod p.$
Let's fix an integer $a$ in ther range $1le a<p$. By Little Fermat we know that $a^p-1equiv1pmod p$. We use this to study the number of solutions $xin A$ such that $xequiv apmod p$.
So let $x=a+kp$ for some $k$, $0le k<p$. The binomial theorem tells us that
$$
beginaligned
x^p-1&=(a+kp)^p-1\
&=a^p-1+binom p-11a^p-2kp+sum_i=2^p-1binom p-1ia^p-1-ik^ip^i.
endaligned
$$
Here all the terms in the last sum are divisible by $p^2$, so we get that
$$
(a+kp)^p-1equiv a^p-1+(p-1)a^p-2kppmodp^2.qquad(*)
$$
Little Fermat tells us that $a^p-1=1+s_ap$ for some integer $s_a$. Therefore $(*)$ tells us that $(a+kp)^p-1$ is congruent to $1$ modulo $p^2$ if and only if
$$s_a+(p-1)a^p-2kequiv0pmod p.qquad(**)$$
Here the coefficient $(p-1)a^p-2$ is not divisible by $p$ so by the basic theory of linear congruences $(**)$ is satisfied for exactly one choice of $k$ in the range $0le k<p$.
The claim follows from this because $pmid ximplies x^p-1notequiv1pmod p.$
answered Jul 15 at 7:49
community wiki
Jyrki Lahtonen
This is a standard fact covered in most textbooks, so I should not want any rep from this. Answering because my search-fu is weak today.
– Jyrki Lahtonen
Jul 15 at 7:52
add a comment |Â
This is a standard fact covered in most textbooks, so I should not want any rep from this. Answering because my search-fu is weak today.
– Jyrki Lahtonen
Jul 15 at 7:52
This is a standard fact covered in most textbooks, so I should not want any rep from this. Answering because my search-fu is weak today.
– Jyrki Lahtonen
Jul 15 at 7:52
This is a standard fact covered in most textbooks, so I should not want any rep from this. Answering because my search-fu is weak today.
– Jyrki Lahtonen
Jul 15 at 7:52
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%2f2852257%2fprove-that-left-left-1-leq-x-leq-p2-p2-mid-leftxp-1-1-right%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
Have you covered the fact that the multiplicative group $BbbZ_p^2^*$ is cyclic of order $p(p-1)$? Probably not (because the question would then be formulated differently), but I'm checking because some answerers may want to use that result :-)
– Jyrki Lahtonen
Jul 15 at 7:36
@JyrkiLahtonen We have covered cyclic groups and I know $BbbZ_p^2^*$ is cyclic of order $p(p-1)$
– Jon
Jul 15 at 7:44
In a cyclic group of order $n$ the equation $x^d=1$ has exactly $gcd(n,d)$ solutions.
– Jyrki Lahtonen
Jul 15 at 7:49
@JyrkiLahtonen Where can i see a proof of that?
– Jon
Jul 15 at 7:52
I would expect texts covering cyclic groups to cover that also. Sketch: without loss of generality we can assume that the group is the additive group $BbbZ_n$. A coset $overlinea$ satisfies $doverlinea=overline0$ if and only if $a$ is a multiple of $n/d$. There are $d$ choices of $a$ in the range $0le a<n$.
– Jyrki Lahtonen
Jul 15 at 7:57