Mixing
![$langle 3 rangle$ in $textbfZ[omega]$ ramifies, not splits, right?](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZCTB4-bb-s-32SAm6ytjzFOU06cH9o8q-a_wq_UnH6lcd8hvws23CmBWHM6g256LzTX9yK1EiCCzTC1NSgtxlNk_J9hdr9bA3tD0Nqntbl521j4bLAm_uXPANuWLBhcCKTKzns2gaUodx/s72-c/1.jpg)
Number of solutions related to fermat's last theorem
Clash Royale CLAN TAG#URR8PPP
up vote
-1
down vote
favorite
Can anyone tell me how will we calculate number of solutions of
$x^k + y^k - z^k equiv 0 mod p$
And $0<x,y,z<p$
$1le p le10^6 $
$1le k le 10^18$
It is related to fermat's last theorem somehow
For eg:-
$P=5$ and $K=4$ has $2$ solutions
For $k=1~x,y,z=1,1,2$
For $k=2$ no soln
For $k=3~x,y,z=1,3,2$
For $k=4$ no soln
combinatorics
asked Jul 22 at 20:02
dank uploader
13
add a comment |Â
up vote
-1
down vote
favorite
Can anyone tell me how will we calculate number of solutions of
$x^k + y^k - z^k equiv 0 mod p$
And $0<x,y,z<p$
$1le p le10^6 $
$1le k le 10^18$
It is related to fermat's last theorem somehow
For eg:-
$P=5$ and $K=4$ has $2$ solutions
For $k=1~x,y,z=1,1,2$
For $k=2$ no soln
For $k=3~x,y,z=1,3,2$
For $k=4$ no soln
combinatorics
asked Jul 22 at 20:02
dank uploader
13
Please use MathJax to format your questions
– saulspatz
Jul 22 at 20:06
Am I right in assuming that $p$ is prime? Which programming contest is this from?
– Hagen von Eitzen
Jul 22 at 20:08
@HagenvonEitzen yepp p is prime ques is from hackerearth july circuits
– dank uploader
Jul 22 at 20:18
Perhaps more closely related to Fermat's little theorem.
– saulspatz
Jul 22 at 20:35
add a comment |Â
up vote
-1
down vote
favorite
up vote
-1
down vote
favorite
Can anyone tell me how will we calculate number of solutions of
$x^k + y^k - z^k equiv 0 mod p$
And $0<x,y,z<p$
$1le p le10^6 $
$1le k le 10^18$
It is related to fermat's last theorem somehow
For eg:-
$P=5$ and $K=4$ has $2$ solutions
For $k=1~x,y,z=1,1,2$
For $k=2$ no soln
For $k=3~x,y,z=1,3,2$
For $k=4$ no soln
combinatorics
asked Jul 22 at 20:02
dank uploader
13
Can anyone tell me how will we calculate number of solutions of
$x^k + y^k - z^k equiv 0 mod p$
And $0<x,y,z<p$
$1le p le10^6 $
$1le k le 10^18$
It is related to fermat's last theorem somehow
For eg:-
$P=5$ and $K=4$ has $2$ solutions
For $k=1~x,y,z=1,1,2$
For $k=2$ no soln
For $k=3~x,y,z=1,3,2$
For $k=4$ no soln
combinatorics
asked Jul 22 at 20:02
dank uploader
13
edited Jul 22 at 20:19
asked Jul 22 at 20:02
dank uploader
13
asked Jul 22 at 20:02
dank uploader
13
asked Jul 22 at 20:02
dank uploader
13
13
Please use MathJax to format your questions
– saulspatz
Jul 22 at 20:06
Am I right in assuming that $p$ is prime? Which programming contest is this from?
– Hagen von Eitzen
Jul 22 at 20:08
@HagenvonEitzen yepp p is prime ques is from hackerearth july circuits
– dank uploader
Jul 22 at 20:18
Perhaps more closely related to Fermat's little theorem.
– saulspatz
Jul 22 at 20:35
add a comment |Â
Please use MathJax to format your questions
– saulspatz
Jul 22 at 20:06
Am I right in assuming that $p$ is prime? Which programming contest is this from?
– Hagen von Eitzen
Jul 22 at 20:08
@HagenvonEitzen yepp p is prime ques is from hackerearth july circuits
– dank uploader
Jul 22 at 20:18
Perhaps more closely related to Fermat's little theorem.
– saulspatz
Jul 22 at 20:35
Please use MathJax to format your questions
– saulspatz
Jul 22 at 20:06
Please use MathJax to format your questions
– saulspatz
Jul 22 at 20:06
Am I right in assuming that $p$ is prime? Which programming contest is this from?
– Hagen von Eitzen
Jul 22 at 20:08
Am I right in assuming that $p$ is prime? Which programming contest is this from?
– Hagen von Eitzen
Jul 22 at 20:08
@HagenvonEitzen yepp p is prime ques is from hackerearth july circuits
– dank uploader
Jul 22 at 20:18
@HagenvonEitzen yepp p is prime ques is from hackerearth july circuits
– dank uploader
Jul 22 at 20:18
Perhaps more closely related to Fermat's little theorem.
– saulspatz
Jul 22 at 20:35
Perhaps more closely related to Fermat's little theorem.
– saulspatz
Jul 22 at 20:35
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
0
down vote
accepted
One can reduce the problem a lot:
By Fermat's little theorem, $a^p-1equiv 1pmod p$ for all $anotequiv 0pmod p$. It follows that a solution for $k$ exists iff a solution for $kbmodp-1$ exists, i.e., we need only check $0le k<p-1$. In fact, as taking inverses $bmod p$ is a bijection, a solution f $k$ exists iff a solution for $p-1-k$ exist, i.e., we need only check $0le klefracp-12$. For small $p$, we can thus simply loop over all possible values and check. We immediately get that there is no solution for $k=0$ (as $1+1notequiv 1pmod p$): We also immediately get that $(1,1,2)$ is a solutions for $k=1$ (except when $p=2$), and $(3,4,5)$ is a solution for $k=2$ at least for $p>5$. For $k=fracp-12$, there is no solution (provided $p>3$): $a^2kequiv 1$ implies $a^kequiv pm1$
If $(x,y,z)$ is a solution for some $k$, then so is $(xy^-1bmod p,1,zy^-1bmod p)$, i.e., we need only look for consecutive $k$th powers.
This suggests the following: Find a generator $a$ and for $1le x<p$, find $ell(x)$ such that $a^ell(x)equiv xpmod p$. This can easily be prepared in $plog(p)$ time. Next, loop over $x=1,ldots, p-2$ and note that a solution exists for $k=gcd(ell(x),ell(x+1))$ and any divisor thereof.
answered Jul 22 at 21:04
Hagen von Eitzen
265k20258477
Can you explain this with an example when p=23 and k=20 what can be the number of possible values of k such that a solution exists for x^k+y^k=z^k (mod p) That would be a great help thanks
– dank uploader
Jul 23 at 9:10
Also what is l(x) here
– dank uploader
Jul 23 at 14:10
add a comment |Â
up vote
0
down vote
If you want the statement to hold "for any $x,y,z$" as it is now, then if you plug $x=y=z=1$ you get that $p|1$ which is a contradiction
answered Jul 22 at 20:14
asdf
3,378519
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
accepted
One can reduce the problem a lot:
By Fermat's little theorem, $a^p-1equiv 1pmod p$ for all $anotequiv 0pmod p$. It follows that a solution for $k$ exists iff a solution for $kbmodp-1$ exists, i.e., we need only check $0le k<p-1$. In fact, as taking inverses $bmod p$ is a bijection, a solution f $k$ exists iff a solution for $p-1-k$ exist, i.e., we need only check $0le klefracp-12$. For small $p$, we can thus simply loop over all possible values and check. We immediately get that there is no solution for $k=0$ (as $1+1notequiv 1pmod p$): We also immediately get that $(1,1,2)$ is a solutions for $k=1$ (except when $p=2$), and $(3,4,5)$ is a solution for $k=2$ at least for $p>5$. For $k=fracp-12$, there is no solution (provided $p>3$): $a^2kequiv 1$ implies $a^kequiv pm1$
If $(x,y,z)$ is a solution for some $k$, then so is $(xy^-1bmod p,1,zy^-1bmod p)$, i.e., we need only look for consecutive $k$th powers.
This suggests the following: Find a generator $a$ and for $1le x<p$, find $ell(x)$ such that $a^ell(x)equiv xpmod p$. This can easily be prepared in $plog(p)$ time. Next, loop over $x=1,ldots, p-2$ and note that a solution exists for $k=gcd(ell(x),ell(x+1))$ and any divisor thereof.
answered Jul 22 at 21:04
Hagen von Eitzen
265k20258477
Can you explain this with an example when p=23 and k=20 what can be the number of possible values of k such that a solution exists for x^k+y^k=z^k (mod p) That would be a great help thanks
– dank uploader
Jul 23 at 9:10
Also what is l(x) here
– dank uploader
Jul 23 at 14:10
add a comment |Â
up vote
0
down vote
accepted
One can reduce the problem a lot:
By Fermat's little theorem, $a^p-1equiv 1pmod p$ for all $anotequiv 0pmod p$. It follows that a solution for $k$ exists iff a solution for $kbmodp-1$ exists, i.e., we need only check $0le k<p-1$. In fact, as taking inverses $bmod p$ is a bijection, a solution f $k$ exists iff a solution for $p-1-k$ exist, i.e., we need only check $0le klefracp-12$. For small $p$, we can thus simply loop over all possible values and check. We immediately get that there is no solution for $k=0$ (as $1+1notequiv 1pmod p$): We also immediately get that $(1,1,2)$ is a solutions for $k=1$ (except when $p=2$), and $(3,4,5)$ is a solution for $k=2$ at least for $p>5$. For $k=fracp-12$, there is no solution (provided $p>3$): $a^2kequiv 1$ implies $a^kequiv pm1$
If $(x,y,z)$ is a solution for some $k$, then so is $(xy^-1bmod p,1,zy^-1bmod p)$, i.e., we need only look for consecutive $k$th powers.
This suggests the following: Find a generator $a$ and for $1le x<p$, find $ell(x)$ such that $a^ell(x)equiv xpmod p$. This can easily be prepared in $plog(p)$ time. Next, loop over $x=1,ldots, p-2$ and note that a solution exists for $k=gcd(ell(x),ell(x+1))$ and any divisor thereof.
answered Jul 22 at 21:04
Hagen von Eitzen
265k20258477
Can you explain this with an example when p=23 and k=20 what can be the number of possible values of k such that a solution exists for x^k+y^k=z^k (mod p) That would be a great help thanks
– dank uploader
Jul 23 at 9:10
Also what is l(x) here
– dank uploader
Jul 23 at 14:10
add a comment |Â
up vote
0
down vote
accepted
up vote
0
down vote
accepted
One can reduce the problem a lot:
By Fermat's little theorem, $a^p-1equiv 1pmod p$ for all $anotequiv 0pmod p$. It follows that a solution for $k$ exists iff a solution for $kbmodp-1$ exists, i.e., we need only check $0le k<p-1$. In fact, as taking inverses $bmod p$ is a bijection, a solution f $k$ exists iff a solution for $p-1-k$ exist, i.e., we need only check $0le klefracp-12$. For small $p$, we can thus simply loop over all possible values and check. We immediately get that there is no solution for $k=0$ (as $1+1notequiv 1pmod p$): We also immediately get that $(1,1,2)$ is a solutions for $k=1$ (except when $p=2$), and $(3,4,5)$ is a solution for $k=2$ at least for $p>5$. For $k=fracp-12$, there is no solution (provided $p>3$): $a^2kequiv 1$ implies $a^kequiv pm1$
If $(x,y,z)$ is a solution for some $k$, then so is $(xy^-1bmod p,1,zy^-1bmod p)$, i.e., we need only look for consecutive $k$th powers.
This suggests the following: Find a generator $a$ and for $1le x<p$, find $ell(x)$ such that $a^ell(x)equiv xpmod p$. This can easily be prepared in $plog(p)$ time. Next, loop over $x=1,ldots, p-2$ and note that a solution exists for $k=gcd(ell(x),ell(x+1))$ and any divisor thereof.
answered Jul 22 at 21:04
Hagen von Eitzen
265k20258477
One can reduce the problem a lot:
By Fermat's little theorem, $a^p-1equiv 1pmod p$ for all $anotequiv 0pmod p$. It follows that a solution for $k$ exists iff a solution for $kbmodp-1$ exists, i.e., we need only check $0le k<p-1$. In fact, as taking inverses $bmod p$ is a bijection, a solution f $k$ exists iff a solution for $p-1-k$ exist, i.e., we need only check $0le klefracp-12$. For small $p$, we can thus simply loop over all possible values and check. We immediately get that there is no solution for $k=0$ (as $1+1notequiv 1pmod p$): We also immediately get that $(1,1,2)$ is a solutions for $k=1$ (except when $p=2$), and $(3,4,5)$ is a solution for $k=2$ at least for $p>5$. For $k=fracp-12$, there is no solution (provided $p>3$): $a^2kequiv 1$ implies $a^kequiv pm1$
If $(x,y,z)$ is a solution for some $k$, then so is $(xy^-1bmod p,1,zy^-1bmod p)$, i.e., we need only look for consecutive $k$th powers.
This suggests the following: Find a generator $a$ and for $1le x<p$, find $ell(x)$ such that $a^ell(x)equiv xpmod p$. This can easily be prepared in $plog(p)$ time. Next, loop over $x=1,ldots, p-2$ and note that a solution exists for $k=gcd(ell(x),ell(x+1))$ and any divisor thereof.
answered Jul 22 at 21:04
Hagen von Eitzen
265k20258477
answered Jul 22 at 21:04
Hagen von Eitzen
265k20258477
answered Jul 22 at 21:04
Hagen von Eitzen
265k20258477
answered Jul 22 at 21:04
Hagen von Eitzen
265k20258477
265k20258477
Can you explain this with an example when p=23 and k=20 what can be the number of possible values of k such that a solution exists for x^k+y^k=z^k (mod p) That would be a great help thanks
– dank uploader
Jul 23 at 9:10
Also what is l(x) here
– dank uploader
Jul 23 at 14:10
add a comment |Â
Can you explain this with an example when p=23 and k=20 what can be the number of possible values of k such that a solution exists for x^k+y^k=z^k (mod p) That would be a great help thanks
– dank uploader
Jul 23 at 9:10
Also what is l(x) here
– dank uploader
Jul 23 at 14:10
Can you explain this with an example when p=23 and k=20 what can be the number of possible values of k such that a solution exists for x^k+y^k=z^k (mod p) That would be a great help thanks
– dank uploader
Jul 23 at 9:10
Can you explain this with an example when p=23 and k=20 what can be the number of possible values of k such that a solution exists for x^k+y^k=z^k (mod p) That would be a great help thanks
– dank uploader
Jul 23 at 9:10
Also what is l(x) here
– dank uploader
Jul 23 at 14:10
Also what is l(x) here
– dank uploader
Jul 23 at 14:10
add a comment |Â
up vote
0
down vote
If you want the statement to hold "for any $x,y,z$" as it is now, then if you plug $x=y=z=1$ you get that $p|1$ which is a contradiction
answered Jul 22 at 20:14
asdf
3,378519
add a comment |Â
up vote
0
down vote
If you want the statement to hold "for any $x,y,z$" as it is now, then if you plug $x=y=z=1$ you get that $p|1$ which is a contradiction
answered Jul 22 at 20:14
asdf
3,378519
add a comment |Â
up vote
0
down vote
up vote
0
down vote
If you want the statement to hold "for any $x,y,z$" as it is now, then if you plug $x=y=z=1$ you get that $p|1$ which is a contradiction
answered Jul 22 at 20:14
asdf
3,378519
If you want the statement to hold "for any $x,y,z$" as it is now, then if you plug $x=y=z=1$ you get that $p|1$ which is a contradiction
answered Jul 22 at 20:14
asdf
3,378519
answered Jul 22 at 20:14
asdf
3,378519
answered Jul 22 at 20:14
asdf
3,378519
answered Jul 22 at 20:14
asdf
3,378519
3,378519
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%2f2859719%2fnumber-of-solutions-related-to-fermats-last-theorem%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
Please use MathJax to format your questions
– saulspatz
Jul 22 at 20:06
Am I right in assuming that $p$ is prime? Which programming contest is this from?
– Hagen von Eitzen
Jul 22 at 20:08
@HagenvonEitzen yepp p is prime ques is from hackerearth july circuits
– dank uploader
Jul 22 at 20:18
Perhaps more closely related to Fermat's little theorem.
– saulspatz
Jul 22 at 20:35