prove there exist postive integers $a,b$ such $p^2|a^2+ab+b^2$
$begingroup$
Problem 1: Let prime $pequiv 1pmod 3$.show that:there exist postive integers $ale b<p$ such
$$p^2|a^2+ab+b^2$$
I have only prove there $a,b$ such $$p|a^2+ab+b^2$$
Problem 1 from this:
Problem 2.3 (Noam Elkies). Prove that there are infinitely many triples $(a,b,p)$ of integers, with $p$ prime and $0<aleq b<p$, for which $p^5$ divides $(a+b)^p-a^p-b^p$.
The key claim is that if $pequiv1pmod3$, then $$p(x^2+xy+y^2)^2;mathrm{divides};(x+y)^p-x^p-y^p$$ as polynomials in $x$ and $y$. $color{red}{underline{color{black}{text{Since it's known that}}}}$ one can select $a$ and $b$ such that $color{red}{underline{color{black}{p^2mid a^2+ab+b^2}}}$, the conclusion follows. (The theory of quadratic forms tells us we can do it with $p^2=a^2+ab+b^2$; Thue's lemma lets us do it by solving $x^2+x+1equiv0pmod{p^2}$.)
To prove this, it is the same to show that $$(x^2+x+1)^2;mathrm{divides};F(x)overset{mathrm{def}}=(x+1)^p-x^p-1.$$ since the binomial coefficients $binom pk$ are clearly divisible by $p$. Let $zeta$ be a third root of unity. Then $F(zeta)=(1+zeta)^p-zeta^p-1=-zeta^2-zeta-1=0$. Moreover, $F'(x)=p(x+1)^{p-1}-px^{p-1}$, so $F'(zeta)=p-p=0$. Hence $zeta$ is a double root of $F$ as needed.
(Incidentally, $p=2017$ works!)
Image that replaced the text
number-theory
$endgroup$
add a comment |
$begingroup$
Problem 1: Let prime $pequiv 1pmod 3$.show that:there exist postive integers $ale b<p$ such
$$p^2|a^2+ab+b^2$$
I have only prove there $a,b$ such $$p|a^2+ab+b^2$$
Problem 1 from this:
Problem 2.3 (Noam Elkies). Prove that there are infinitely many triples $(a,b,p)$ of integers, with $p$ prime and $0<aleq b<p$, for which $p^5$ divides $(a+b)^p-a^p-b^p$.
The key claim is that if $pequiv1pmod3$, then $$p(x^2+xy+y^2)^2;mathrm{divides};(x+y)^p-x^p-y^p$$ as polynomials in $x$ and $y$. $color{red}{underline{color{black}{text{Since it's known that}}}}$ one can select $a$ and $b$ such that $color{red}{underline{color{black}{p^2mid a^2+ab+b^2}}}$, the conclusion follows. (The theory of quadratic forms tells us we can do it with $p^2=a^2+ab+b^2$; Thue's lemma lets us do it by solving $x^2+x+1equiv0pmod{p^2}$.)
To prove this, it is the same to show that $$(x^2+x+1)^2;mathrm{divides};F(x)overset{mathrm{def}}=(x+1)^p-x^p-1.$$ since the binomial coefficients $binom pk$ are clearly divisible by $p$. Let $zeta$ be a third root of unity. Then $F(zeta)=(1+zeta)^p-zeta^p-1=-zeta^2-zeta-1=0$. Moreover, $F'(x)=p(x+1)^{p-1}-px^{p-1}$, so $F'(zeta)=p-p=0$. Hence $zeta$ is a double root of $F$ as needed.
(Incidentally, $p=2017$ works!)
Image that replaced the text
number-theory
$endgroup$
add a comment |
$begingroup$
Problem 1: Let prime $pequiv 1pmod 3$.show that:there exist postive integers $ale b<p$ such
$$p^2|a^2+ab+b^2$$
I have only prove there $a,b$ such $$p|a^2+ab+b^2$$
Problem 1 from this:
Problem 2.3 (Noam Elkies). Prove that there are infinitely many triples $(a,b,p)$ of integers, with $p$ prime and $0<aleq b<p$, for which $p^5$ divides $(a+b)^p-a^p-b^p$.
The key claim is that if $pequiv1pmod3$, then $$p(x^2+xy+y^2)^2;mathrm{divides};(x+y)^p-x^p-y^p$$ as polynomials in $x$ and $y$. $color{red}{underline{color{black}{text{Since it's known that}}}}$ one can select $a$ and $b$ such that $color{red}{underline{color{black}{p^2mid a^2+ab+b^2}}}$, the conclusion follows. (The theory of quadratic forms tells us we can do it with $p^2=a^2+ab+b^2$; Thue's lemma lets us do it by solving $x^2+x+1equiv0pmod{p^2}$.)
To prove this, it is the same to show that $$(x^2+x+1)^2;mathrm{divides};F(x)overset{mathrm{def}}=(x+1)^p-x^p-1.$$ since the binomial coefficients $binom pk$ are clearly divisible by $p$. Let $zeta$ be a third root of unity. Then $F(zeta)=(1+zeta)^p-zeta^p-1=-zeta^2-zeta-1=0$. Moreover, $F'(x)=p(x+1)^{p-1}-px^{p-1}$, so $F'(zeta)=p-p=0$. Hence $zeta$ is a double root of $F$ as needed.
(Incidentally, $p=2017$ works!)
Image that replaced the text
number-theory
$endgroup$
Problem 1: Let prime $pequiv 1pmod 3$.show that:there exist postive integers $ale b<p$ such
$$p^2|a^2+ab+b^2$$
I have only prove there $a,b$ such $$p|a^2+ab+b^2$$
Problem 1 from this:
Problem 2.3 (Noam Elkies). Prove that there are infinitely many triples $(a,b,p)$ of integers, with $p$ prime and $0<aleq b<p$, for which $p^5$ divides $(a+b)^p-a^p-b^p$.
The key claim is that if $pequiv1pmod3$, then $$p(x^2+xy+y^2)^2;mathrm{divides};(x+y)^p-x^p-y^p$$ as polynomials in $x$ and $y$. $color{red}{underline{color{black}{text{Since it's known that}}}}$ one can select $a$ and $b$ such that $color{red}{underline{color{black}{p^2mid a^2+ab+b^2}}}$, the conclusion follows. (The theory of quadratic forms tells us we can do it with $p^2=a^2+ab+b^2$; Thue's lemma lets us do it by solving $x^2+x+1equiv0pmod{p^2}$.)
To prove this, it is the same to show that $$(x^2+x+1)^2;mathrm{divides};F(x)overset{mathrm{def}}=(x+1)^p-x^p-1.$$ since the binomial coefficients $binom pk$ are clearly divisible by $p$. Let $zeta$ be a third root of unity. Then $F(zeta)=(1+zeta)^p-zeta^p-1=-zeta^2-zeta-1=0$. Moreover, $F'(x)=p(x+1)^{p-1}-px^{p-1}$, so $F'(zeta)=p-p=0$. Hence $zeta$ is a double root of $F$ as needed.
(Incidentally, $p=2017$ works!)
Image that replaced the text
number-theory
number-theory
edited Jan 15 at 8:58
manooooh
5681517
5681517
asked Dec 12 '18 at 13:18
geromtygeromty
977423
977423
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Alternate solution via Thue's Lemma
Proposition. Let $pequiv 1pmod 3$ be a prime. Then there is a solution to
$$
x^2+x+1equiv 0 pmod{p^2}
$$
Proof. By Quadratic Reciprocity, $-3$ is a quadratic residue $pmod p$, hence
$$
u^2 equiv -3 pmod p
$$
for some integer $u$. Setting $uequiv 2c+1pmod p$, this becomes
$$
c^2+c+1 equiv 0 pmod p
$$
So $c$ is a solution to $f(x):=x^2+x+1equiv 0pmod p$. Hensel's Lemma tells us that if
$$
f'(c)notequiv 0 pmod p
$$
Then there exists a unique $d=c+kp$ such that
$$
f(d) equiv 0 pmod{p^2}
$$
Since
$$
f'(c)^2 = (2c+1)^2 equiv -3 pmod p
$$
If $f'(c)equiv 0 pmod p$ then $0equiv -3pmod p$ which implies $p=3$. This contradicts $pequiv 1pmod 3$, therefore $f'(c)notequiv 0 pmod p$.
Hence there is some $d$ such that
$$
d^2+d+1equiv 0 pmod{p^2}
$$
$$tag*{$square$}$$
We now solve our main problem.
Lemma. Let $pequiv 1pmod 3$ be a prime. Then there are integers $0<a,b<p$ such that
$$
a^2+ab+b^2equiv 0 pmod{p^2}
$$
Proof. We have shown that there is some integer $d$ such that
$$
d^2+d+1 equiv 0pmod{p^2}
$$
Now by Thue's Lemma, since $gcd(d,p^2)=1$, we can find $0<|a|,|b|<p$ such that
$$
db equiv a pmod{p^2}
$$
By rearranging the sign, we may assume that $b>0$ and $-p<a<p$. Now $a,b$ satisfies
$$
a^2+ab+b^2 equiv d^2b^2+db^2+b^2 equiv b^2(d^2+d+1)equiv 0 pmod{p^2}
$$
Therefore if $a> 0$ we have found our solution $0<a,b<p$. Otherwise, $a<0$ and we consider two cases ($-aneq b$, otherwise $dequiv -1pmod{p^2}$ contradicts $d^2+d+1equiv 0pmod{p^2}$):
Case 1: $-a > b$
We use the equality
$$
a^2+ab+b^2 = (-a-b)^2 + (-a-b)b + b^2
$$
and obtain a solution $(a',b') = (-a-b,b)$. Since $0<-a<p$ and $0<b<p$, we have $-a-b< p$. By assumption $0 <-a-b$, therefore $0 < a',b' < p$ and we are done.
Case 2: $-a < b$
We use another equality:
$$
a^2 + ab + b^2 = (-a)^2 + (-a)(a+b) + (a+b)^2
$$
and set the new solution as $(a',b') = (-a,a+b)$. Clearly $0 < a'=-a < p$. Since $-p < a < 0$ and $0 < b < p$, we get $a+b < p $. Finally, by assumption we have $0 < a+b$, therefore $0 < a+b=b' < p$. Hence we have a solution $0<a',b' < p$.
$$tag*{$square$}$$
This completes the proof.
Extra. Let $0<a,b<p$ and
$$a^2+ab+b^2equiv 0 pmod{p^2}$$
for some odd $p$. Then
$$a^2+ab+b^2 = p^2$$
Proof. Since $0<a,b< p$, we have
$$
a^2 + ab + b^2 < 3p^2
$$
Morever, since $a^2+ab+b^2equiv 0 pmod{p^2}$, we must have $a^2+ab+b^2 = p^2$ or $2p^2$. If $a^2+ab+b^2=2p^2$ then
$$
a^2+ab+b^2 equiv 0 pmod 2
$$
There is no solution if $a$ or $b$ is odd, therefore both $a,b$ are even. But this means
$$
a^2+ab+b^2equiv 0 pmod 4
$$
Since $a^2+ab+b^2$ is also divisible by odd $p^2$, it is divisible by $4p^2$. This contradicts that $a^2+ab+b^2 < 3p^2$, therefore we must have
$$
a^2+ab+b^2 = p^2
$$
$$tag*{$square$}$$
$endgroup$
add a comment |
$begingroup$
This relies on the following statement: if some residue class $a$ is a square mod $p$, then it is a square mod $p^2$.
Indeed, if $b^2=a+tp [p^2]$, then $(b+kp)^2=a+(t+2k)p [p^2]$.
So you know that there is some $x$ such that $p|x^2+x+1$, thus $-3=(2x-1)^2$ is a square mod $p$, thus mod $p^2$, and if $y^2=-3[p^2]$, then $a=(1+y)/2$ (mod $p^2$) and $1$ work.
$endgroup$
$begingroup$
Your LaTeX is broken
$endgroup$
– Lucas Henrique
Dec 12 '18 at 13:33
1
$begingroup$
Thanks, corrected!
$endgroup$
– Mindlack
Dec 12 '18 at 13:34
$begingroup$
I can't undertand your unswer,first your step ,what's mean
$endgroup$
– math110
Dec 16 '18 at 15:22
add a comment |
$begingroup$
1. Solution to $p^2= X^2+3Y^2$
It is well known that $pequiv 1pmod 3$ if and only if
$$
p=x^2+3y^2
$$
for some integers $x,y$. So immediately we have a presentation of $p^2$ as
$$
begin{align}
p^2 &= (x^2+3y^2)^2\
&=(x+sqrt{-3}y)^2(x-sqrt{-3}y)^2\
&=((x^2-3y^2)+2xysqrt{-3})((x^2-3y^2)-2xysqrt{-3})\
&=(x^2-3y^2)^2+3(2xy)^2
end{align}
$$
2. Solution to $p^2=a^2+ab+b^2,quad 0leq a,b< p$
The expression $u^2+3v^2$ can be rewritten in the following three ways:
$$
begin{align}
u^2+3v^2 &= (pm u-v)^2 + (pm u-v)(2v) + (2v)^2\
u^2+3v^2 &= (u+v)^2 + (u+v)(-u+v) + (-u+v)^2
end{align}
$$
From (1), we have
$$
p^2 = (x^2-3y)^2 + 3(2xy)^2
$$
Therefore applying any of the three transformations will already give us
$$
p^2 = a^2 + ab+b^2
$$
We shall show that depending on whether $x<y$, $y<x<3y$ or $3y<x$, exactly one of the previous transformations will give us a solution such that $0leq a,b<p$. (Clearly $xneq y$ and $xneq 3y$, or $p$ is not prime.)
Case 2a: $x<y$
We use the transformation
$$
u^2+3v^2 = (-u-v)^2 + (-u-v)(2v) + (2v)^2
$$
Hence
$$
begin{align}
p^2 &= (x^2-3y^2)^2 + 3(2xy)^2\
&= (3y^2-x^2-2xy)^2 + (3y^2-x^2-2xy)(4xy) + (4xy)^2\
&= a^2+ab+b^2
end{align}
$$
Hence
$$
begin{align}
a &= 3y^2-x^2-2xy = (3y+x)(y-x)\
b &= 4xy
end{align}
$$
Since $0<x<y$, we get $0< a,b$. Next we check that
$$
begin{align}
p-a &= x^2+3y^2 - (3y^2-x^2-2xy) = 2x^2+2xy > 0\
p-b &= x^2+3y^2 - 4xy = (3y-x)(y-x) > 0
end{align}
$$
Therefore $0< a,b < p$.
Case 2b: $3y<x$
We use the transformation
$$
u^2+3v^2 = (u-v)^2 + (u-v)(2v) + (2v)^2
$$
Hence
$$
begin{align}
p^2 &= (x^2-3y^2)^2 + 3(2xy)^2\
&= (x^2-3y^2-2xy)^2 + (x^2-3y^2-2xy)(4xy) + (4xy)^2\
&= a^2+ab+b^2
end{align}
$$
Hence
$$
begin{align}
a &= x^2-3y^2-2xy = (x-3y)(x+y)\
b &= 4xy
end{align}
$$
Since $0<3y < x$, we get $0< a,b$. Next we check that
$$
begin{align}
p-a &= x^2+3y^2 - (x^2-3y^2-2xy) = 6y^2+2xy > 0\
p-b &= x^2+3y^2 - 4xy = (x-3y)(x-y) > 0
end{align}
$$
Therefore $0< a,b < p$.
Case 2c: $y<x<3y$
We use the transformation
$$
u^2+3v^2 = (u+v)^2 + (u+v)(-u+v) + (-u+v)^2
$$
Hence
$$
begin{align}
p^2 &= (x^2-3y^2)^2 + 3(2xy)^2\
&= (x^2-3y^2+2xy)^2 + (x^2-3y^2+2xy)(3y^2-x^2+2xy) + (3y^2-x^2+2xy)^2\
&= a^2+ab+b^2
end{align}
$$
Hence
$$
begin{align}
a &= x^2-3y^2+2xy = (x+3y)(x-y)\
b &= 3y^2-x^2+2xy = (3y-x)(y+x)
end{align}
$$
Since $y<x < 3y$, we get $0< a,b$. Next we check that
$$
begin{align}
p-a &= x^2+3y^2 - (x^2-3y^2+2xy) = 6y^2-2xy = 2y(3y-x) > 0\
p-b &= x^2+3y^2 - (3y^2-x^2+2xy) = 2x^2-2xy = 2x(x-y) > 0
end{align}
$$
Therefore $0< a,b < p$.
This completes the proof.
$endgroup$
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%2f3036675%2fprove-there-exist-postive-integers-a-b-such-p2a2abb2%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Alternate solution via Thue's Lemma
Proposition. Let $pequiv 1pmod 3$ be a prime. Then there is a solution to
$$
x^2+x+1equiv 0 pmod{p^2}
$$
Proof. By Quadratic Reciprocity, $-3$ is a quadratic residue $pmod p$, hence
$$
u^2 equiv -3 pmod p
$$
for some integer $u$. Setting $uequiv 2c+1pmod p$, this becomes
$$
c^2+c+1 equiv 0 pmod p
$$
So $c$ is a solution to $f(x):=x^2+x+1equiv 0pmod p$. Hensel's Lemma tells us that if
$$
f'(c)notequiv 0 pmod p
$$
Then there exists a unique $d=c+kp$ such that
$$
f(d) equiv 0 pmod{p^2}
$$
Since
$$
f'(c)^2 = (2c+1)^2 equiv -3 pmod p
$$
If $f'(c)equiv 0 pmod p$ then $0equiv -3pmod p$ which implies $p=3$. This contradicts $pequiv 1pmod 3$, therefore $f'(c)notequiv 0 pmod p$.
Hence there is some $d$ such that
$$
d^2+d+1equiv 0 pmod{p^2}
$$
$$tag*{$square$}$$
We now solve our main problem.
Lemma. Let $pequiv 1pmod 3$ be a prime. Then there are integers $0<a,b<p$ such that
$$
a^2+ab+b^2equiv 0 pmod{p^2}
$$
Proof. We have shown that there is some integer $d$ such that
$$
d^2+d+1 equiv 0pmod{p^2}
$$
Now by Thue's Lemma, since $gcd(d,p^2)=1$, we can find $0<|a|,|b|<p$ such that
$$
db equiv a pmod{p^2}
$$
By rearranging the sign, we may assume that $b>0$ and $-p<a<p$. Now $a,b$ satisfies
$$
a^2+ab+b^2 equiv d^2b^2+db^2+b^2 equiv b^2(d^2+d+1)equiv 0 pmod{p^2}
$$
Therefore if $a> 0$ we have found our solution $0<a,b<p$. Otherwise, $a<0$ and we consider two cases ($-aneq b$, otherwise $dequiv -1pmod{p^2}$ contradicts $d^2+d+1equiv 0pmod{p^2}$):
Case 1: $-a > b$
We use the equality
$$
a^2+ab+b^2 = (-a-b)^2 + (-a-b)b + b^2
$$
and obtain a solution $(a',b') = (-a-b,b)$. Since $0<-a<p$ and $0<b<p$, we have $-a-b< p$. By assumption $0 <-a-b$, therefore $0 < a',b' < p$ and we are done.
Case 2: $-a < b$
We use another equality:
$$
a^2 + ab + b^2 = (-a)^2 + (-a)(a+b) + (a+b)^2
$$
and set the new solution as $(a',b') = (-a,a+b)$. Clearly $0 < a'=-a < p$. Since $-p < a < 0$ and $0 < b < p$, we get $a+b < p $. Finally, by assumption we have $0 < a+b$, therefore $0 < a+b=b' < p$. Hence we have a solution $0<a',b' < p$.
$$tag*{$square$}$$
This completes the proof.
Extra. Let $0<a,b<p$ and
$$a^2+ab+b^2equiv 0 pmod{p^2}$$
for some odd $p$. Then
$$a^2+ab+b^2 = p^2$$
Proof. Since $0<a,b< p$, we have
$$
a^2 + ab + b^2 < 3p^2
$$
Morever, since $a^2+ab+b^2equiv 0 pmod{p^2}$, we must have $a^2+ab+b^2 = p^2$ or $2p^2$. If $a^2+ab+b^2=2p^2$ then
$$
a^2+ab+b^2 equiv 0 pmod 2
$$
There is no solution if $a$ or $b$ is odd, therefore both $a,b$ are even. But this means
$$
a^2+ab+b^2equiv 0 pmod 4
$$
Since $a^2+ab+b^2$ is also divisible by odd $p^2$, it is divisible by $4p^2$. This contradicts that $a^2+ab+b^2 < 3p^2$, therefore we must have
$$
a^2+ab+b^2 = p^2
$$
$$tag*{$square$}$$
$endgroup$
add a comment |
$begingroup$
Alternate solution via Thue's Lemma
Proposition. Let $pequiv 1pmod 3$ be a prime. Then there is a solution to
$$
x^2+x+1equiv 0 pmod{p^2}
$$
Proof. By Quadratic Reciprocity, $-3$ is a quadratic residue $pmod p$, hence
$$
u^2 equiv -3 pmod p
$$
for some integer $u$. Setting $uequiv 2c+1pmod p$, this becomes
$$
c^2+c+1 equiv 0 pmod p
$$
So $c$ is a solution to $f(x):=x^2+x+1equiv 0pmod p$. Hensel's Lemma tells us that if
$$
f'(c)notequiv 0 pmod p
$$
Then there exists a unique $d=c+kp$ such that
$$
f(d) equiv 0 pmod{p^2}
$$
Since
$$
f'(c)^2 = (2c+1)^2 equiv -3 pmod p
$$
If $f'(c)equiv 0 pmod p$ then $0equiv -3pmod p$ which implies $p=3$. This contradicts $pequiv 1pmod 3$, therefore $f'(c)notequiv 0 pmod p$.
Hence there is some $d$ such that
$$
d^2+d+1equiv 0 pmod{p^2}
$$
$$tag*{$square$}$$
We now solve our main problem.
Lemma. Let $pequiv 1pmod 3$ be a prime. Then there are integers $0<a,b<p$ such that
$$
a^2+ab+b^2equiv 0 pmod{p^2}
$$
Proof. We have shown that there is some integer $d$ such that
$$
d^2+d+1 equiv 0pmod{p^2}
$$
Now by Thue's Lemma, since $gcd(d,p^2)=1$, we can find $0<|a|,|b|<p$ such that
$$
db equiv a pmod{p^2}
$$
By rearranging the sign, we may assume that $b>0$ and $-p<a<p$. Now $a,b$ satisfies
$$
a^2+ab+b^2 equiv d^2b^2+db^2+b^2 equiv b^2(d^2+d+1)equiv 0 pmod{p^2}
$$
Therefore if $a> 0$ we have found our solution $0<a,b<p$. Otherwise, $a<0$ and we consider two cases ($-aneq b$, otherwise $dequiv -1pmod{p^2}$ contradicts $d^2+d+1equiv 0pmod{p^2}$):
Case 1: $-a > b$
We use the equality
$$
a^2+ab+b^2 = (-a-b)^2 + (-a-b)b + b^2
$$
and obtain a solution $(a',b') = (-a-b,b)$. Since $0<-a<p$ and $0<b<p$, we have $-a-b< p$. By assumption $0 <-a-b$, therefore $0 < a',b' < p$ and we are done.
Case 2: $-a < b$
We use another equality:
$$
a^2 + ab + b^2 = (-a)^2 + (-a)(a+b) + (a+b)^2
$$
and set the new solution as $(a',b') = (-a,a+b)$. Clearly $0 < a'=-a < p$. Since $-p < a < 0$ and $0 < b < p$, we get $a+b < p $. Finally, by assumption we have $0 < a+b$, therefore $0 < a+b=b' < p$. Hence we have a solution $0<a',b' < p$.
$$tag*{$square$}$$
This completes the proof.
Extra. Let $0<a,b<p$ and
$$a^2+ab+b^2equiv 0 pmod{p^2}$$
for some odd $p$. Then
$$a^2+ab+b^2 = p^2$$
Proof. Since $0<a,b< p$, we have
$$
a^2 + ab + b^2 < 3p^2
$$
Morever, since $a^2+ab+b^2equiv 0 pmod{p^2}$, we must have $a^2+ab+b^2 = p^2$ or $2p^2$. If $a^2+ab+b^2=2p^2$ then
$$
a^2+ab+b^2 equiv 0 pmod 2
$$
There is no solution if $a$ or $b$ is odd, therefore both $a,b$ are even. But this means
$$
a^2+ab+b^2equiv 0 pmod 4
$$
Since $a^2+ab+b^2$ is also divisible by odd $p^2$, it is divisible by $4p^2$. This contradicts that $a^2+ab+b^2 < 3p^2$, therefore we must have
$$
a^2+ab+b^2 = p^2
$$
$$tag*{$square$}$$
$endgroup$
add a comment |
$begingroup$
Alternate solution via Thue's Lemma
Proposition. Let $pequiv 1pmod 3$ be a prime. Then there is a solution to
$$
x^2+x+1equiv 0 pmod{p^2}
$$
Proof. By Quadratic Reciprocity, $-3$ is a quadratic residue $pmod p$, hence
$$
u^2 equiv -3 pmod p
$$
for some integer $u$. Setting $uequiv 2c+1pmod p$, this becomes
$$
c^2+c+1 equiv 0 pmod p
$$
So $c$ is a solution to $f(x):=x^2+x+1equiv 0pmod p$. Hensel's Lemma tells us that if
$$
f'(c)notequiv 0 pmod p
$$
Then there exists a unique $d=c+kp$ such that
$$
f(d) equiv 0 pmod{p^2}
$$
Since
$$
f'(c)^2 = (2c+1)^2 equiv -3 pmod p
$$
If $f'(c)equiv 0 pmod p$ then $0equiv -3pmod p$ which implies $p=3$. This contradicts $pequiv 1pmod 3$, therefore $f'(c)notequiv 0 pmod p$.
Hence there is some $d$ such that
$$
d^2+d+1equiv 0 pmod{p^2}
$$
$$tag*{$square$}$$
We now solve our main problem.
Lemma. Let $pequiv 1pmod 3$ be a prime. Then there are integers $0<a,b<p$ such that
$$
a^2+ab+b^2equiv 0 pmod{p^2}
$$
Proof. We have shown that there is some integer $d$ such that
$$
d^2+d+1 equiv 0pmod{p^2}
$$
Now by Thue's Lemma, since $gcd(d,p^2)=1$, we can find $0<|a|,|b|<p$ such that
$$
db equiv a pmod{p^2}
$$
By rearranging the sign, we may assume that $b>0$ and $-p<a<p$. Now $a,b$ satisfies
$$
a^2+ab+b^2 equiv d^2b^2+db^2+b^2 equiv b^2(d^2+d+1)equiv 0 pmod{p^2}
$$
Therefore if $a> 0$ we have found our solution $0<a,b<p$. Otherwise, $a<0$ and we consider two cases ($-aneq b$, otherwise $dequiv -1pmod{p^2}$ contradicts $d^2+d+1equiv 0pmod{p^2}$):
Case 1: $-a > b$
We use the equality
$$
a^2+ab+b^2 = (-a-b)^2 + (-a-b)b + b^2
$$
and obtain a solution $(a',b') = (-a-b,b)$. Since $0<-a<p$ and $0<b<p$, we have $-a-b< p$. By assumption $0 <-a-b$, therefore $0 < a',b' < p$ and we are done.
Case 2: $-a < b$
We use another equality:
$$
a^2 + ab + b^2 = (-a)^2 + (-a)(a+b) + (a+b)^2
$$
and set the new solution as $(a',b') = (-a,a+b)$. Clearly $0 < a'=-a < p$. Since $-p < a < 0$ and $0 < b < p$, we get $a+b < p $. Finally, by assumption we have $0 < a+b$, therefore $0 < a+b=b' < p$. Hence we have a solution $0<a',b' < p$.
$$tag*{$square$}$$
This completes the proof.
Extra. Let $0<a,b<p$ and
$$a^2+ab+b^2equiv 0 pmod{p^2}$$
for some odd $p$. Then
$$a^2+ab+b^2 = p^2$$
Proof. Since $0<a,b< p$, we have
$$
a^2 + ab + b^2 < 3p^2
$$
Morever, since $a^2+ab+b^2equiv 0 pmod{p^2}$, we must have $a^2+ab+b^2 = p^2$ or $2p^2$. If $a^2+ab+b^2=2p^2$ then
$$
a^2+ab+b^2 equiv 0 pmod 2
$$
There is no solution if $a$ or $b$ is odd, therefore both $a,b$ are even. But this means
$$
a^2+ab+b^2equiv 0 pmod 4
$$
Since $a^2+ab+b^2$ is also divisible by odd $p^2$, it is divisible by $4p^2$. This contradicts that $a^2+ab+b^2 < 3p^2$, therefore we must have
$$
a^2+ab+b^2 = p^2
$$
$$tag*{$square$}$$
$endgroup$
Alternate solution via Thue's Lemma
Proposition. Let $pequiv 1pmod 3$ be a prime. Then there is a solution to
$$
x^2+x+1equiv 0 pmod{p^2}
$$
Proof. By Quadratic Reciprocity, $-3$ is a quadratic residue $pmod p$, hence
$$
u^2 equiv -3 pmod p
$$
for some integer $u$. Setting $uequiv 2c+1pmod p$, this becomes
$$
c^2+c+1 equiv 0 pmod p
$$
So $c$ is a solution to $f(x):=x^2+x+1equiv 0pmod p$. Hensel's Lemma tells us that if
$$
f'(c)notequiv 0 pmod p
$$
Then there exists a unique $d=c+kp$ such that
$$
f(d) equiv 0 pmod{p^2}
$$
Since
$$
f'(c)^2 = (2c+1)^2 equiv -3 pmod p
$$
If $f'(c)equiv 0 pmod p$ then $0equiv -3pmod p$ which implies $p=3$. This contradicts $pequiv 1pmod 3$, therefore $f'(c)notequiv 0 pmod p$.
Hence there is some $d$ such that
$$
d^2+d+1equiv 0 pmod{p^2}
$$
$$tag*{$square$}$$
We now solve our main problem.
Lemma. Let $pequiv 1pmod 3$ be a prime. Then there are integers $0<a,b<p$ such that
$$
a^2+ab+b^2equiv 0 pmod{p^2}
$$
Proof. We have shown that there is some integer $d$ such that
$$
d^2+d+1 equiv 0pmod{p^2}
$$
Now by Thue's Lemma, since $gcd(d,p^2)=1$, we can find $0<|a|,|b|<p$ such that
$$
db equiv a pmod{p^2}
$$
By rearranging the sign, we may assume that $b>0$ and $-p<a<p$. Now $a,b$ satisfies
$$
a^2+ab+b^2 equiv d^2b^2+db^2+b^2 equiv b^2(d^2+d+1)equiv 0 pmod{p^2}
$$
Therefore if $a> 0$ we have found our solution $0<a,b<p$. Otherwise, $a<0$ and we consider two cases ($-aneq b$, otherwise $dequiv -1pmod{p^2}$ contradicts $d^2+d+1equiv 0pmod{p^2}$):
Case 1: $-a > b$
We use the equality
$$
a^2+ab+b^2 = (-a-b)^2 + (-a-b)b + b^2
$$
and obtain a solution $(a',b') = (-a-b,b)$. Since $0<-a<p$ and $0<b<p$, we have $-a-b< p$. By assumption $0 <-a-b$, therefore $0 < a',b' < p$ and we are done.
Case 2: $-a < b$
We use another equality:
$$
a^2 + ab + b^2 = (-a)^2 + (-a)(a+b) + (a+b)^2
$$
and set the new solution as $(a',b') = (-a,a+b)$. Clearly $0 < a'=-a < p$. Since $-p < a < 0$ and $0 < b < p$, we get $a+b < p $. Finally, by assumption we have $0 < a+b$, therefore $0 < a+b=b' < p$. Hence we have a solution $0<a',b' < p$.
$$tag*{$square$}$$
This completes the proof.
Extra. Let $0<a,b<p$ and
$$a^2+ab+b^2equiv 0 pmod{p^2}$$
for some odd $p$. Then
$$a^2+ab+b^2 = p^2$$
Proof. Since $0<a,b< p$, we have
$$
a^2 + ab + b^2 < 3p^2
$$
Morever, since $a^2+ab+b^2equiv 0 pmod{p^2}$, we must have $a^2+ab+b^2 = p^2$ or $2p^2$. If $a^2+ab+b^2=2p^2$ then
$$
a^2+ab+b^2 equiv 0 pmod 2
$$
There is no solution if $a$ or $b$ is odd, therefore both $a,b$ are even. But this means
$$
a^2+ab+b^2equiv 0 pmod 4
$$
Since $a^2+ab+b^2$ is also divisible by odd $p^2$, it is divisible by $4p^2$. This contradicts that $a^2+ab+b^2 < 3p^2$, therefore we must have
$$
a^2+ab+b^2 = p^2
$$
$$tag*{$square$}$$
answered Jan 15 at 6:49
Yong Hao NgYong Hao Ng
3,5691222
3,5691222
add a comment |
add a comment |
$begingroup$
This relies on the following statement: if some residue class $a$ is a square mod $p$, then it is a square mod $p^2$.
Indeed, if $b^2=a+tp [p^2]$, then $(b+kp)^2=a+(t+2k)p [p^2]$.
So you know that there is some $x$ such that $p|x^2+x+1$, thus $-3=(2x-1)^2$ is a square mod $p$, thus mod $p^2$, and if $y^2=-3[p^2]$, then $a=(1+y)/2$ (mod $p^2$) and $1$ work.
$endgroup$
$begingroup$
Your LaTeX is broken
$endgroup$
– Lucas Henrique
Dec 12 '18 at 13:33
1
$begingroup$
Thanks, corrected!
$endgroup$
– Mindlack
Dec 12 '18 at 13:34
$begingroup$
I can't undertand your unswer,first your step ,what's mean
$endgroup$
– math110
Dec 16 '18 at 15:22
add a comment |
$begingroup$
This relies on the following statement: if some residue class $a$ is a square mod $p$, then it is a square mod $p^2$.
Indeed, if $b^2=a+tp [p^2]$, then $(b+kp)^2=a+(t+2k)p [p^2]$.
So you know that there is some $x$ such that $p|x^2+x+1$, thus $-3=(2x-1)^2$ is a square mod $p$, thus mod $p^2$, and if $y^2=-3[p^2]$, then $a=(1+y)/2$ (mod $p^2$) and $1$ work.
$endgroup$
$begingroup$
Your LaTeX is broken
$endgroup$
– Lucas Henrique
Dec 12 '18 at 13:33
1
$begingroup$
Thanks, corrected!
$endgroup$
– Mindlack
Dec 12 '18 at 13:34
$begingroup$
I can't undertand your unswer,first your step ,what's mean
$endgroup$
– math110
Dec 16 '18 at 15:22
add a comment |
$begingroup$
This relies on the following statement: if some residue class $a$ is a square mod $p$, then it is a square mod $p^2$.
Indeed, if $b^2=a+tp [p^2]$, then $(b+kp)^2=a+(t+2k)p [p^2]$.
So you know that there is some $x$ such that $p|x^2+x+1$, thus $-3=(2x-1)^2$ is a square mod $p$, thus mod $p^2$, and if $y^2=-3[p^2]$, then $a=(1+y)/2$ (mod $p^2$) and $1$ work.
$endgroup$
This relies on the following statement: if some residue class $a$ is a square mod $p$, then it is a square mod $p^2$.
Indeed, if $b^2=a+tp [p^2]$, then $(b+kp)^2=a+(t+2k)p [p^2]$.
So you know that there is some $x$ such that $p|x^2+x+1$, thus $-3=(2x-1)^2$ is a square mod $p$, thus mod $p^2$, and if $y^2=-3[p^2]$, then $a=(1+y)/2$ (mod $p^2$) and $1$ work.
edited Dec 12 '18 at 13:34
answered Dec 12 '18 at 13:32
MindlackMindlack
3,73518
3,73518
$begingroup$
Your LaTeX is broken
$endgroup$
– Lucas Henrique
Dec 12 '18 at 13:33
1
$begingroup$
Thanks, corrected!
$endgroup$
– Mindlack
Dec 12 '18 at 13:34
$begingroup$
I can't undertand your unswer,first your step ,what's mean
$endgroup$
– math110
Dec 16 '18 at 15:22
add a comment |
$begingroup$
Your LaTeX is broken
$endgroup$
– Lucas Henrique
Dec 12 '18 at 13:33
1
$begingroup$
Thanks, corrected!
$endgroup$
– Mindlack
Dec 12 '18 at 13:34
$begingroup$
I can't undertand your unswer,first your step ,what's mean
$endgroup$
– math110
Dec 16 '18 at 15:22
$begingroup$
Your LaTeX is broken
$endgroup$
– Lucas Henrique
Dec 12 '18 at 13:33
$begingroup$
Your LaTeX is broken
$endgroup$
– Lucas Henrique
Dec 12 '18 at 13:33
1
1
$begingroup$
Thanks, corrected!
$endgroup$
– Mindlack
Dec 12 '18 at 13:34
$begingroup$
Thanks, corrected!
$endgroup$
– Mindlack
Dec 12 '18 at 13:34
$begingroup$
I can't undertand your unswer,first your step ,what's mean
$endgroup$
– math110
Dec 16 '18 at 15:22
$begingroup$
I can't undertand your unswer,first your step ,what's mean
$endgroup$
– math110
Dec 16 '18 at 15:22
add a comment |
$begingroup$
1. Solution to $p^2= X^2+3Y^2$
It is well known that $pequiv 1pmod 3$ if and only if
$$
p=x^2+3y^2
$$
for some integers $x,y$. So immediately we have a presentation of $p^2$ as
$$
begin{align}
p^2 &= (x^2+3y^2)^2\
&=(x+sqrt{-3}y)^2(x-sqrt{-3}y)^2\
&=((x^2-3y^2)+2xysqrt{-3})((x^2-3y^2)-2xysqrt{-3})\
&=(x^2-3y^2)^2+3(2xy)^2
end{align}
$$
2. Solution to $p^2=a^2+ab+b^2,quad 0leq a,b< p$
The expression $u^2+3v^2$ can be rewritten in the following three ways:
$$
begin{align}
u^2+3v^2 &= (pm u-v)^2 + (pm u-v)(2v) + (2v)^2\
u^2+3v^2 &= (u+v)^2 + (u+v)(-u+v) + (-u+v)^2
end{align}
$$
From (1), we have
$$
p^2 = (x^2-3y)^2 + 3(2xy)^2
$$
Therefore applying any of the three transformations will already give us
$$
p^2 = a^2 + ab+b^2
$$
We shall show that depending on whether $x<y$, $y<x<3y$ or $3y<x$, exactly one of the previous transformations will give us a solution such that $0leq a,b<p$. (Clearly $xneq y$ and $xneq 3y$, or $p$ is not prime.)
Case 2a: $x<y$
We use the transformation
$$
u^2+3v^2 = (-u-v)^2 + (-u-v)(2v) + (2v)^2
$$
Hence
$$
begin{align}
p^2 &= (x^2-3y^2)^2 + 3(2xy)^2\
&= (3y^2-x^2-2xy)^2 + (3y^2-x^2-2xy)(4xy) + (4xy)^2\
&= a^2+ab+b^2
end{align}
$$
Hence
$$
begin{align}
a &= 3y^2-x^2-2xy = (3y+x)(y-x)\
b &= 4xy
end{align}
$$
Since $0<x<y$, we get $0< a,b$. Next we check that
$$
begin{align}
p-a &= x^2+3y^2 - (3y^2-x^2-2xy) = 2x^2+2xy > 0\
p-b &= x^2+3y^2 - 4xy = (3y-x)(y-x) > 0
end{align}
$$
Therefore $0< a,b < p$.
Case 2b: $3y<x$
We use the transformation
$$
u^2+3v^2 = (u-v)^2 + (u-v)(2v) + (2v)^2
$$
Hence
$$
begin{align}
p^2 &= (x^2-3y^2)^2 + 3(2xy)^2\
&= (x^2-3y^2-2xy)^2 + (x^2-3y^2-2xy)(4xy) + (4xy)^2\
&= a^2+ab+b^2
end{align}
$$
Hence
$$
begin{align}
a &= x^2-3y^2-2xy = (x-3y)(x+y)\
b &= 4xy
end{align}
$$
Since $0<3y < x$, we get $0< a,b$. Next we check that
$$
begin{align}
p-a &= x^2+3y^2 - (x^2-3y^2-2xy) = 6y^2+2xy > 0\
p-b &= x^2+3y^2 - 4xy = (x-3y)(x-y) > 0
end{align}
$$
Therefore $0< a,b < p$.
Case 2c: $y<x<3y$
We use the transformation
$$
u^2+3v^2 = (u+v)^2 + (u+v)(-u+v) + (-u+v)^2
$$
Hence
$$
begin{align}
p^2 &= (x^2-3y^2)^2 + 3(2xy)^2\
&= (x^2-3y^2+2xy)^2 + (x^2-3y^2+2xy)(3y^2-x^2+2xy) + (3y^2-x^2+2xy)^2\
&= a^2+ab+b^2
end{align}
$$
Hence
$$
begin{align}
a &= x^2-3y^2+2xy = (x+3y)(x-y)\
b &= 3y^2-x^2+2xy = (3y-x)(y+x)
end{align}
$$
Since $y<x < 3y$, we get $0< a,b$. Next we check that
$$
begin{align}
p-a &= x^2+3y^2 - (x^2-3y^2+2xy) = 6y^2-2xy = 2y(3y-x) > 0\
p-b &= x^2+3y^2 - (3y^2-x^2+2xy) = 2x^2-2xy = 2x(x-y) > 0
end{align}
$$
Therefore $0< a,b < p$.
This completes the proof.
$endgroup$
add a comment |
$begingroup$
1. Solution to $p^2= X^2+3Y^2$
It is well known that $pequiv 1pmod 3$ if and only if
$$
p=x^2+3y^2
$$
for some integers $x,y$. So immediately we have a presentation of $p^2$ as
$$
begin{align}
p^2 &= (x^2+3y^2)^2\
&=(x+sqrt{-3}y)^2(x-sqrt{-3}y)^2\
&=((x^2-3y^2)+2xysqrt{-3})((x^2-3y^2)-2xysqrt{-3})\
&=(x^2-3y^2)^2+3(2xy)^2
end{align}
$$
2. Solution to $p^2=a^2+ab+b^2,quad 0leq a,b< p$
The expression $u^2+3v^2$ can be rewritten in the following three ways:
$$
begin{align}
u^2+3v^2 &= (pm u-v)^2 + (pm u-v)(2v) + (2v)^2\
u^2+3v^2 &= (u+v)^2 + (u+v)(-u+v) + (-u+v)^2
end{align}
$$
From (1), we have
$$
p^2 = (x^2-3y)^2 + 3(2xy)^2
$$
Therefore applying any of the three transformations will already give us
$$
p^2 = a^2 + ab+b^2
$$
We shall show that depending on whether $x<y$, $y<x<3y$ or $3y<x$, exactly one of the previous transformations will give us a solution such that $0leq a,b<p$. (Clearly $xneq y$ and $xneq 3y$, or $p$ is not prime.)
Case 2a: $x<y$
We use the transformation
$$
u^2+3v^2 = (-u-v)^2 + (-u-v)(2v) + (2v)^2
$$
Hence
$$
begin{align}
p^2 &= (x^2-3y^2)^2 + 3(2xy)^2\
&= (3y^2-x^2-2xy)^2 + (3y^2-x^2-2xy)(4xy) + (4xy)^2\
&= a^2+ab+b^2
end{align}
$$
Hence
$$
begin{align}
a &= 3y^2-x^2-2xy = (3y+x)(y-x)\
b &= 4xy
end{align}
$$
Since $0<x<y$, we get $0< a,b$. Next we check that
$$
begin{align}
p-a &= x^2+3y^2 - (3y^2-x^2-2xy) = 2x^2+2xy > 0\
p-b &= x^2+3y^2 - 4xy = (3y-x)(y-x) > 0
end{align}
$$
Therefore $0< a,b < p$.
Case 2b: $3y<x$
We use the transformation
$$
u^2+3v^2 = (u-v)^2 + (u-v)(2v) + (2v)^2
$$
Hence
$$
begin{align}
p^2 &= (x^2-3y^2)^2 + 3(2xy)^2\
&= (x^2-3y^2-2xy)^2 + (x^2-3y^2-2xy)(4xy) + (4xy)^2\
&= a^2+ab+b^2
end{align}
$$
Hence
$$
begin{align}
a &= x^2-3y^2-2xy = (x-3y)(x+y)\
b &= 4xy
end{align}
$$
Since $0<3y < x$, we get $0< a,b$. Next we check that
$$
begin{align}
p-a &= x^2+3y^2 - (x^2-3y^2-2xy) = 6y^2+2xy > 0\
p-b &= x^2+3y^2 - 4xy = (x-3y)(x-y) > 0
end{align}
$$
Therefore $0< a,b < p$.
Case 2c: $y<x<3y$
We use the transformation
$$
u^2+3v^2 = (u+v)^2 + (u+v)(-u+v) + (-u+v)^2
$$
Hence
$$
begin{align}
p^2 &= (x^2-3y^2)^2 + 3(2xy)^2\
&= (x^2-3y^2+2xy)^2 + (x^2-3y^2+2xy)(3y^2-x^2+2xy) + (3y^2-x^2+2xy)^2\
&= a^2+ab+b^2
end{align}
$$
Hence
$$
begin{align}
a &= x^2-3y^2+2xy = (x+3y)(x-y)\
b &= 3y^2-x^2+2xy = (3y-x)(y+x)
end{align}
$$
Since $y<x < 3y$, we get $0< a,b$. Next we check that
$$
begin{align}
p-a &= x^2+3y^2 - (x^2-3y^2+2xy) = 6y^2-2xy = 2y(3y-x) > 0\
p-b &= x^2+3y^2 - (3y^2-x^2+2xy) = 2x^2-2xy = 2x(x-y) > 0
end{align}
$$
Therefore $0< a,b < p$.
This completes the proof.
$endgroup$
add a comment |
$begingroup$
1. Solution to $p^2= X^2+3Y^2$
It is well known that $pequiv 1pmod 3$ if and only if
$$
p=x^2+3y^2
$$
for some integers $x,y$. So immediately we have a presentation of $p^2$ as
$$
begin{align}
p^2 &= (x^2+3y^2)^2\
&=(x+sqrt{-3}y)^2(x-sqrt{-3}y)^2\
&=((x^2-3y^2)+2xysqrt{-3})((x^2-3y^2)-2xysqrt{-3})\
&=(x^2-3y^2)^2+3(2xy)^2
end{align}
$$
2. Solution to $p^2=a^2+ab+b^2,quad 0leq a,b< p$
The expression $u^2+3v^2$ can be rewritten in the following three ways:
$$
begin{align}
u^2+3v^2 &= (pm u-v)^2 + (pm u-v)(2v) + (2v)^2\
u^2+3v^2 &= (u+v)^2 + (u+v)(-u+v) + (-u+v)^2
end{align}
$$
From (1), we have
$$
p^2 = (x^2-3y)^2 + 3(2xy)^2
$$
Therefore applying any of the three transformations will already give us
$$
p^2 = a^2 + ab+b^2
$$
We shall show that depending on whether $x<y$, $y<x<3y$ or $3y<x$, exactly one of the previous transformations will give us a solution such that $0leq a,b<p$. (Clearly $xneq y$ and $xneq 3y$, or $p$ is not prime.)
Case 2a: $x<y$
We use the transformation
$$
u^2+3v^2 = (-u-v)^2 + (-u-v)(2v) + (2v)^2
$$
Hence
$$
begin{align}
p^2 &= (x^2-3y^2)^2 + 3(2xy)^2\
&= (3y^2-x^2-2xy)^2 + (3y^2-x^2-2xy)(4xy) + (4xy)^2\
&= a^2+ab+b^2
end{align}
$$
Hence
$$
begin{align}
a &= 3y^2-x^2-2xy = (3y+x)(y-x)\
b &= 4xy
end{align}
$$
Since $0<x<y$, we get $0< a,b$. Next we check that
$$
begin{align}
p-a &= x^2+3y^2 - (3y^2-x^2-2xy) = 2x^2+2xy > 0\
p-b &= x^2+3y^2 - 4xy = (3y-x)(y-x) > 0
end{align}
$$
Therefore $0< a,b < p$.
Case 2b: $3y<x$
We use the transformation
$$
u^2+3v^2 = (u-v)^2 + (u-v)(2v) + (2v)^2
$$
Hence
$$
begin{align}
p^2 &= (x^2-3y^2)^2 + 3(2xy)^2\
&= (x^2-3y^2-2xy)^2 + (x^2-3y^2-2xy)(4xy) + (4xy)^2\
&= a^2+ab+b^2
end{align}
$$
Hence
$$
begin{align}
a &= x^2-3y^2-2xy = (x-3y)(x+y)\
b &= 4xy
end{align}
$$
Since $0<3y < x$, we get $0< a,b$. Next we check that
$$
begin{align}
p-a &= x^2+3y^2 - (x^2-3y^2-2xy) = 6y^2+2xy > 0\
p-b &= x^2+3y^2 - 4xy = (x-3y)(x-y) > 0
end{align}
$$
Therefore $0< a,b < p$.
Case 2c: $y<x<3y$
We use the transformation
$$
u^2+3v^2 = (u+v)^2 + (u+v)(-u+v) + (-u+v)^2
$$
Hence
$$
begin{align}
p^2 &= (x^2-3y^2)^2 + 3(2xy)^2\
&= (x^2-3y^2+2xy)^2 + (x^2-3y^2+2xy)(3y^2-x^2+2xy) + (3y^2-x^2+2xy)^2\
&= a^2+ab+b^2
end{align}
$$
Hence
$$
begin{align}
a &= x^2-3y^2+2xy = (x+3y)(x-y)\
b &= 3y^2-x^2+2xy = (3y-x)(y+x)
end{align}
$$
Since $y<x < 3y$, we get $0< a,b$. Next we check that
$$
begin{align}
p-a &= x^2+3y^2 - (x^2-3y^2+2xy) = 6y^2-2xy = 2y(3y-x) > 0\
p-b &= x^2+3y^2 - (3y^2-x^2+2xy) = 2x^2-2xy = 2x(x-y) > 0
end{align}
$$
Therefore $0< a,b < p$.
This completes the proof.
$endgroup$
1. Solution to $p^2= X^2+3Y^2$
It is well known that $pequiv 1pmod 3$ if and only if
$$
p=x^2+3y^2
$$
for some integers $x,y$. So immediately we have a presentation of $p^2$ as
$$
begin{align}
p^2 &= (x^2+3y^2)^2\
&=(x+sqrt{-3}y)^2(x-sqrt{-3}y)^2\
&=((x^2-3y^2)+2xysqrt{-3})((x^2-3y^2)-2xysqrt{-3})\
&=(x^2-3y^2)^2+3(2xy)^2
end{align}
$$
2. Solution to $p^2=a^2+ab+b^2,quad 0leq a,b< p$
The expression $u^2+3v^2$ can be rewritten in the following three ways:
$$
begin{align}
u^2+3v^2 &= (pm u-v)^2 + (pm u-v)(2v) + (2v)^2\
u^2+3v^2 &= (u+v)^2 + (u+v)(-u+v) + (-u+v)^2
end{align}
$$
From (1), we have
$$
p^2 = (x^2-3y)^2 + 3(2xy)^2
$$
Therefore applying any of the three transformations will already give us
$$
p^2 = a^2 + ab+b^2
$$
We shall show that depending on whether $x<y$, $y<x<3y$ or $3y<x$, exactly one of the previous transformations will give us a solution such that $0leq a,b<p$. (Clearly $xneq y$ and $xneq 3y$, or $p$ is not prime.)
Case 2a: $x<y$
We use the transformation
$$
u^2+3v^2 = (-u-v)^2 + (-u-v)(2v) + (2v)^2
$$
Hence
$$
begin{align}
p^2 &= (x^2-3y^2)^2 + 3(2xy)^2\
&= (3y^2-x^2-2xy)^2 + (3y^2-x^2-2xy)(4xy) + (4xy)^2\
&= a^2+ab+b^2
end{align}
$$
Hence
$$
begin{align}
a &= 3y^2-x^2-2xy = (3y+x)(y-x)\
b &= 4xy
end{align}
$$
Since $0<x<y$, we get $0< a,b$. Next we check that
$$
begin{align}
p-a &= x^2+3y^2 - (3y^2-x^2-2xy) = 2x^2+2xy > 0\
p-b &= x^2+3y^2 - 4xy = (3y-x)(y-x) > 0
end{align}
$$
Therefore $0< a,b < p$.
Case 2b: $3y<x$
We use the transformation
$$
u^2+3v^2 = (u-v)^2 + (u-v)(2v) + (2v)^2
$$
Hence
$$
begin{align}
p^2 &= (x^2-3y^2)^2 + 3(2xy)^2\
&= (x^2-3y^2-2xy)^2 + (x^2-3y^2-2xy)(4xy) + (4xy)^2\
&= a^2+ab+b^2
end{align}
$$
Hence
$$
begin{align}
a &= x^2-3y^2-2xy = (x-3y)(x+y)\
b &= 4xy
end{align}
$$
Since $0<3y < x$, we get $0< a,b$. Next we check that
$$
begin{align}
p-a &= x^2+3y^2 - (x^2-3y^2-2xy) = 6y^2+2xy > 0\
p-b &= x^2+3y^2 - 4xy = (x-3y)(x-y) > 0
end{align}
$$
Therefore $0< a,b < p$.
Case 2c: $y<x<3y$
We use the transformation
$$
u^2+3v^2 = (u+v)^2 + (u+v)(-u+v) + (-u+v)^2
$$
Hence
$$
begin{align}
p^2 &= (x^2-3y^2)^2 + 3(2xy)^2\
&= (x^2-3y^2+2xy)^2 + (x^2-3y^2+2xy)(3y^2-x^2+2xy) + (3y^2-x^2+2xy)^2\
&= a^2+ab+b^2
end{align}
$$
Hence
$$
begin{align}
a &= x^2-3y^2+2xy = (x+3y)(x-y)\
b &= 3y^2-x^2+2xy = (3y-x)(y+x)
end{align}
$$
Since $y<x < 3y$, we get $0< a,b$. Next we check that
$$
begin{align}
p-a &= x^2+3y^2 - (x^2-3y^2+2xy) = 6y^2-2xy = 2y(3y-x) > 0\
p-b &= x^2+3y^2 - (3y^2-x^2+2xy) = 2x^2-2xy = 2x(x-y) > 0
end{align}
$$
Therefore $0< a,b < p$.
This completes the proof.
answered Jan 14 at 14:02
Yong Hao NgYong Hao Ng
3,5691222
3,5691222
add a comment |
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%2f3036675%2fprove-there-exist-postive-integers-a-b-such-p2a2abb2%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