For what primes $p nmid gcd(a,b,c)$ does $p mid a+b+c implies p nmid a^2+b^2+c^2$?
$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?
number-theory prime-numbers divisibility
$endgroup$
add a comment |
$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?
number-theory prime-numbers divisibility
$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
add a comment |
$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?
number-theory prime-numbers divisibility
$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
number-theory prime-numbers divisibility
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
add a comment |
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
add a comment |
1 Answer
1
active
oldest
votes
$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.
$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
add a comment |
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
});
}
});
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
Required, but never shown
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
$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.
$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
add a comment |
$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.
$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
add a comment |
$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.
$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.
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
add a comment |
$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
add a comment |
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.
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
Required, but never shown
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
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
Required, but never shown
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
Required, but never shown
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
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
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