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












$begingroup$



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?










share|cite|improve this question











$endgroup$








  • 1




    $begingroup$
    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$.
    $endgroup$
    – user10354138
    Dec 9 '18 at 9:28










  • $begingroup$
    Are they the only primes that satisfy the property?
    $endgroup$
    – Haran
    Dec 9 '18 at 9:32










  • $begingroup$
    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$).
    $endgroup$
    – user10354138
    Dec 9 '18 at 9:35












  • $begingroup$
    Could we speak in chat?
    $endgroup$
    – Haran
    Dec 9 '18 at 9:41


















3












$begingroup$



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?










share|cite|improve this question











$endgroup$








  • 1




    $begingroup$
    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$.
    $endgroup$
    – user10354138
    Dec 9 '18 at 9:28










  • $begingroup$
    Are they the only primes that satisfy the property?
    $endgroup$
    – Haran
    Dec 9 '18 at 9:32










  • $begingroup$
    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$).
    $endgroup$
    – user10354138
    Dec 9 '18 at 9:35












  • $begingroup$
    Could we speak in chat?
    $endgroup$
    – Haran
    Dec 9 '18 at 9:41
















3












3








3





$begingroup$



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?










share|cite|improve this question











$endgroup$





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















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Dec 9 '18 at 8:45









TheSimpliFire

12.8k62461




12.8k62461










asked Dec 9 '18 at 8:40









HaranHaran

1,149424




1,149424








  • 1




    $begingroup$
    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$.
    $endgroup$
    – user10354138
    Dec 9 '18 at 9:28










  • $begingroup$
    Are they the only primes that satisfy the property?
    $endgroup$
    – Haran
    Dec 9 '18 at 9:32










  • $begingroup$
    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$).
    $endgroup$
    – user10354138
    Dec 9 '18 at 9:35












  • $begingroup$
    Could we speak in chat?
    $endgroup$
    – Haran
    Dec 9 '18 at 9:41
















  • 1




    $begingroup$
    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$.
    $endgroup$
    – user10354138
    Dec 9 '18 at 9:28










  • $begingroup$
    Are they the only primes that satisfy the property?
    $endgroup$
    – Haran
    Dec 9 '18 at 9:32










  • $begingroup$
    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$).
    $endgroup$
    – user10354138
    Dec 9 '18 at 9:35












  • $begingroup$
    Could we speak in chat?
    $endgroup$
    – Haran
    Dec 9 '18 at 9:41










1




1




$begingroup$
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$.
$endgroup$
– user10354138
Dec 9 '18 at 9:28




$begingroup$
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$.
$endgroup$
– user10354138
Dec 9 '18 at 9:28












$begingroup$
Are they the only primes that satisfy the property?
$endgroup$
– Haran
Dec 9 '18 at 9:32




$begingroup$
Are they the only primes that satisfy the property?
$endgroup$
– Haran
Dec 9 '18 at 9:32












$begingroup$
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$).
$endgroup$
– user10354138
Dec 9 '18 at 9:35






$begingroup$
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$).
$endgroup$
– user10354138
Dec 9 '18 at 9:35














$begingroup$
Could we speak in chat?
$endgroup$
– Haran
Dec 9 '18 at 9:41






$begingroup$
Could we speak in chat?
$endgroup$
– Haran
Dec 9 '18 at 9:41












1 Answer
1






active

oldest

votes


















4












$begingroup$

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











$endgroup$













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










  • $begingroup$
    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$.
    $endgroup$
    – Haran
    Dec 9 '18 at 9:19










  • $begingroup$
    @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.
    $endgroup$
    – Mark Bennet
    Dec 9 '18 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












$begingroup$

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











$endgroup$













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










  • $begingroup$
    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$.
    $endgroup$
    – Haran
    Dec 9 '18 at 9:19










  • $begingroup$
    @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.
    $endgroup$
    – Mark Bennet
    Dec 9 '18 at 11:55
















4












$begingroup$

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











$endgroup$













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










  • $begingroup$
    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$.
    $endgroup$
    – Haran
    Dec 9 '18 at 9:19










  • $begingroup$
    @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.
    $endgroup$
    – Mark Bennet
    Dec 9 '18 at 11:55














4












4








4





$begingroup$

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











$endgroup$



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 '18 at 12:20

























answered Dec 9 '18 at 9:00









Mark BennetMark Bennet

81.6k984181




81.6k984181












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










  • $begingroup$
    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$.
    $endgroup$
    – Haran
    Dec 9 '18 at 9:19










  • $begingroup$
    @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.
    $endgroup$
    – Mark Bennet
    Dec 9 '18 at 11:55


















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










  • $begingroup$
    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$.
    $endgroup$
    – Haran
    Dec 9 '18 at 9:19










  • $begingroup$
    @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.
    $endgroup$
    – Mark Bennet
    Dec 9 '18 at 11:55
















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




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












$begingroup$
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$.
$endgroup$
– Haran
Dec 9 '18 at 9:19




$begingroup$
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$.
$endgroup$
– Haran
Dec 9 '18 at 9:19












$begingroup$
@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.
$endgroup$
– Mark Bennet
Dec 9 '18 at 11:55




$begingroup$
@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.
$endgroup$
– Mark Bennet
Dec 9 '18 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.




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

How to change which sound is reproduced for terminal bell?

Can I use Tabulator js library in my java Spring + Thymeleaf project?

Title Spacing in Bjornstrup Chapter, Removing Chapter Number From Contents