Check whether $k in [0, p]$ in the equation: $a^k + b^k equiv c^kmodp$ has no solutions under the following conditions

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
2
down vote

favorite
1












Check whether the equation: $a^k + b^k equiv c^kmodp$ has no solutions



where,

$ p $ is a prime $ > 3 $,

$k in [0, p]$
and the condition $ 0 < a, b, c < p$ holds.



Can we determine all values of $k in [1, p] $ for which solution doesn't exist?

Or I rephrase - for any $k in [1, p]$, how to tell if any solution exists or not? Thanks.



Some Observations:

We are considering $p > 3$, so $(p - 1)$ is always even. We know that there is at least one such $k$ for which solution doesn't exist ($fracp - 12$).

Now, there are some interesting observation/pattern in such values of $k$ (for which there is no solution).



  • If a solution doesn't exist for some $k in [0, p-1)$ , then there is no solution for all $k + n dot (p - 1), n in W$.


  • If $fracp - 12 in Prime$, then there in only one such $k$ i.e. $fracp-12$.


  • If $fracp-12 notin Prime$, then there are/maybe other such $k$. Now, if there is such $k < fracp-12$ for which there is no solution, then $k | (p - 1)$, i.e. $p-1$ is divisible by $k$. In other words, if $k$ and $p-1$ are co-prime, then a solution always exists.


  • Following from previous point, then all such $in [k, 2k, 3k, .. (p-1)]$ don't have any solution.

  • Some examples,

    • $p = 11$:

      $fracp-12 = 5 in Prime$, so only one such k. $5$. (Note we can generate all $k$s as $0, 5, 10, 15, 20, ...$.)

    • $p = 13$:

      $fracp-12 = 6 notin Prime$, other such $k < fracp-12$ are 3 and 4. All such $k in [0, p-1]$ are $0, 3, 4, 6, 8, 9, 12$.

    • $p = 47$:

      $fracp-12 = 23 in Prime$, so only one such $k = 23$. $0, 23, 46$.

    • $p = 67$:

      such $k$s are $0, 22, 33, 44, 66$

    • $p = 29$:

      such $k$s are $0, 7, 14, 21, 28$




number-theory elementary-number-theory modular-arithmetic systems-of-equations diophantine-equations




share|cite|improve this question

















  • 2




    See also this question·.
    – Dietrich Burde
    Jul 24 at 14:56






  • 2




    @DietrichBurde that question was asked me. Please see that this question is different from the previous :)
    – Rahul Goswami
    Jul 24 at 14:57














up vote
2
down vote

favorite
1












Check whether the equation: $a^k + b^k equiv c^kmodp$ has no solutions



where,

$ p $ is a prime $ > 3 $,

$k in [0, p]$
and the condition $ 0 < a, b, c < p$ holds.



Can we determine all values of $k in [1, p] $ for which solution doesn't exist?

Or I rephrase - for any $k in [1, p]$, how to tell if any solution exists or not? Thanks.



Some Observations:

We are considering $p > 3$, so $(p - 1)$ is always even. We know that there is at least one such $k$ for which solution doesn't exist ($fracp - 12$).

Now, there are some interesting observation/pattern in such values of $k$ (for which there is no solution).



  • If a solution doesn't exist for some $k in [0, p-1)$ , then there is no solution for all $k + n dot (p - 1), n in W$.


  • If $fracp - 12 in Prime$, then there in only one such $k$ i.e. $fracp-12$.


  • If $fracp-12 notin Prime$, then there are/maybe other such $k$. Now, if there is such $k < fracp-12$ for which there is no solution, then $k | (p - 1)$, i.e. $p-1$ is divisible by $k$. In other words, if $k$ and $p-1$ are co-prime, then a solution always exists.


  • Following from previous point, then all such $in [k, 2k, 3k, .. (p-1)]$ don't have any solution.

  • Some examples,

    • $p = 11$:

      $fracp-12 = 5 in Prime$, so only one such k. $5$. (Note we can generate all $k$s as $0, 5, 10, 15, 20, ...$.)

    • $p = 13$:

      $fracp-12 = 6 notin Prime$, other such $k < fracp-12$ are 3 and 4. All such $k in [0, p-1]$ are $0, 3, 4, 6, 8, 9, 12$.

    • $p = 47$:

      $fracp-12 = 23 in Prime$, so only one such $k = 23$. $0, 23, 46$.

    • $p = 67$:

      such $k$s are $0, 22, 33, 44, 66$

    • $p = 29$:

      such $k$s are $0, 7, 14, 21, 28$




number-theory elementary-number-theory modular-arithmetic systems-of-equations diophantine-equations




share|cite|improve this question

















  • 2




    See also this question·.
    – Dietrich Burde
    Jul 24 at 14:56






  • 2




    @DietrichBurde that question was asked me. Please see that this question is different from the previous :)
    – Rahul Goswami
    Jul 24 at 14:57












up vote
2
down vote

favorite
1









up vote
2
down vote

favorite
1






1





Check whether the equation: $a^k + b^k equiv c^kmodp$ has no solutions



where,

$ p $ is a prime $ > 3 $,

$k in [0, p]$
and the condition $ 0 < a, b, c < p$ holds.



Can we determine all values of $k in [1, p] $ for which solution doesn't exist?

Or I rephrase - for any $k in [1, p]$, how to tell if any solution exists or not? Thanks.



Some Observations:

We are considering $p > 3$, so $(p - 1)$ is always even. We know that there is at least one such $k$ for which solution doesn't exist ($fracp - 12$).

Now, there are some interesting observation/pattern in such values of $k$ (for which there is no solution).



  • If a solution doesn't exist for some $k in [0, p-1)$ , then there is no solution for all $k + n dot (p - 1), n in W$.


  • If $fracp - 12 in Prime$, then there in only one such $k$ i.e. $fracp-12$.


  • If $fracp-12 notin Prime$, then there are/maybe other such $k$. Now, if there is such $k < fracp-12$ for which there is no solution, then $k | (p - 1)$, i.e. $p-1$ is divisible by $k$. In other words, if $k$ and $p-1$ are co-prime, then a solution always exists.


  • Following from previous point, then all such $in [k, 2k, 3k, .. (p-1)]$ don't have any solution.

  • Some examples,

    • $p = 11$:

      $fracp-12 = 5 in Prime$, so only one such k. $5$. (Note we can generate all $k$s as $0, 5, 10, 15, 20, ...$.)

    • $p = 13$:

      $fracp-12 = 6 notin Prime$, other such $k < fracp-12$ are 3 and 4. All such $k in [0, p-1]$ are $0, 3, 4, 6, 8, 9, 12$.

    • $p = 47$:

      $fracp-12 = 23 in Prime$, so only one such $k = 23$. $0, 23, 46$.

    • $p = 67$:

      such $k$s are $0, 22, 33, 44, 66$

    • $p = 29$:

      such $k$s are $0, 7, 14, 21, 28$




number-theory elementary-number-theory modular-arithmetic systems-of-equations diophantine-equations




share|cite|improve this question













Check whether the equation: $a^k + b^k equiv c^kmodp$ has no solutions



where,

$ p $ is a prime $ > 3 $,

$k in [0, p]$
and the condition $ 0 < a, b, c < p$ holds.



Can we determine all values of $k in [1, p] $ for which solution doesn't exist?

Or I rephrase - for any $k in [1, p]$, how to tell if any solution exists or not? Thanks.



Some Observations:

We are considering $p > 3$, so $(p - 1)$ is always even. We know that there is at least one such $k$ for which solution doesn't exist ($fracp - 12$).

Now, there are some interesting observation/pattern in such values of $k$ (for which there is no solution).



  • If a solution doesn't exist for some $k in [0, p-1)$ , then there is no solution for all $k + n dot (p - 1), n in W$.


  • If $fracp - 12 in Prime$, then there in only one such $k$ i.e. $fracp-12$.


  • If $fracp-12 notin Prime$, then there are/maybe other such $k$. Now, if there is such $k < fracp-12$ for which there is no solution, then $k | (p - 1)$, i.e. $p-1$ is divisible by $k$. In other words, if $k$ and $p-1$ are co-prime, then a solution always exists.


  • Following from previous point, then all such $in [k, 2k, 3k, .. (p-1)]$ don't have any solution.

  • Some examples,

    • $p = 11$:

      $fracp-12 = 5 in Prime$, so only one such k. $5$. (Note we can generate all $k$s as $0, 5, 10, 15, 20, ...$.)

    • $p = 13$:

      $fracp-12 = 6 notin Prime$, other such $k < fracp-12$ are 3 and 4. All such $k in [0, p-1]$ are $0, 3, 4, 6, 8, 9, 12$.

    • $p = 47$:

      $fracp-12 = 23 in Prime$, so only one such $k = 23$. $0, 23, 46$.

    • $p = 67$:

      such $k$s are $0, 22, 33, 44, 66$

    • $p = 29$:

      such $k$s are $0, 7, 14, 21, 28$





number-theory elementary-number-theory modular-arithmetic systems-of-equations diophantine-equations





share|cite|improve this question












share|cite|improve this question




share|cite|improve this question








edited Jul 25 at 19:53
























asked Jul 24 at 14:51









Rahul Goswami

319114




319114







  • 2




    See also this question·.
    – Dietrich Burde
    Jul 24 at 14:56






  • 2




    @DietrichBurde that question was asked me. Please see that this question is different from the previous :)
    – Rahul Goswami
    Jul 24 at 14:57












  • 2




    See also this question·.
    – Dietrich Burde
    Jul 24 at 14:56






  • 2




    @DietrichBurde that question was asked me. Please see that this question is different from the previous :)
    – Rahul Goswami
    Jul 24 at 14:57







2




2




See also this question·.
– Dietrich Burde
Jul 24 at 14:56




See also this question·.
– Dietrich Burde
Jul 24 at 14:56




2




2




@DietrichBurde that question was asked me. Please see that this question is different from the previous :)
– Rahul Goswami
Jul 24 at 14:57




@DietrichBurde that question was asked me. Please see that this question is different from the previous :)
– Rahul Goswami
Jul 24 at 14:57










1 Answer
1






active

oldest

votes

















up vote
1
down vote



accepted










Write $k = k'd$ where $k' = gcd(k,p-1)$ is prime to $p-1$; then $xmapsto x^d$ is a bijection of $mathbbF_p$, and thus writing $X' = X^d, Y'=Y^d, Z'=Z^d$, we see that the equation with $k$ has the same number of solutions as the equation with $k'$. Hence let us assume that $k$ divides $p-1$.



Your question is closely related to counting the number points on the projective Fermat curve $X^k + Y^k = Z^k$ over $mathbbF_p$. That is, we count the solutions for which $(X,Y,Z) neq (0,0,0)$ and we identify any two solutions of the form $(X,Y,Z)$ and $(lambda X,lambda Y,lambda Z)$ where $lambda in mathbbF_p^times$. More precisely, the number of projective solutions is simply $(p-1)$ times the number of solutions to your equation when $(X,Y,Z) neq (0,0,0)$ (you also prohibit solutions of the form where one of $X,Y$ or $Z$ vanishes, but it is easy to count how many solutions are there of this form; I will leave this calculation to you).



Let us focus on counting the number of projective solutions then. Let us denote it by $N_p$. This question is very classical, and it is known how to present the number of solutions (when $k$ divides $p-1$) using certain Jacobi sums, but I doubt this will be of much use to you here. However, as a direct consequence of the use of the Jacobi sums, one obtains the very nice Hasse-Weil estimate $$|N_p - (p+1)| leq (k-1)(k-2)sqrtp$$



In particular, for any given $k$ there are many projective solutions (and hence a solution in your case) for $p$ sufficiently large.



While this does not give a complete answer to your question, note that the complete formula with Jacobi sums will tell you exactly how many solutions there are, but since they are sums of convolutions of characters, I think their behaviour can be quite random. Thus for $k$ large relative to $p$ (say $kapprox p^1/4$) I think it will be hard to say something general.



For more about the Jacobi sums and the Fermat curve, see the nice treatment in section 6.1 of the book "Introduction to Cyclotomic Fields" by Lawrence Washington, where all the claims I mentioned here are proved.



Edit: let me be a bit more precise. Let us write the number of solutions for your equation as $M_p$. You are asking when $M_p > 0$. We have the easy estimate $$M_p geq (p-1)(N_p - 3k),$$ where the $-3k$ comes from the need to disregard solutions of the form $(X,Y,0),(X,0,Z),(0,Y,Z)$. So whenever $N_p >3k$, there is a solution. When does this happen? Well, using the Hasse-Weil bound, we have $$N_p -3k geq p+1 -3k -(k-1)(k-2)sqrtp.$$ If my high school algebra does not fail me, this inequality is achieved whenever (say) $k < frac12p^1/4$, at least if $p>10$. You may check it for yourself (one should also be able to achieve a slightly better bound; in any case the best asymptotic bound is $k<< p^1/4$).



Of course, in general one has to replace $k$ by $gcd(k,p-1)$. Therefore, this method shows that you have a solution whenever $gcd(k,p-1) < frac12p^1/4$ (which is in most cases a much weaker inequality than $k < frac12p^1/4$).






share|cite|improve this answer























  • Hello @GalPorat, thank you for your detailed answer! But I think I wasn't clear to you in asking the question. Here, I am only interested in knowing for how many $k$s does the solution doesn't exist? I mean I don't want the number of solutions for any $k$ (I think this will make things more complex), just yes or no whether the solution exists. The examples I have produced were generated by me by a Python script, but it is not feasible for large primes. Because currently, I am checking every possible values of $a, b, c$ and see if there is a solution!
    – Rahul Goswami
    Jul 24 at 16:17










  • And another important obeservation I noticed in all primes < 100, is that - Whenever a solution exists, the $a$ in the equation is always equal to $1$. So, maybe we can try solving this same problem for $1 + b^k equiv c^k mod p$. Maybe I should add this the question description?
    – Rahul Goswami
    Jul 24 at 16:21










  • Also, can you briefly explain what $mathbbF_p$ means here?
    – Rahul Goswami
    Jul 24 at 16:23










  • @RahulGoswami I edited my answer slightly.
    – Gal Porat
    Jul 24 at 17:00










  • @RahulGoswami $mathbbF_p$ is the field with $p$ elements, aka $mathbbZ/pmathbbZ$ or sometimes $mathbbZ_p$.
    – Gal Porat
    Jul 24 at 17:03










Your Answer




StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);








 

draft saved


draft discarded


















StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2861435%2fcheck-whether-k-in-0-p-in-the-equation-ak-bk-equiv-ck-modp-ha%23new-answer', 'question_page');

);

Post as a guest

















1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes








up vote
1
down vote



accepted










Write $k = k'd$ where $k' = gcd(k,p-1)$ is prime to $p-1$; then $xmapsto x^d$ is a bijection of $mathbbF_p$, and thus writing $X' = X^d, Y'=Y^d, Z'=Z^d$, we see that the equation with $k$ has the same number of solutions as the equation with $k'$. Hence let us assume that $k$ divides $p-1$.



Your question is closely related to counting the number points on the projective Fermat curve $X^k + Y^k = Z^k$ over $mathbbF_p$. That is, we count the solutions for which $(X,Y,Z) neq (0,0,0)$ and we identify any two solutions of the form $(X,Y,Z)$ and $(lambda X,lambda Y,lambda Z)$ where $lambda in mathbbF_p^times$. More precisely, the number of projective solutions is simply $(p-1)$ times the number of solutions to your equation when $(X,Y,Z) neq (0,0,0)$ (you also prohibit solutions of the form where one of $X,Y$ or $Z$ vanishes, but it is easy to count how many solutions are there of this form; I will leave this calculation to you).



Let us focus on counting the number of projective solutions then. Let us denote it by $N_p$. This question is very classical, and it is known how to present the number of solutions (when $k$ divides $p-1$) using certain Jacobi sums, but I doubt this will be of much use to you here. However, as a direct consequence of the use of the Jacobi sums, one obtains the very nice Hasse-Weil estimate $$|N_p - (p+1)| leq (k-1)(k-2)sqrtp$$



In particular, for any given $k$ there are many projective solutions (and hence a solution in your case) for $p$ sufficiently large.



While this does not give a complete answer to your question, note that the complete formula with Jacobi sums will tell you exactly how many solutions there are, but since they are sums of convolutions of characters, I think their behaviour can be quite random. Thus for $k$ large relative to $p$ (say $kapprox p^1/4$) I think it will be hard to say something general.



For more about the Jacobi sums and the Fermat curve, see the nice treatment in section 6.1 of the book "Introduction to Cyclotomic Fields" by Lawrence Washington, where all the claims I mentioned here are proved.



Edit: let me be a bit more precise. Let us write the number of solutions for your equation as $M_p$. You are asking when $M_p > 0$. We have the easy estimate $$M_p geq (p-1)(N_p - 3k),$$ where the $-3k$ comes from the need to disregard solutions of the form $(X,Y,0),(X,0,Z),(0,Y,Z)$. So whenever $N_p >3k$, there is a solution. When does this happen? Well, using the Hasse-Weil bound, we have $$N_p -3k geq p+1 -3k -(k-1)(k-2)sqrtp.$$ If my high school algebra does not fail me, this inequality is achieved whenever (say) $k < frac12p^1/4$, at least if $p>10$. You may check it for yourself (one should also be able to achieve a slightly better bound; in any case the best asymptotic bound is $k<< p^1/4$).



Of course, in general one has to replace $k$ by $gcd(k,p-1)$. Therefore, this method shows that you have a solution whenever $gcd(k,p-1) < frac12p^1/4$ (which is in most cases a much weaker inequality than $k < frac12p^1/4$).






share|cite|improve this answer























  • Hello @GalPorat, thank you for your detailed answer! But I think I wasn't clear to you in asking the question. Here, I am only interested in knowing for how many $k$s does the solution doesn't exist? I mean I don't want the number of solutions for any $k$ (I think this will make things more complex), just yes or no whether the solution exists. The examples I have produced were generated by me by a Python script, but it is not feasible for large primes. Because currently, I am checking every possible values of $a, b, c$ and see if there is a solution!
    – Rahul Goswami
    Jul 24 at 16:17










  • And another important obeservation I noticed in all primes < 100, is that - Whenever a solution exists, the $a$ in the equation is always equal to $1$. So, maybe we can try solving this same problem for $1 + b^k equiv c^k mod p$. Maybe I should add this the question description?
    – Rahul Goswami
    Jul 24 at 16:21










  • Also, can you briefly explain what $mathbbF_p$ means here?
    – Rahul Goswami
    Jul 24 at 16:23










  • @RahulGoswami I edited my answer slightly.
    – Gal Porat
    Jul 24 at 17:00










  • @RahulGoswami $mathbbF_p$ is the field with $p$ elements, aka $mathbbZ/pmathbbZ$ or sometimes $mathbbZ_p$.
    – Gal Porat
    Jul 24 at 17:03














up vote
1
down vote



accepted










Write $k = k'd$ where $k' = gcd(k,p-1)$ is prime to $p-1$; then $xmapsto x^d$ is a bijection of $mathbbF_p$, and thus writing $X' = X^d, Y'=Y^d, Z'=Z^d$, we see that the equation with $k$ has the same number of solutions as the equation with $k'$. Hence let us assume that $k$ divides $p-1$.



Your question is closely related to counting the number points on the projective Fermat curve $X^k + Y^k = Z^k$ over $mathbbF_p$. That is, we count the solutions for which $(X,Y,Z) neq (0,0,0)$ and we identify any two solutions of the form $(X,Y,Z)$ and $(lambda X,lambda Y,lambda Z)$ where $lambda in mathbbF_p^times$. More precisely, the number of projective solutions is simply $(p-1)$ times the number of solutions to your equation when $(X,Y,Z) neq (0,0,0)$ (you also prohibit solutions of the form where one of $X,Y$ or $Z$ vanishes, but it is easy to count how many solutions are there of this form; I will leave this calculation to you).



Let us focus on counting the number of projective solutions then. Let us denote it by $N_p$. This question is very classical, and it is known how to present the number of solutions (when $k$ divides $p-1$) using certain Jacobi sums, but I doubt this will be of much use to you here. However, as a direct consequence of the use of the Jacobi sums, one obtains the very nice Hasse-Weil estimate $$|N_p - (p+1)| leq (k-1)(k-2)sqrtp$$



In particular, for any given $k$ there are many projective solutions (and hence a solution in your case) for $p$ sufficiently large.



While this does not give a complete answer to your question, note that the complete formula with Jacobi sums will tell you exactly how many solutions there are, but since they are sums of convolutions of characters, I think their behaviour can be quite random. Thus for $k$ large relative to $p$ (say $kapprox p^1/4$) I think it will be hard to say something general.



For more about the Jacobi sums and the Fermat curve, see the nice treatment in section 6.1 of the book "Introduction to Cyclotomic Fields" by Lawrence Washington, where all the claims I mentioned here are proved.



Edit: let me be a bit more precise. Let us write the number of solutions for your equation as $M_p$. You are asking when $M_p > 0$. We have the easy estimate $$M_p geq (p-1)(N_p - 3k),$$ where the $-3k$ comes from the need to disregard solutions of the form $(X,Y,0),(X,0,Z),(0,Y,Z)$. So whenever $N_p >3k$, there is a solution. When does this happen? Well, using the Hasse-Weil bound, we have $$N_p -3k geq p+1 -3k -(k-1)(k-2)sqrtp.$$ If my high school algebra does not fail me, this inequality is achieved whenever (say) $k < frac12p^1/4$, at least if $p>10$. You may check it for yourself (one should also be able to achieve a slightly better bound; in any case the best asymptotic bound is $k<< p^1/4$).



Of course, in general one has to replace $k$ by $gcd(k,p-1)$. Therefore, this method shows that you have a solution whenever $gcd(k,p-1) < frac12p^1/4$ (which is in most cases a much weaker inequality than $k < frac12p^1/4$).






share|cite|improve this answer























  • Hello @GalPorat, thank you for your detailed answer! But I think I wasn't clear to you in asking the question. Here, I am only interested in knowing for how many $k$s does the solution doesn't exist? I mean I don't want the number of solutions for any $k$ (I think this will make things more complex), just yes or no whether the solution exists. The examples I have produced were generated by me by a Python script, but it is not feasible for large primes. Because currently, I am checking every possible values of $a, b, c$ and see if there is a solution!
    – Rahul Goswami
    Jul 24 at 16:17










  • And another important obeservation I noticed in all primes < 100, is that - Whenever a solution exists, the $a$ in the equation is always equal to $1$. So, maybe we can try solving this same problem for $1 + b^k equiv c^k mod p$. Maybe I should add this the question description?
    – Rahul Goswami
    Jul 24 at 16:21










  • Also, can you briefly explain what $mathbbF_p$ means here?
    – Rahul Goswami
    Jul 24 at 16:23










  • @RahulGoswami I edited my answer slightly.
    – Gal Porat
    Jul 24 at 17:00










  • @RahulGoswami $mathbbF_p$ is the field with $p$ elements, aka $mathbbZ/pmathbbZ$ or sometimes $mathbbZ_p$.
    – Gal Porat
    Jul 24 at 17:03












up vote
1
down vote



accepted







up vote
1
down vote



accepted






Write $k = k'd$ where $k' = gcd(k,p-1)$ is prime to $p-1$; then $xmapsto x^d$ is a bijection of $mathbbF_p$, and thus writing $X' = X^d, Y'=Y^d, Z'=Z^d$, we see that the equation with $k$ has the same number of solutions as the equation with $k'$. Hence let us assume that $k$ divides $p-1$.



Your question is closely related to counting the number points on the projective Fermat curve $X^k + Y^k = Z^k$ over $mathbbF_p$. That is, we count the solutions for which $(X,Y,Z) neq (0,0,0)$ and we identify any two solutions of the form $(X,Y,Z)$ and $(lambda X,lambda Y,lambda Z)$ where $lambda in mathbbF_p^times$. More precisely, the number of projective solutions is simply $(p-1)$ times the number of solutions to your equation when $(X,Y,Z) neq (0,0,0)$ (you also prohibit solutions of the form where one of $X,Y$ or $Z$ vanishes, but it is easy to count how many solutions are there of this form; I will leave this calculation to you).



Let us focus on counting the number of projective solutions then. Let us denote it by $N_p$. This question is very classical, and it is known how to present the number of solutions (when $k$ divides $p-1$) using certain Jacobi sums, but I doubt this will be of much use to you here. However, as a direct consequence of the use of the Jacobi sums, one obtains the very nice Hasse-Weil estimate $$|N_p - (p+1)| leq (k-1)(k-2)sqrtp$$



In particular, for any given $k$ there are many projective solutions (and hence a solution in your case) for $p$ sufficiently large.



While this does not give a complete answer to your question, note that the complete formula with Jacobi sums will tell you exactly how many solutions there are, but since they are sums of convolutions of characters, I think their behaviour can be quite random. Thus for $k$ large relative to $p$ (say $kapprox p^1/4$) I think it will be hard to say something general.



For more about the Jacobi sums and the Fermat curve, see the nice treatment in section 6.1 of the book "Introduction to Cyclotomic Fields" by Lawrence Washington, where all the claims I mentioned here are proved.



Edit: let me be a bit more precise. Let us write the number of solutions for your equation as $M_p$. You are asking when $M_p > 0$. We have the easy estimate $$M_p geq (p-1)(N_p - 3k),$$ where the $-3k$ comes from the need to disregard solutions of the form $(X,Y,0),(X,0,Z),(0,Y,Z)$. So whenever $N_p >3k$, there is a solution. When does this happen? Well, using the Hasse-Weil bound, we have $$N_p -3k geq p+1 -3k -(k-1)(k-2)sqrtp.$$ If my high school algebra does not fail me, this inequality is achieved whenever (say) $k < frac12p^1/4$, at least if $p>10$. You may check it for yourself (one should also be able to achieve a slightly better bound; in any case the best asymptotic bound is $k<< p^1/4$).



Of course, in general one has to replace $k$ by $gcd(k,p-1)$. Therefore, this method shows that you have a solution whenever $gcd(k,p-1) < frac12p^1/4$ (which is in most cases a much weaker inequality than $k < frac12p^1/4$).






share|cite|improve this answer















Write $k = k'd$ where $k' = gcd(k,p-1)$ is prime to $p-1$; then $xmapsto x^d$ is a bijection of $mathbbF_p$, and thus writing $X' = X^d, Y'=Y^d, Z'=Z^d$, we see that the equation with $k$ has the same number of solutions as the equation with $k'$. Hence let us assume that $k$ divides $p-1$.



Your question is closely related to counting the number points on the projective Fermat curve $X^k + Y^k = Z^k$ over $mathbbF_p$. That is, we count the solutions for which $(X,Y,Z) neq (0,0,0)$ and we identify any two solutions of the form $(X,Y,Z)$ and $(lambda X,lambda Y,lambda Z)$ where $lambda in mathbbF_p^times$. More precisely, the number of projective solutions is simply $(p-1)$ times the number of solutions to your equation when $(X,Y,Z) neq (0,0,0)$ (you also prohibit solutions of the form where one of $X,Y$ or $Z$ vanishes, but it is easy to count how many solutions are there of this form; I will leave this calculation to you).



Let us focus on counting the number of projective solutions then. Let us denote it by $N_p$. This question is very classical, and it is known how to present the number of solutions (when $k$ divides $p-1$) using certain Jacobi sums, but I doubt this will be of much use to you here. However, as a direct consequence of the use of the Jacobi sums, one obtains the very nice Hasse-Weil estimate $$|N_p - (p+1)| leq (k-1)(k-2)sqrtp$$



In particular, for any given $k$ there are many projective solutions (and hence a solution in your case) for $p$ sufficiently large.



While this does not give a complete answer to your question, note that the complete formula with Jacobi sums will tell you exactly how many solutions there are, but since they are sums of convolutions of characters, I think their behaviour can be quite random. Thus for $k$ large relative to $p$ (say $kapprox p^1/4$) I think it will be hard to say something general.



For more about the Jacobi sums and the Fermat curve, see the nice treatment in section 6.1 of the book "Introduction to Cyclotomic Fields" by Lawrence Washington, where all the claims I mentioned here are proved.



Edit: let me be a bit more precise. Let us write the number of solutions for your equation as $M_p$. You are asking when $M_p > 0$. We have the easy estimate $$M_p geq (p-1)(N_p - 3k),$$ where the $-3k$ comes from the need to disregard solutions of the form $(X,Y,0),(X,0,Z),(0,Y,Z)$. So whenever $N_p >3k$, there is a solution. When does this happen? Well, using the Hasse-Weil bound, we have $$N_p -3k geq p+1 -3k -(k-1)(k-2)sqrtp.$$ If my high school algebra does not fail me, this inequality is achieved whenever (say) $k < frac12p^1/4$, at least if $p>10$. You may check it for yourself (one should also be able to achieve a slightly better bound; in any case the best asymptotic bound is $k<< p^1/4$).



Of course, in general one has to replace $k$ by $gcd(k,p-1)$. Therefore, this method shows that you have a solution whenever $gcd(k,p-1) < frac12p^1/4$ (which is in most cases a much weaker inequality than $k < frac12p^1/4$).







share|cite|improve this answer















share|cite|improve this answer



share|cite|improve this answer








edited Jul 24 at 17:54


























answered Jul 24 at 15:56









Gal Porat

718413




718413











  • Hello @GalPorat, thank you for your detailed answer! But I think I wasn't clear to you in asking the question. Here, I am only interested in knowing for how many $k$s does the solution doesn't exist? I mean I don't want the number of solutions for any $k$ (I think this will make things more complex), just yes or no whether the solution exists. The examples I have produced were generated by me by a Python script, but it is not feasible for large primes. Because currently, I am checking every possible values of $a, b, c$ and see if there is a solution!
    – Rahul Goswami
    Jul 24 at 16:17










  • And another important obeservation I noticed in all primes < 100, is that - Whenever a solution exists, the $a$ in the equation is always equal to $1$. So, maybe we can try solving this same problem for $1 + b^k equiv c^k mod p$. Maybe I should add this the question description?
    – Rahul Goswami
    Jul 24 at 16:21










  • Also, can you briefly explain what $mathbbF_p$ means here?
    – Rahul Goswami
    Jul 24 at 16:23










  • @RahulGoswami I edited my answer slightly.
    – Gal Porat
    Jul 24 at 17:00










  • @RahulGoswami $mathbbF_p$ is the field with $p$ elements, aka $mathbbZ/pmathbbZ$ or sometimes $mathbbZ_p$.
    – Gal Porat
    Jul 24 at 17:03
















  • Hello @GalPorat, thank you for your detailed answer! But I think I wasn't clear to you in asking the question. Here, I am only interested in knowing for how many $k$s does the solution doesn't exist? I mean I don't want the number of solutions for any $k$ (I think this will make things more complex), just yes or no whether the solution exists. The examples I have produced were generated by me by a Python script, but it is not feasible for large primes. Because currently, I am checking every possible values of $a, b, c$ and see if there is a solution!
    – Rahul Goswami
    Jul 24 at 16:17










  • And another important obeservation I noticed in all primes < 100, is that - Whenever a solution exists, the $a$ in the equation is always equal to $1$. So, maybe we can try solving this same problem for $1 + b^k equiv c^k mod p$. Maybe I should add this the question description?
    – Rahul Goswami
    Jul 24 at 16:21










  • Also, can you briefly explain what $mathbbF_p$ means here?
    – Rahul Goswami
    Jul 24 at 16:23










  • @RahulGoswami I edited my answer slightly.
    – Gal Porat
    Jul 24 at 17:00










  • @RahulGoswami $mathbbF_p$ is the field with $p$ elements, aka $mathbbZ/pmathbbZ$ or sometimes $mathbbZ_p$.
    – Gal Porat
    Jul 24 at 17:03















Hello @GalPorat, thank you for your detailed answer! But I think I wasn't clear to you in asking the question. Here, I am only interested in knowing for how many $k$s does the solution doesn't exist? I mean I don't want the number of solutions for any $k$ (I think this will make things more complex), just yes or no whether the solution exists. The examples I have produced were generated by me by a Python script, but it is not feasible for large primes. Because currently, I am checking every possible values of $a, b, c$ and see if there is a solution!
– Rahul Goswami
Jul 24 at 16:17




Hello @GalPorat, thank you for your detailed answer! But I think I wasn't clear to you in asking the question. Here, I am only interested in knowing for how many $k$s does the solution doesn't exist? I mean I don't want the number of solutions for any $k$ (I think this will make things more complex), just yes or no whether the solution exists. The examples I have produced were generated by me by a Python script, but it is not feasible for large primes. Because currently, I am checking every possible values of $a, b, c$ and see if there is a solution!
– Rahul Goswami
Jul 24 at 16:17












And another important obeservation I noticed in all primes < 100, is that - Whenever a solution exists, the $a$ in the equation is always equal to $1$. So, maybe we can try solving this same problem for $1 + b^k equiv c^k mod p$. Maybe I should add this the question description?
– Rahul Goswami
Jul 24 at 16:21




And another important obeservation I noticed in all primes < 100, is that - Whenever a solution exists, the $a$ in the equation is always equal to $1$. So, maybe we can try solving this same problem for $1 + b^k equiv c^k mod p$. Maybe I should add this the question description?
– Rahul Goswami
Jul 24 at 16:21












Also, can you briefly explain what $mathbbF_p$ means here?
– Rahul Goswami
Jul 24 at 16:23




Also, can you briefly explain what $mathbbF_p$ means here?
– Rahul Goswami
Jul 24 at 16:23












@RahulGoswami I edited my answer slightly.
– Gal Porat
Jul 24 at 17:00




@RahulGoswami I edited my answer slightly.
– Gal Porat
Jul 24 at 17:00












@RahulGoswami $mathbbF_p$ is the field with $p$ elements, aka $mathbbZ/pmathbbZ$ or sometimes $mathbbZ_p$.
– Gal Porat
Jul 24 at 17:03




@RahulGoswami $mathbbF_p$ is the field with $p$ elements, aka $mathbbZ/pmathbbZ$ or sometimes $mathbbZ_p$.
– Gal Porat
Jul 24 at 17:03












 

draft saved


draft discarded


























 


draft saved


draft discarded














StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2861435%2fcheck-whether-k-in-0-p-in-the-equation-ak-bk-equiv-ck-modp-ha%23new-answer', 'question_page');

);

Post as a guest
































































Comments

Post a Comment

Popular posts from this blog

What is the equation of a 3D cone with generalised tilt?

Image
Clash Royale CLAN TAG #URR8PPP up vote 2 down vote favorite What is the equation of a 3D cone with generalized tilt? I've noticed that in most equations given to represent a cone, there is no parameter which defines the tilt of the cone in 3D space and that most of them have their point at the origin $(0,0,0)$ - I was wondering if anyone could give me a more generalized cone equation for a cone in any position in 3D space 3d share | cite | improve this question edited Jul 25 '16 at 0:05 ervx 9,425 3 13 36 asked Jul 24 '16 at 15:38 Charlene 11 2 2 Welcome to Math.SE! Could you please explain a few things to help people give an answer useful to you: 1. What do you mean by "generalized tilt"? 2. Are you asking about a right circular cone? Does the angle at the vertex matter? 3. What form of answer (implicit, parametric...?) are you looking for? 4. If this is homework, what tools do you have available, an...
Read more

Color the edges and diagonals of a regular polygon

Image
Clash Royale CLAN TAG #URR8PPP up vote 5 down vote favorite 1 Here is the problem: For what $n$ is it possible to color the edges and diagonals of an $n$-side regular polygon with $dfracbinomn23$ colors, such that you use every color exactly three times and for every color the three segments (edges or diagonals) with that color form a triangle? Trivially $nequiv 0 text or 1 pmod3$. I can also prove that if the statement is true for $k$ than it is true for $3k$ as well. How to finish? Please help! Thanks combinatorial-geometry share | cite | improve this question edited Aug 6 at 21:57 alcana 118 4 asked Aug 6 at 21:15 Leo Gardner 356 11 Even assuming "polyhpn" in the title is a typo for polygon , it is unclear what you mean by "the edges and sides". Aren't the side of a regular polygon the same as the edges? A regular $n$-sided polygon has $n$ edges. – hardmath Aug 6 at 21:20 3 $n$ ne...
Read more

Relationship between determinant of matrix and determinant of adjoint?

Image
Clash Royale CLAN TAG #URR8PPP up vote 2 down vote favorite We are studying adjoints in class, and I was curious if there is a relationship between the determinant of matrix A, and the determinant of the adjoint of matrix A? I assume there would be a relationship because finding the adjoint requires creating a cofactor matrix and then transposing it. linear-algebra determinant adjoint-operators share | cite | improve this question asked Nov 17 '17 at 17:32 CluelessCoder 32 5 For a square matrix $A$ of order $n$, we have $A(operatornameadj A)=(operatornameadj A)A=|A|I_n$ where $I_n$ is the identity matrix of order $n$. This should tell you about the determinant of the adjoint in terms of that of $A$ (use multiplicative property and other elementary properties of determinants). – Prasun Biswas Nov 17 '17 at 17:35 1 @CluelessCoder: see here: math.stackexchange.com/questions/516127/…...
Read more