For what primes $p nmid gcd(a,b,c)$ does $p mid a+b+c implies p nmid a^2+b^2+c^2$?












3















Let us have prime $p$ such that $p nmid gcd(a,b,c)$ and $p mid a+b+c$. For what primes is it then impossible for $p mid a^2+b^2+c^2$ ?




One example of such a prime is $p=5$:



If $5 mid a^2+b^2+c^2$ ; then $5 mid abc$ as the quadratic residues modulo $5$ are only $1,0,-1$. WLOG, let $5mid a$. Then, $5 mid b+c$ and $5 mid b^2+c^2$ which shows that $5 mid bc$ and thus, $5 mid b$ and $5mid c$. Contradiction.



It is probable that $5$ might be the only prime that shows the above characteristics. Are there any other primes or an infinite set of primes that share these properties due to the structure of their quadratic residues?






number-theory prime-numbers divisibility







share|cite|improve this question




















  • 1




    All primes of the form $p=6k-1$ has this property, because they are represented by the binary quadratic form $X^2+XY+Y^2$.
    – user10354138
    Dec 9 at 9:28










  • Are they the only primes that satisfy the property?
    – Haran
    Dec 9 at 9:32










  • Oops, I meant not represented by $X^2+XY+Y^2$. The cases $p=2,3$ are easily eliminated, and all primes of the form $6k+1$ are represented by $X^2+XY+Y^2$ and $6k-1$ are not (recall representability is equivalent to the discriminant $d=-3$ being a quadratic residue $mod 4p$, since $h(-3)=1$).
    – user10354138
    Dec 9 at 9:35












  • Could we speak in chat?
    – Haran
    Dec 9 at 9:41


















3















Let us have prime $p$ such that $p nmid gcd(a,b,c)$ and $p mid a+b+c$. For what primes is it then impossible for $p mid a^2+b^2+c^2$ ?




One example of such a prime is $p=5$:



If $5 mid a^2+b^2+c^2$ ; then $5 mid abc$ as the quadratic residues modulo $5$ are only $1,0,-1$. WLOG, let $5mid a$. Then, $5 mid b+c$ and $5 mid b^2+c^2$ which shows that $5 mid bc$ and thus, $5 mid b$ and $5mid c$. Contradiction.



It is probable that $5$ might be the only prime that shows the above characteristics. Are there any other primes or an infinite set of primes that share these properties due to the structure of their quadratic residues?






number-theory prime-numbers divisibility







share|cite|improve this question




















  • 1




    All primes of the form $p=6k-1$ has this property, because they are represented by the binary quadratic form $X^2+XY+Y^2$.
    – user10354138
    Dec 9 at 9:28










  • Are they the only primes that satisfy the property?
    – Haran
    Dec 9 at 9:32










  • Oops, I meant not represented by $X^2+XY+Y^2$. The cases $p=2,3$ are easily eliminated, and all primes of the form $6k+1$ are represented by $X^2+XY+Y^2$ and $6k-1$ are not (recall representability is equivalent to the discriminant $d=-3$ being a quadratic residue $mod 4p$, since $h(-3)=1$).
    – user10354138
    Dec 9 at 9:35












  • Could we speak in chat?
    – Haran
    Dec 9 at 9:41
















3












3








3








Let us have prime $p$ such that $p nmid gcd(a,b,c)$ and $p mid a+b+c$. For what primes is it then impossible for $p mid a^2+b^2+c^2$ ?




One example of such a prime is $p=5$:



If $5 mid a^2+b^2+c^2$ ; then $5 mid abc$ as the quadratic residues modulo $5$ are only $1,0,-1$. WLOG, let $5mid a$. Then, $5 mid b+c$ and $5 mid b^2+c^2$ which shows that $5 mid bc$ and thus, $5 mid b$ and $5mid c$. Contradiction.



It is probable that $5$ might be the only prime that shows the above characteristics. Are there any other primes or an infinite set of primes that share these properties due to the structure of their quadratic residues?






number-theory prime-numbers divisibility







share|cite|improve this question
















Let us have prime $p$ such that $p nmid gcd(a,b,c)$ and $p mid a+b+c$. For what primes is it then impossible for $p mid a^2+b^2+c^2$ ?




One example of such a prime is $p=5$:



If $5 mid a^2+b^2+c^2$ ; then $5 mid abc$ as the quadratic residues modulo $5$ are only $1,0,-1$. WLOG, let $5mid a$. Then, $5 mid b+c$ and $5 mid b^2+c^2$ which shows that $5 mid bc$ and thus, $5 mid b$ and $5mid c$. Contradiction.



It is probable that $5$ might be the only prime that shows the above characteristics. Are there any other primes or an infinite set of primes that share these properties due to the structure of their quadratic residues?






number-theory prime-numbers divisibility




number-theory prime-numbers divisibility






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Dec 9 at 8:45









TheSimpliFire

12.2k62258




12.2k62258










asked Dec 9 at 8:40









Haran

773320




773320








  • 1




    All primes of the form $p=6k-1$ has this property, because they are represented by the binary quadratic form $X^2+XY+Y^2$.
    – user10354138
    Dec 9 at 9:28










  • Are they the only primes that satisfy the property?
    – Haran
    Dec 9 at 9:32










  • Oops, I meant not represented by $X^2+XY+Y^2$. The cases $p=2,3$ are easily eliminated, and all primes of the form $6k+1$ are represented by $X^2+XY+Y^2$ and $6k-1$ are not (recall representability is equivalent to the discriminant $d=-3$ being a quadratic residue $mod 4p$, since $h(-3)=1$).
    – user10354138
    Dec 9 at 9:35












  • Could we speak in chat?
    – Haran
    Dec 9 at 9:41
















  • 1




    All primes of the form $p=6k-1$ has this property, because they are represented by the binary quadratic form $X^2+XY+Y^2$.
    – user10354138
    Dec 9 at 9:28










  • Are they the only primes that satisfy the property?
    – Haran
    Dec 9 at 9:32










  • Oops, I meant not represented by $X^2+XY+Y^2$. The cases $p=2,3$ are easily eliminated, and all primes of the form $6k+1$ are represented by $X^2+XY+Y^2$ and $6k-1$ are not (recall representability is equivalent to the discriminant $d=-3$ being a quadratic residue $mod 4p$, since $h(-3)=1$).
    – user10354138
    Dec 9 at 9:35












  • Could we speak in chat?
    – Haran
    Dec 9 at 9:41










1




1




All primes of the form $p=6k-1$ has this property, because they are represented by the binary quadratic form $X^2+XY+Y^2$.
– user10354138
Dec 9 at 9:28




All primes of the form $p=6k-1$ has this property, because they are represented by the binary quadratic form $X^2+XY+Y^2$.
– user10354138
Dec 9 at 9:28












Are they the only primes that satisfy the property?
– Haran
Dec 9 at 9:32




Are they the only primes that satisfy the property?
– Haran
Dec 9 at 9:32












Oops, I meant not represented by $X^2+XY+Y^2$. The cases $p=2,3$ are easily eliminated, and all primes of the form $6k+1$ are represented by $X^2+XY+Y^2$ and $6k-1$ are not (recall representability is equivalent to the discriminant $d=-3$ being a quadratic residue $mod 4p$, since $h(-3)=1$).
– user10354138
Dec 9 at 9:35






Oops, I meant not represented by $X^2+XY+Y^2$. The cases $p=2,3$ are easily eliminated, and all primes of the form $6k+1$ are represented by $X^2+XY+Y^2$ and $6k-1$ are not (recall representability is equivalent to the discriminant $d=-3$ being a quadratic residue $mod 4p$, since $h(-3)=1$).
– user10354138
Dec 9 at 9:35














Could we speak in chat?
– Haran
Dec 9 at 9:41






Could we speak in chat?
– Haran
Dec 9 at 9:41












1 Answer
1






active

oldest

votes


















4














Here is a hint to prompt further exploration.



We can eliminate $p=2$ from consideration.



Just setting $c=kp-a-b$ for arbitrary $a$ and $b$ gives, with an easy calculation, the test that $a^2+ab+b^2$ is/is not divisible by $p$ for some choice of $a,b$ - or alternatively whether $(2a+b)^2+3b^2$ is ever divisible by $p$.




Just to add from various comments to the question and this answer, this form can be reduced to saying that $x^2+3$ is divisible by $p$, and this in turn means $x^2equiv -3bmod p$ or that $-3$ is a quadratic residue mod $p$.



This is true for $pequiv 1 bmod 6$ but not for $pequiv -1 bmod 6$ (quite easy to prove using quadratic reciprocity)



You can also go via theorems about which primes are represented by quadratic forms.



The important point here is to note how a question which seems to involve three squares and all the quadratic residues, can be reduced to a question about a single quadratic residue - and how this relates to the coincidences which seem to have to occur if - given all the residues there are - the sum of the three squares never comes out divisible by $p$.



This kind of manipulation is quite common for this type of problem, and the results which come out can look and feel like a kind of magic.






share|cite|improve this answer























  • True, we can also eliminate the values of $p=3,7$
    – Haran
    Dec 9 at 9:10










  • In fact, we can multiply $c^2$ such that $bc equiv 1 pmod{p}$ and $ac equiv x pmod{p}$ to make the equation $p mid x^2+x+1$.
    – Haran
    Dec 9 at 9:19










  • @Haran Or you can perform the same trick with the form $(2a+b)^2+3b^2$ to get the form $x^2+3$ which may be easier to use if you are thinking of quadratic residues, since it takes you down to just one unknown square.
    – Mark Bennet
    Dec 9 at 11:55











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',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
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%2f3032163%2ffor-what-primes-p-nmid-gcda-b-c-does-p-mid-abc-implies-p-nmid-a2b%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes









4














Here is a hint to prompt further exploration.



We can eliminate $p=2$ from consideration.



Just setting $c=kp-a-b$ for arbitrary $a$ and $b$ gives, with an easy calculation, the test that $a^2+ab+b^2$ is/is not divisible by $p$ for some choice of $a,b$ - or alternatively whether $(2a+b)^2+3b^2$ is ever divisible by $p$.




Just to add from various comments to the question and this answer, this form can be reduced to saying that $x^2+3$ is divisible by $p$, and this in turn means $x^2equiv -3bmod p$ or that $-3$ is a quadratic residue mod $p$.



This is true for $pequiv 1 bmod 6$ but not for $pequiv -1 bmod 6$ (quite easy to prove using quadratic reciprocity)



You can also go via theorems about which primes are represented by quadratic forms.



The important point here is to note how a question which seems to involve three squares and all the quadratic residues, can be reduced to a question about a single quadratic residue - and how this relates to the coincidences which seem to have to occur if - given all the residues there are - the sum of the three squares never comes out divisible by $p$.



This kind of manipulation is quite common for this type of problem, and the results which come out can look and feel like a kind of magic.






share|cite|improve this answer























  • True, we can also eliminate the values of $p=3,7$
    – Haran
    Dec 9 at 9:10










  • In fact, we can multiply $c^2$ such that $bc equiv 1 pmod{p}$ and $ac equiv x pmod{p}$ to make the equation $p mid x^2+x+1$.
    – Haran
    Dec 9 at 9:19










  • @Haran Or you can perform the same trick with the form $(2a+b)^2+3b^2$ to get the form $x^2+3$ which may be easier to use if you are thinking of quadratic residues, since it takes you down to just one unknown square.
    – Mark Bennet
    Dec 9 at 11:55
















4














Here is a hint to prompt further exploration.



We can eliminate $p=2$ from consideration.



Just setting $c=kp-a-b$ for arbitrary $a$ and $b$ gives, with an easy calculation, the test that $a^2+ab+b^2$ is/is not divisible by $p$ for some choice of $a,b$ - or alternatively whether $(2a+b)^2+3b^2$ is ever divisible by $p$.




Just to add from various comments to the question and this answer, this form can be reduced to saying that $x^2+3$ is divisible by $p$, and this in turn means $x^2equiv -3bmod p$ or that $-3$ is a quadratic residue mod $p$.



This is true for $pequiv 1 bmod 6$ but not for $pequiv -1 bmod 6$ (quite easy to prove using quadratic reciprocity)



You can also go via theorems about which primes are represented by quadratic forms.



The important point here is to note how a question which seems to involve three squares and all the quadratic residues, can be reduced to a question about a single quadratic residue - and how this relates to the coincidences which seem to have to occur if - given all the residues there are - the sum of the three squares never comes out divisible by $p$.



This kind of manipulation is quite common for this type of problem, and the results which come out can look and feel like a kind of magic.






share|cite|improve this answer























  • True, we can also eliminate the values of $p=3,7$
    – Haran
    Dec 9 at 9:10










  • In fact, we can multiply $c^2$ such that $bc equiv 1 pmod{p}$ and $ac equiv x pmod{p}$ to make the equation $p mid x^2+x+1$.
    – Haran
    Dec 9 at 9:19










  • @Haran Or you can perform the same trick with the form $(2a+b)^2+3b^2$ to get the form $x^2+3$ which may be easier to use if you are thinking of quadratic residues, since it takes you down to just one unknown square.
    – Mark Bennet
    Dec 9 at 11:55














4












4








4






Here is a hint to prompt further exploration.



We can eliminate $p=2$ from consideration.



Just setting $c=kp-a-b$ for arbitrary $a$ and $b$ gives, with an easy calculation, the test that $a^2+ab+b^2$ is/is not divisible by $p$ for some choice of $a,b$ - or alternatively whether $(2a+b)^2+3b^2$ is ever divisible by $p$.




Just to add from various comments to the question and this answer, this form can be reduced to saying that $x^2+3$ is divisible by $p$, and this in turn means $x^2equiv -3bmod p$ or that $-3$ is a quadratic residue mod $p$.



This is true for $pequiv 1 bmod 6$ but not for $pequiv -1 bmod 6$ (quite easy to prove using quadratic reciprocity)



You can also go via theorems about which primes are represented by quadratic forms.



The important point here is to note how a question which seems to involve three squares and all the quadratic residues, can be reduced to a question about a single quadratic residue - and how this relates to the coincidences which seem to have to occur if - given all the residues there are - the sum of the three squares never comes out divisible by $p$.



This kind of manipulation is quite common for this type of problem, and the results which come out can look and feel like a kind of magic.






share|cite|improve this answer














Here is a hint to prompt further exploration.



We can eliminate $p=2$ from consideration.



Just setting $c=kp-a-b$ for arbitrary $a$ and $b$ gives, with an easy calculation, the test that $a^2+ab+b^2$ is/is not divisible by $p$ for some choice of $a,b$ - or alternatively whether $(2a+b)^2+3b^2$ is ever divisible by $p$.




Just to add from various comments to the question and this answer, this form can be reduced to saying that $x^2+3$ is divisible by $p$, and this in turn means $x^2equiv -3bmod p$ or that $-3$ is a quadratic residue mod $p$.



This is true for $pequiv 1 bmod 6$ but not for $pequiv -1 bmod 6$ (quite easy to prove using quadratic reciprocity)



You can also go via theorems about which primes are represented by quadratic forms.



The important point here is to note how a question which seems to involve three squares and all the quadratic residues, can be reduced to a question about a single quadratic residue - and how this relates to the coincidences which seem to have to occur if - given all the residues there are - the sum of the three squares never comes out divisible by $p$.



This kind of manipulation is quite common for this type of problem, and the results which come out can look and feel like a kind of magic.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Dec 9 at 12:20

























answered Dec 9 at 9:00









Mark Bennet

80.4k981179




80.4k981179












  • True, we can also eliminate the values of $p=3,7$
    – Haran
    Dec 9 at 9:10










  • In fact, we can multiply $c^2$ such that $bc equiv 1 pmod{p}$ and $ac equiv x pmod{p}$ to make the equation $p mid x^2+x+1$.
    – Haran
    Dec 9 at 9:19










  • @Haran Or you can perform the same trick with the form $(2a+b)^2+3b^2$ to get the form $x^2+3$ which may be easier to use if you are thinking of quadratic residues, since it takes you down to just one unknown square.
    – Mark Bennet
    Dec 9 at 11:55


















  • True, we can also eliminate the values of $p=3,7$
    – Haran
    Dec 9 at 9:10










  • In fact, we can multiply $c^2$ such that $bc equiv 1 pmod{p}$ and $ac equiv x pmod{p}$ to make the equation $p mid x^2+x+1$.
    – Haran
    Dec 9 at 9:19










  • @Haran Or you can perform the same trick with the form $(2a+b)^2+3b^2$ to get the form $x^2+3$ which may be easier to use if you are thinking of quadratic residues, since it takes you down to just one unknown square.
    – Mark Bennet
    Dec 9 at 11:55
















True, we can also eliminate the values of $p=3,7$
– Haran
Dec 9 at 9:10




True, we can also eliminate the values of $p=3,7$
– Haran
Dec 9 at 9:10












In fact, we can multiply $c^2$ such that $bc equiv 1 pmod{p}$ and $ac equiv x pmod{p}$ to make the equation $p mid x^2+x+1$.
– Haran
Dec 9 at 9:19




In fact, we can multiply $c^2$ such that $bc equiv 1 pmod{p}$ and $ac equiv x pmod{p}$ to make the equation $p mid x^2+x+1$.
– Haran
Dec 9 at 9:19












@Haran Or you can perform the same trick with the form $(2a+b)^2+3b^2$ to get the form $x^2+3$ which may be easier to use if you are thinking of quadratic residues, since it takes you down to just one unknown square.
– Mark Bennet
Dec 9 at 11:55




@Haran Or you can perform the same trick with the form $(2a+b)^2+3b^2$ to get the form $x^2+3$ which may be easier to use if you are thinking of quadratic residues, since it takes you down to just one unknown square.
– Mark Bennet
Dec 9 at 11:55


















draft saved

draft discarded




















































Thanks for contributing an answer to Mathematics Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid …



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.





Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


Please pay close attention to the following guidance:


  • Please be sure to answer the question. Provide details and share your research!

But avoid …



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3032163%2ffor-what-primes-p-nmid-gcda-b-c-does-p-mid-abc-implies-p-nmid-a2b%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







-

Popular posts from this blog

Bressuire

Image
.mw-parser-output .infobox{border:1px solid #aaa;background-color:#f9f9f9;color:black;margin:.5em 0 .5em 1em;padding:.2em;float:right;clear:right;width:22em;text-align:left;font-size:88%;line-height:1.6em}.mw-parser-output .infobox td,.mw-parser-output .infobox th{vertical-align:top;padding:0 .2em}.mw-parser-output .infobox caption{font-size:larger}.mw-parser-output .infobox.bordered{border-collapse:collapse}.mw-parser-output .infobox.bordered td,.mw-parser-output .infobox.bordered th{border:1px solid #aaa}.mw-parser-output .infobox.bordered .borderless td,.mw-parser-output .infobox.bordered .borderless th{border:0}.mw-parser-output .infobox-showbutton .mw-collapsible-text{color:inherit}.mw-parser-output .infobox.bordered .mergedtoprow td,.mw-parser-output .infobox.bordered .mergedtoprow th{border:0;border-top:1px solid #aaa;border-right:1px solid #aaa}.mw-parser-output .infobox.bordered .mergedrow td,.mw-parser-output .infobox.bordered .mergedrow th{border:0;border-right:1px solid ...
Read more

Cabo Verde

Image
  Nota: Cabo-verdiano redireciona para este artigo. Para a língua falada em Cabo Verde, veja crioulo cabo-verdiano. Para outros significados, veja Cabo Verde (desambiguação). Coordenadas: 14° 55' N 23° 31' O Cabo Verde República de Cabo Verde Bandeira Brasão de Armas Lema: Unidade, Trabalho, Progresso Hino nacional: Cântico da Liberdade Gentílico: cabo-verdiano [ 1 ] Capital Praia 14° 55' N 23° 31' O Cidade mais populosa Praia Língua oficial Português Governo República unitária semipresidencialista [ 2 ]  - Presidente Jorge Carlos Fonseca  - Primeiro-ministro Ulisses Correia e Silva História    - Descoberta 1460   - Independência 00 • de Portugal 5 de Julho de 1975   - Multipartidarismo 13 de Janeiro de 1990  Área    - Total 4 033 km² (146.º)  - Água (%) 0,08 População    - Estimativa para 2017 560 899 [ 3 ] hab. (173.º) ...
Read more

Gyllenstierna

Image
.mw-parser-output .infobox{border:1px solid #aaa;background-color:#f9f9f9;color:black;margin:.5em 0 .5em 1em;padding:.2em;float:right;clear:right;width:22em;text-align:left;font-size:88%;line-height:1.6em}.mw-parser-output .infobox td,.mw-parser-output .infobox th{vertical-align:top;padding:0 .2em}.mw-parser-output .infobox caption{font-size:larger}.mw-parser-output .infobox.bordered{border-collapse:collapse}.mw-parser-output .infobox.bordered td,.mw-parser-output .infobox.bordered th{border:1px solid #aaa}.mw-parser-output .infobox.bordered .borderless td,.mw-parser-output .infobox.bordered .borderless th{border:0}.mw-parser-output .infobox-showbutton .mw-collapsible-text{color:inherit}.mw-parser-output .infobox.bordered .mergedtoprow td,.mw-parser-output .infobox.bordered .mergedtoprow th{border:0;border-top:1px solid #aaa;border-right:1px solid #aaa}.mw-parser-output .infobox.bordered .mergedrow td,.mw-parser-output .infobox.bordered .mergedrow th{border:0;border-right:1px solid ...
Read more