Mixing
$(a^n+ b^n) pmod p = c^n pmod p$ relation between $n$ and $p$
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
I am aware of the fact that the equation $$(a^n+ b^n) pmod p= c^npmod p$$ has a solution for every integer $n$ if $p$ (a prime) is large enough. But I am interested to know the relation between $n$ and $p$ to obtain a solution for the equation. In other words , say we have a prime $p$ then how to determine what values of $n$ can give a solution for $0<a,b,c<p$ .
Also, if we have a given integer $n$ , is there a way to determine what should be the minimum value of $p$ to obtain a solution of the equation? ($0<a,b,c<p$)
number-theory modular-arithmetic finite-fields
edited Jul 24 at 21:21
Bernard
110k635103
asked Jul 24 at 21:18
Sujan Dutta
197211
add a comment |Â
up vote
0
down vote
favorite
I am aware of the fact that the equation $$(a^n+ b^n) pmod p= c^npmod p$$ has a solution for every integer $n$ if $p$ (a prime) is large enough. But I am interested to know the relation between $n$ and $p$ to obtain a solution for the equation. In other words , say we have a prime $p$ then how to determine what values of $n$ can give a solution for $0<a,b,c<p$ .
Also, if we have a given integer $n$ , is there a way to determine what should be the minimum value of $p$ to obtain a solution of the equation? ($0<a,b,c<p$)
number-theory modular-arithmetic finite-fields
edited Jul 24 at 21:21
Bernard
110k635103
asked Jul 24 at 21:18
Sujan Dutta
197211
1
if $a^n + b^n = c^n pmod p$ has a solution for $0 < a,b,c < p$, then multiply everything by $c'^n$ where $c'$ is the inverse of $c pmod p$. the equation $x^n + y^n = 1 pmod p$ has a solution. So you can assume $c = 1$ to simply the task a little bit.
– achille hui
Jul 24 at 21:25
1
Related: math.stackexchange.com/questions/2861435/check-whether-k-in-0-p-in-the-equation-ak-bk-equiv-ck-modp-ha/2861496?noredirect=1#comment5903630_2861496
– Gal Porat
Jul 25 at 6:11
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I am aware of the fact that the equation $$(a^n+ b^n) pmod p= c^npmod p$$ has a solution for every integer $n$ if $p$ (a prime) is large enough. But I am interested to know the relation between $n$ and $p$ to obtain a solution for the equation. In other words , say we have a prime $p$ then how to determine what values of $n$ can give a solution for $0<a,b,c<p$ .
Also, if we have a given integer $n$ , is there a way to determine what should be the minimum value of $p$ to obtain a solution of the equation? ($0<a,b,c<p$)
number-theory modular-arithmetic finite-fields
edited Jul 24 at 21:21
Bernard
110k635103
asked Jul 24 at 21:18
Sujan Dutta
197211
I am aware of the fact that the equation $$(a^n+ b^n) pmod p= c^npmod p$$ has a solution for every integer $n$ if $p$ (a prime) is large enough. But I am interested to know the relation between $n$ and $p$ to obtain a solution for the equation. In other words , say we have a prime $p$ then how to determine what values of $n$ can give a solution for $0<a,b,c<p$ .
Also, if we have a given integer $n$ , is there a way to determine what should be the minimum value of $p$ to obtain a solution of the equation? ($0<a,b,c<p$)
number-theory modular-arithmetic finite-fields
edited Jul 24 at 21:21
Bernard
110k635103
asked Jul 24 at 21:18
Sujan Dutta
197211
edited Jul 24 at 21:21
Bernard
110k635103
edited Jul 24 at 21:21
Bernard
110k635103
edited Jul 24 at 21:21
Bernard
110k635103
110k635103
asked Jul 24 at 21:18
Sujan Dutta
197211
asked Jul 24 at 21:18
Sujan Dutta
197211
asked Jul 24 at 21:18
Sujan Dutta
197211
197211
1
if $a^n + b^n = c^n pmod p$ has a solution for $0 < a,b,c < p$, then multiply everything by $c'^n$ where $c'$ is the inverse of $c pmod p$. the equation $x^n + y^n = 1 pmod p$ has a solution. So you can assume $c = 1$ to simply the task a little bit.
– achille hui
Jul 24 at 21:25
1
Related: math.stackexchange.com/questions/2861435/check-whether-k-in-0-p-in-the-equation-ak-bk-equiv-ck-modp-ha/2861496?noredirect=1#comment5903630_2861496
– Gal Porat
Jul 25 at 6:11
add a comment |Â
1
if $a^n + b^n = c^n pmod p$ has a solution for $0 < a,b,c < p$, then multiply everything by $c'^n$ where $c'$ is the inverse of $c pmod p$. the equation $x^n + y^n = 1 pmod p$ has a solution. So you can assume $c = 1$ to simply the task a little bit.
– achille hui
Jul 24 at 21:25
1
Related: math.stackexchange.com/questions/2861435/check-whether-k-in-0-p-in-the-equation-ak-bk-equiv-ck-modp-ha/2861496?noredirect=1#comment5903630_2861496
– Gal Porat
Jul 25 at 6:11
1
1
if $a^n + b^n = c^n pmod p$ has a solution for $0 < a,b,c < p$, then multiply everything by $c'^n$ where $c'$ is the inverse of $c pmod p$. the equation $x^n + y^n = 1 pmod p$ has a solution. So you can assume $c = 1$ to simply the task a little bit.
– achille hui
Jul 24 at 21:25
if $a^n + b^n = c^n pmod p$ has a solution for $0 < a,b,c < p$, then multiply everything by $c'^n$ where $c'$ is the inverse of $c pmod p$. the equation $x^n + y^n = 1 pmod p$ has a solution. So you can assume $c = 1$ to simply the task a little bit.
– achille hui
Jul 24 at 21:25
1
1
Related: math.stackexchange.com/questions/2861435/check-whether-k-in-0-p-in-the-equation-ak-bk-equiv-ck-modp-ha/2861496?noredirect=1#comment5903630_2861496
– Gal Porat
Jul 25 at 6:11
Related: math.stackexchange.com/questions/2861435/check-whether-k-in-0-p-in-the-equation-ak-bk-equiv-ck-modp-ha/2861496?noredirect=1#comment5903630_2861496
– Gal Porat
Jul 25 at 6:11
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
Tests for small $n$ are easy: No solution for $n=0$, $(1,1,2)$ is a solution for $n=1$ (if $p>2$), $(3,4,5)$ is a solution if $p>5$.
For the general approach: By little Fermat, a solution for $n$ is a solution for $n'$ if $n'equiv npmodp-1$, hence you need only check $0le n<p-1$. In fact, by taking multiplicative inverses $bmod p$, you need only check $nle fracp-12$. As $n=fracp-12$ leads to $a^nequiv pm1pmod p$, we can exclude $fracp-12$ for $p>3$. If $gcd(d,p-1)=1$, taking $d$th powers is just a permutation of the non-zero residue classes $bmod p$, i.e., a solution for $n$ exists iff a solution for $dn$ exists.
For exhaustive searches, one can follow achille hi's comment and look for $x^n+y^nequiv 1pmod p$, or equivalently for $x^n+1equiv z^npmod p$. For a systematic approach, find a primitive root $epsilon$ and for $1le xle p-1$ compute the discrete logarithm $L(x)$, i.e., $0le L(x)<p-1$ with $epsilon^L(x)equiv xpmod p$. Then $x$ is an $n$th power iff $dnequiv L(x)pmod p-1$ for some $d$. Hence by iterating iterate over the values and note that $x,x+1$ are a solution for $n$ iff $n$ is a common divisor of $L(x)+u(p-1)$ and $L(x+1)+v(p-1)$ for suitable $u,v$.
answered Jul 25 at 5:48
Hagen von Eitzen
265k20258477
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
Tests for small $n$ are easy: No solution for $n=0$, $(1,1,2)$ is a solution for $n=1$ (if $p>2$), $(3,4,5)$ is a solution if $p>5$.
For the general approach: By little Fermat, a solution for $n$ is a solution for $n'$ if $n'equiv npmodp-1$, hence you need only check $0le n<p-1$. In fact, by taking multiplicative inverses $bmod p$, you need only check $nle fracp-12$. As $n=fracp-12$ leads to $a^nequiv pm1pmod p$, we can exclude $fracp-12$ for $p>3$. If $gcd(d,p-1)=1$, taking $d$th powers is just a permutation of the non-zero residue classes $bmod p$, i.e., a solution for $n$ exists iff a solution for $dn$ exists.
For exhaustive searches, one can follow achille hi's comment and look for $x^n+y^nequiv 1pmod p$, or equivalently for $x^n+1equiv z^npmod p$. For a systematic approach, find a primitive root $epsilon$ and for $1le xle p-1$ compute the discrete logarithm $L(x)$, i.e., $0le L(x)<p-1$ with $epsilon^L(x)equiv xpmod p$. Then $x$ is an $n$th power iff $dnequiv L(x)pmod p-1$ for some $d$. Hence by iterating iterate over the values and note that $x,x+1$ are a solution for $n$ iff $n$ is a common divisor of $L(x)+u(p-1)$ and $L(x+1)+v(p-1)$ for suitable $u,v$.
answered Jul 25 at 5:48
Hagen von Eitzen
265k20258477
add a comment |Â
up vote
1
down vote
accepted
Tests for small $n$ are easy: No solution for $n=0$, $(1,1,2)$ is a solution for $n=1$ (if $p>2$), $(3,4,5)$ is a solution if $p>5$.
For the general approach: By little Fermat, a solution for $n$ is a solution for $n'$ if $n'equiv npmodp-1$, hence you need only check $0le n<p-1$. In fact, by taking multiplicative inverses $bmod p$, you need only check $nle fracp-12$. As $n=fracp-12$ leads to $a^nequiv pm1pmod p$, we can exclude $fracp-12$ for $p>3$. If $gcd(d,p-1)=1$, taking $d$th powers is just a permutation of the non-zero residue classes $bmod p$, i.e., a solution for $n$ exists iff a solution for $dn$ exists.
For exhaustive searches, one can follow achille hi's comment and look for $x^n+y^nequiv 1pmod p$, or equivalently for $x^n+1equiv z^npmod p$. For a systematic approach, find a primitive root $epsilon$ and for $1le xle p-1$ compute the discrete logarithm $L(x)$, i.e., $0le L(x)<p-1$ with $epsilon^L(x)equiv xpmod p$. Then $x$ is an $n$th power iff $dnequiv L(x)pmod p-1$ for some $d$. Hence by iterating iterate over the values and note that $x,x+1$ are a solution for $n$ iff $n$ is a common divisor of $L(x)+u(p-1)$ and $L(x+1)+v(p-1)$ for suitable $u,v$.
answered Jul 25 at 5:48
Hagen von Eitzen
265k20258477
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
Tests for small $n$ are easy: No solution for $n=0$, $(1,1,2)$ is a solution for $n=1$ (if $p>2$), $(3,4,5)$ is a solution if $p>5$.
For the general approach: By little Fermat, a solution for $n$ is a solution for $n'$ if $n'equiv npmodp-1$, hence you need only check $0le n<p-1$. In fact, by taking multiplicative inverses $bmod p$, you need only check $nle fracp-12$. As $n=fracp-12$ leads to $a^nequiv pm1pmod p$, we can exclude $fracp-12$ for $p>3$. If $gcd(d,p-1)=1$, taking $d$th powers is just a permutation of the non-zero residue classes $bmod p$, i.e., a solution for $n$ exists iff a solution for $dn$ exists.
For exhaustive searches, one can follow achille hi's comment and look for $x^n+y^nequiv 1pmod p$, or equivalently for $x^n+1equiv z^npmod p$. For a systematic approach, find a primitive root $epsilon$ and for $1le xle p-1$ compute the discrete logarithm $L(x)$, i.e., $0le L(x)<p-1$ with $epsilon^L(x)equiv xpmod p$. Then $x$ is an $n$th power iff $dnequiv L(x)pmod p-1$ for some $d$. Hence by iterating iterate over the values and note that $x,x+1$ are a solution for $n$ iff $n$ is a common divisor of $L(x)+u(p-1)$ and $L(x+1)+v(p-1)$ for suitable $u,v$.
answered Jul 25 at 5:48
Hagen von Eitzen
265k20258477
Tests for small $n$ are easy: No solution for $n=0$, $(1,1,2)$ is a solution for $n=1$ (if $p>2$), $(3,4,5)$ is a solution if $p>5$.
For the general approach: By little Fermat, a solution for $n$ is a solution for $n'$ if $n'equiv npmodp-1$, hence you need only check $0le n<p-1$. In fact, by taking multiplicative inverses $bmod p$, you need only check $nle fracp-12$. As $n=fracp-12$ leads to $a^nequiv pm1pmod p$, we can exclude $fracp-12$ for $p>3$. If $gcd(d,p-1)=1$, taking $d$th powers is just a permutation of the non-zero residue classes $bmod p$, i.e., a solution for $n$ exists iff a solution for $dn$ exists.
For exhaustive searches, one can follow achille hi's comment and look for $x^n+y^nequiv 1pmod p$, or equivalently for $x^n+1equiv z^npmod p$. For a systematic approach, find a primitive root $epsilon$ and for $1le xle p-1$ compute the discrete logarithm $L(x)$, i.e., $0le L(x)<p-1$ with $epsilon^L(x)equiv xpmod p$. Then $x$ is an $n$th power iff $dnequiv L(x)pmod p-1$ for some $d$. Hence by iterating iterate over the values and note that $x,x+1$ are a solution for $n$ iff $n$ is a common divisor of $L(x)+u(p-1)$ and $L(x+1)+v(p-1)$ for suitable $u,v$.
answered Jul 25 at 5:48
Hagen von Eitzen
265k20258477
answered Jul 25 at 5:48
Hagen von Eitzen
265k20258477
answered Jul 25 at 5:48
Hagen von Eitzen
265k20258477
answered Jul 25 at 5:48
Hagen von Eitzen
265k20258477
265k20258477
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%2f2861774%2fan-bn-pmod-p-cn-pmod-p-relation-between-n-and-p%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
if $a^n + b^n = c^n pmod p$ has a solution for $0 < a,b,c < p$, then multiply everything by $c'^n$ where $c'$ is the inverse of $c pmod p$. the equation $x^n + y^n = 1 pmod p$ has a solution. So you can assume $c = 1$ to simply the task a little bit.
– achille hui
Jul 24 at 21:25
1
Related: math.stackexchange.com/questions/2861435/check-whether-k-in-0-p-in-the-equation-ak-bk-equiv-ck-modp-ha/2861496?noredirect=1#comment5903630_2861496
– Gal Porat
Jul 25 at 6:11