A square modulo every prime is a square. Proof valid?
$begingroup$
As Eric Schneider asked, "Am I mistaken, or does the following (actually) elementary proof work?"
Theorem. Any integer which is a square modulo every prime is a square.
Lemma. For any odd prime $p$, any integer which is a square modulo $p$ is a square modulo every power of $p$.
Proof. Let $a$ be any square modulo $p$. Let $r$ be any integer $geqslant 1$. Use induction on $r$. (I adopt this approach to avoid a bug, spotted by Ingix, in my earlier proof.) The result is true for $r=1$. Suppose, by the inductive hypothesis, that $a$ is a square modulo $p^{r-1}$. Then $a=x^2mod p^{r-1}$ for some $x$.
Work modulo $p^r$. If $x=0$ then $a=0=0^2$ modulo $p^r$. Otherwise, for $0leqslant k<p$, $(kp^{r-1}+x)^2=jp^{r-1}+amod p^r$ for some $0leqslant j<p$.
Suppose two distinct $kp^{r-1}+x$ had the same square. Then
begin{align*}
(kp^{r-1}+x)^2&=(lp^{r-1}+x)^2mod p^rtag{ with $kne l$}\
(k^2-l^2)p^{2r-2}+2(k-l)p^{r-1}x&=0mod p^r\
2(k-l)p^{r-1}x&=0mod p^rtag{ as $r>1$}\
2(k-l)x&=0mod p
end{align*}
$p$ is an odd prime and $xne 0mod p$, so $pnmid 2x$, so the last line is false.
Therefore, by the pigeonhole principle, the values of the $p$ distinct expressions $(kp^{r-1}+x)^2$ for $0leqslant k<p$ are the values $jp^{r-1}+a$ for $0leqslant j<p$ in some order. In particular, in one case $j=0$, so $a$ is a square modulo $p^r$.
Proof of theorem. Let $a$ be a square modulo every prime. Then, by Lemma 1, $a$ is a square modulo every odd prime-power. Then, by the Chinese remainder theorem, $a$ is a square modulo every odd integer. Then, by Eric Schneider's argument, with $n=2$, but applying it only to $p$ being an odd prime and not to $p=2$, for every odd prime $p$, $p^r; ||;a$ for an even number $r$.
Thus either $a=x^2$ or $a=2x^2$ for some integer $x$. Let $p$ be a prime where $p=pm 3mod 8$. Then, modulo $p$, $a$ is a quadratic residue modulo $p$ by supposition, but 2 is not a quadratic residue, so $2a$ is not a quadratic residue, so $2a$ is not a square in $mathbb{Z}$. Thus for every integer $x$, $(2x)^2=4x^2ne 2a$, so $2x^2ne a$, so $a$ is a square, as required.
I see no elementary proof of this theorem, with no use of quadratic reciprocity (QR). I wonder if the above qualifies. Chan asked for a proof of this very result but that question was closed as a duplicate of a different question, viz the one where Eric Schneider's answer has been used above. There is Hagen von Eitzen's proof of a similar result, but that relies on QR. ArithmeticGeometer requested a proof without using QR, and the only answer is an advanced proof.
number-theory modular-arithmetic quadratic-residues
asked Jun 12 '18 at 7:48
Rosie FRosie F
1,379416
$endgroup$
|
show 4 more comments
$begingroup$
As Eric Schneider asked, "Am I mistaken, or does the following (actually) elementary proof work?"
Theorem. Any integer which is a square modulo every prime is a square.
Lemma. For any odd prime $p$, any integer which is a square modulo $p$ is a square modulo every power of $p$.
Proof. Let $a$ be any square modulo $p$. Let $r$ be any integer $geqslant 1$. Use induction on $r$. (I adopt this approach to avoid a bug, spotted by Ingix, in my earlier proof.) The result is true for $r=1$. Suppose, by the inductive hypothesis, that $a$ is a square modulo $p^{r-1}$. Then $a=x^2mod p^{r-1}$ for some $x$.
Work modulo $p^r$. If $x=0$ then $a=0=0^2$ modulo $p^r$. Otherwise, for $0leqslant k<p$, $(kp^{r-1}+x)^2=jp^{r-1}+amod p^r$ for some $0leqslant j<p$.
Suppose two distinct $kp^{r-1}+x$ had the same square. Then
begin{align*}
(kp^{r-1}+x)^2&=(lp^{r-1}+x)^2mod p^rtag{ with $kne l$}\
(k^2-l^2)p^{2r-2}+2(k-l)p^{r-1}x&=0mod p^r\
2(k-l)p^{r-1}x&=0mod p^rtag{ as $r>1$}\
2(k-l)x&=0mod p
end{align*}
$p$ is an odd prime and $xne 0mod p$, so $pnmid 2x$, so the last line is false.
Therefore, by the pigeonhole principle, the values of the $p$ distinct expressions $(kp^{r-1}+x)^2$ for $0leqslant k<p$ are the values $jp^{r-1}+a$ for $0leqslant j<p$ in some order. In particular, in one case $j=0$, so $a$ is a square modulo $p^r$.
Proof of theorem. Let $a$ be a square modulo every prime. Then, by Lemma 1, $a$ is a square modulo every odd prime-power. Then, by the Chinese remainder theorem, $a$ is a square modulo every odd integer. Then, by Eric Schneider's argument, with $n=2$, but applying it only to $p$ being an odd prime and not to $p=2$, for every odd prime $p$, $p^r; ||;a$ for an even number $r$.
Thus either $a=x^2$ or $a=2x^2$ for some integer $x$. Let $p$ be a prime where $p=pm 3mod 8$. Then, modulo $p$, $a$ is a quadratic residue modulo $p$ by supposition, but 2 is not a quadratic residue, so $2a$ is not a quadratic residue, so $2a$ is not a square in $mathbb{Z}$. Thus for every integer $x$, $(2x)^2=4x^2ne 2a$, so $2x^2ne a$, so $a$ is a square, as required.
I see no elementary proof of this theorem, with no use of quadratic reciprocity (QR). I wonder if the above qualifies. Chan asked for a proof of this very result but that question was closed as a duplicate of a different question, viz the one where Eric Schneider's answer has been used above. There is Hagen von Eitzen's proof of a similar result, but that relies on QR. ArithmeticGeometer requested a proof without using QR, and the only answer is an advanced proof.
number-theory modular-arithmetic quadratic-residues
asked Jun 12 '18 at 7:48
Rosie FRosie F
1,379416
$endgroup$
$begingroup$
Isn't this just a local-global principal?
$endgroup$
– quantum
Jun 12 '18 at 8:11
$begingroup$
@quantum Indeed, but what elementary proof is there of that?
$endgroup$
– Rosie F
Jun 12 '18 at 8:15
$begingroup$
Quadratic Reciprocity is generally considered to be elementary. It's in most elementary Number Theory textbooks, it requires no complex variables – what's not elementary about it?
$endgroup$
– Gerry Myerson
Jun 12 '18 at 8:53
1
$begingroup$
For different people elementary means different things, I certainly don't find the usual proofs of quadratic reciprocity elementary. For the OP, the first error I found (didn't look any further) is that you concluded from $k ne l$ that you could divide an equation by $(k-l)$ and still go from mod $p^{r-1}$ to mod $p^{r-1}$. If $k-l$ is a multiple of $p$, this is not valid.
$endgroup$
– Ingix
Jun 12 '18 at 9:26
2
$begingroup$
@DavidDiaz You have to take care to choose $p$. 7 is a square modulo each of 19, 29, 31, 37, 47, 53, 59.
$endgroup$
– Rosie F
Jun 14 '18 at 7:03
|
show 4 more comments
$begingroup$
As Eric Schneider asked, "Am I mistaken, or does the following (actually) elementary proof work?"
Theorem. Any integer which is a square modulo every prime is a square.
Lemma. For any odd prime $p$, any integer which is a square modulo $p$ is a square modulo every power of $p$.
Proof. Let $a$ be any square modulo $p$. Let $r$ be any integer $geqslant 1$. Use induction on $r$. (I adopt this approach to avoid a bug, spotted by Ingix, in my earlier proof.) The result is true for $r=1$. Suppose, by the inductive hypothesis, that $a$ is a square modulo $p^{r-1}$. Then $a=x^2mod p^{r-1}$ for some $x$.
Work modulo $p^r$. If $x=0$ then $a=0=0^2$ modulo $p^r$. Otherwise, for $0leqslant k<p$, $(kp^{r-1}+x)^2=jp^{r-1}+amod p^r$ for some $0leqslant j<p$.
Suppose two distinct $kp^{r-1}+x$ had the same square. Then
begin{align*}
(kp^{r-1}+x)^2&=(lp^{r-1}+x)^2mod p^rtag{ with $kne l$}\
(k^2-l^2)p^{2r-2}+2(k-l)p^{r-1}x&=0mod p^r\
2(k-l)p^{r-1}x&=0mod p^rtag{ as $r>1$}\
2(k-l)x&=0mod p
end{align*}
$p$ is an odd prime and $xne 0mod p$, so $pnmid 2x$, so the last line is false.
Therefore, by the pigeonhole principle, the values of the $p$ distinct expressions $(kp^{r-1}+x)^2$ for $0leqslant k<p$ are the values $jp^{r-1}+a$ for $0leqslant j<p$ in some order. In particular, in one case $j=0$, so $a$ is a square modulo $p^r$.
Proof of theorem. Let $a$ be a square modulo every prime. Then, by Lemma 1, $a$ is a square modulo every odd prime-power. Then, by the Chinese remainder theorem, $a$ is a square modulo every odd integer. Then, by Eric Schneider's argument, with $n=2$, but applying it only to $p$ being an odd prime and not to $p=2$, for every odd prime $p$, $p^r; ||;a$ for an even number $r$.
Thus either $a=x^2$ or $a=2x^2$ for some integer $x$. Let $p$ be a prime where $p=pm 3mod 8$. Then, modulo $p$, $a$ is a quadratic residue modulo $p$ by supposition, but 2 is not a quadratic residue, so $2a$ is not a quadratic residue, so $2a$ is not a square in $mathbb{Z}$. Thus for every integer $x$, $(2x)^2=4x^2ne 2a$, so $2x^2ne a$, so $a$ is a square, as required.
I see no elementary proof of this theorem, with no use of quadratic reciprocity (QR). I wonder if the above qualifies. Chan asked for a proof of this very result but that question was closed as a duplicate of a different question, viz the one where Eric Schneider's answer has been used above. There is Hagen von Eitzen's proof of a similar result, but that relies on QR. ArithmeticGeometer requested a proof without using QR, and the only answer is an advanced proof.
number-theory modular-arithmetic quadratic-residues
asked Jun 12 '18 at 7:48
Rosie FRosie F
1,379416
$endgroup$
As Eric Schneider asked, "Am I mistaken, or does the following (actually) elementary proof work?"
Theorem. Any integer which is a square modulo every prime is a square.
Lemma. For any odd prime $p$, any integer which is a square modulo $p$ is a square modulo every power of $p$.
Proof. Let $a$ be any square modulo $p$. Let $r$ be any integer $geqslant 1$. Use induction on $r$. (I adopt this approach to avoid a bug, spotted by Ingix, in my earlier proof.) The result is true for $r=1$. Suppose, by the inductive hypothesis, that $a$ is a square modulo $p^{r-1}$. Then $a=x^2mod p^{r-1}$ for some $x$.
Work modulo $p^r$. If $x=0$ then $a=0=0^2$ modulo $p^r$. Otherwise, for $0leqslant k<p$, $(kp^{r-1}+x)^2=jp^{r-1}+amod p^r$ for some $0leqslant j<p$.
Suppose two distinct $kp^{r-1}+x$ had the same square. Then
begin{align*}
(kp^{r-1}+x)^2&=(lp^{r-1}+x)^2mod p^rtag{ with $kne l$}\
(k^2-l^2)p^{2r-2}+2(k-l)p^{r-1}x&=0mod p^r\
2(k-l)p^{r-1}x&=0mod p^rtag{ as $r>1$}\
2(k-l)x&=0mod p
end{align*}
$p$ is an odd prime and $xne 0mod p$, so $pnmid 2x$, so the last line is false.
Therefore, by the pigeonhole principle, the values of the $p$ distinct expressions $(kp^{r-1}+x)^2$ for $0leqslant k<p$ are the values $jp^{r-1}+a$ for $0leqslant j<p$ in some order. In particular, in one case $j=0$, so $a$ is a square modulo $p^r$.
Proof of theorem. Let $a$ be a square modulo every prime. Then, by Lemma 1, $a$ is a square modulo every odd prime-power. Then, by the Chinese remainder theorem, $a$ is a square modulo every odd integer. Then, by Eric Schneider's argument, with $n=2$, but applying it only to $p$ being an odd prime and not to $p=2$, for every odd prime $p$, $p^r; ||;a$ for an even number $r$.
Thus either $a=x^2$ or $a=2x^2$ for some integer $x$. Let $p$ be a prime where $p=pm 3mod 8$. Then, modulo $p$, $a$ is a quadratic residue modulo $p$ by supposition, but 2 is not a quadratic residue, so $2a$ is not a quadratic residue, so $2a$ is not a square in $mathbb{Z}$. Thus for every integer $x$, $(2x)^2=4x^2ne 2a$, so $2x^2ne a$, so $a$ is a square, as required.
I see no elementary proof of this theorem, with no use of quadratic reciprocity (QR). I wonder if the above qualifies. Chan asked for a proof of this very result but that question was closed as a duplicate of a different question, viz the one where Eric Schneider's answer has been used above. There is Hagen von Eitzen's proof of a similar result, but that relies on QR. ArithmeticGeometer requested a proof without using QR, and the only answer is an advanced proof.
number-theory modular-arithmetic quadratic-residues
number-theory modular-arithmetic quadratic-residues
asked Jun 12 '18 at 7:48
Rosie FRosie F
1,379416
asked Jun 12 '18 at 7:48
Rosie FRosie F
1,379416
edited Jan 13 at 17:13
Rosie F
asked Jun 12 '18 at 7:48
Rosie FRosie F
1,379416
asked Jun 12 '18 at 7:48
Rosie FRosie F
1,379416
asked Jun 12 '18 at 7:48
Rosie FRosie F
1,379416
1,379416
$begingroup$
Isn't this just a local-global principal?
$endgroup$
– quantum
Jun 12 '18 at 8:11
$begingroup$
@quantum Indeed, but what elementary proof is there of that?
$endgroup$
– Rosie F
Jun 12 '18 at 8:15
$begingroup$
Quadratic Reciprocity is generally considered to be elementary. It's in most elementary Number Theory textbooks, it requires no complex variables – what's not elementary about it?
$endgroup$
– Gerry Myerson
Jun 12 '18 at 8:53
1
$begingroup$
For different people elementary means different things, I certainly don't find the usual proofs of quadratic reciprocity elementary. For the OP, the first error I found (didn't look any further) is that you concluded from $k ne l$ that you could divide an equation by $(k-l)$ and still go from mod $p^{r-1}$ to mod $p^{r-1}$. If $k-l$ is a multiple of $p$, this is not valid.
$endgroup$
– Ingix
Jun 12 '18 at 9:26
2
$begingroup$
@DavidDiaz You have to take care to choose $p$. 7 is a square modulo each of 19, 29, 31, 37, 47, 53, 59.
$endgroup$
– Rosie F
Jun 14 '18 at 7:03
|
show 4 more comments
$begingroup$
Isn't this just a local-global principal?
$endgroup$
– quantum
Jun 12 '18 at 8:11
$begingroup$
@quantum Indeed, but what elementary proof is there of that?
$endgroup$
– Rosie F
Jun 12 '18 at 8:15
$begingroup$
Quadratic Reciprocity is generally considered to be elementary. It's in most elementary Number Theory textbooks, it requires no complex variables – what's not elementary about it?
$endgroup$
– Gerry Myerson
Jun 12 '18 at 8:53
1
$begingroup$
For different people elementary means different things, I certainly don't find the usual proofs of quadratic reciprocity elementary. For the OP, the first error I found (didn't look any further) is that you concluded from $k ne l$ that you could divide an equation by $(k-l)$ and still go from mod $p^{r-1}$ to mod $p^{r-1}$. If $k-l$ is a multiple of $p$, this is not valid.
$endgroup$
– Ingix
Jun 12 '18 at 9:26
2
$begingroup$
@DavidDiaz You have to take care to choose $p$. 7 is a square modulo each of 19, 29, 31, 37, 47, 53, 59.
$endgroup$
– Rosie F
Jun 14 '18 at 7:03
$begingroup$
Isn't this just a local-global principal?
$endgroup$
– quantum
Jun 12 '18 at 8:11
$begingroup$
Isn't this just a local-global principal?
$endgroup$
– quantum
Jun 12 '18 at 8:11
$begingroup$
@quantum Indeed, but what elementary proof is there of that?
$endgroup$
– Rosie F
Jun 12 '18 at 8:15
$begingroup$
@quantum Indeed, but what elementary proof is there of that?
$endgroup$
– Rosie F
Jun 12 '18 at 8:15
$begingroup$
Quadratic Reciprocity is generally considered to be elementary. It's in most elementary Number Theory textbooks, it requires no complex variables – what's not elementary about it?
$endgroup$
– Gerry Myerson
Jun 12 '18 at 8:53
$begingroup$
Quadratic Reciprocity is generally considered to be elementary. It's in most elementary Number Theory textbooks, it requires no complex variables – what's not elementary about it?
$endgroup$
– Gerry Myerson
Jun 12 '18 at 8:53
1
1
$begingroup$
For different people elementary means different things, I certainly don't find the usual proofs of quadratic reciprocity elementary. For the OP, the first error I found (didn't look any further) is that you concluded from $k ne l$ that you could divide an equation by $(k-l)$ and still go from mod $p^{r-1}$ to mod $p^{r-1}$. If $k-l$ is a multiple of $p$, this is not valid.
$endgroup$
– Ingix
Jun 12 '18 at 9:26
$begingroup$
For different people elementary means different things, I certainly don't find the usual proofs of quadratic reciprocity elementary. For the OP, the first error I found (didn't look any further) is that you concluded from $k ne l$ that you could divide an equation by $(k-l)$ and still go from mod $p^{r-1}$ to mod $p^{r-1}$. If $k-l$ is a multiple of $p$, this is not valid.
$endgroup$
– Ingix
Jun 12 '18 at 9:26
2
2
$begingroup$
@DavidDiaz You have to take care to choose $p$. 7 is a square modulo each of 19, 29, 31, 37, 47, 53, 59.
$endgroup$
– Rosie F
Jun 14 '18 at 7:03
$begingroup$
@DavidDiaz You have to take care to choose $p$. 7 is a square modulo each of 19, 29, 31, 37, 47, 53, 59.
$endgroup$
– Rosie F
Jun 14 '18 at 7:03
|
show 4 more comments
0
active
oldest
votes
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%2f2816644%2fa-square-modulo-every-prime-is-a-square-proof-valid%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f2816644%2fa-square-modulo-every-prime-is-a-square-proof-valid%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
$begingroup$
Isn't this just a local-global principal?
$endgroup$
– quantum
Jun 12 '18 at 8:11
$begingroup$
@quantum Indeed, but what elementary proof is there of that?
$endgroup$
– Rosie F
Jun 12 '18 at 8:15
$begingroup$
Quadratic Reciprocity is generally considered to be elementary. It's in most elementary Number Theory textbooks, it requires no complex variables – what's not elementary about it?
$endgroup$
– Gerry Myerson
Jun 12 '18 at 8:53
1
$begingroup$
For different people elementary means different things, I certainly don't find the usual proofs of quadratic reciprocity elementary. For the OP, the first error I found (didn't look any further) is that you concluded from $k ne l$ that you could divide an equation by $(k-l)$ and still go from mod $p^{r-1}$ to mod $p^{r-1}$. If $k-l$ is a multiple of $p$, this is not valid.
$endgroup$
– Ingix
Jun 12 '18 at 9:26
2
$begingroup$
@DavidDiaz You have to take care to choose $p$. 7 is a square modulo each of 19, 29, 31, 37, 47, 53, 59.
$endgroup$
– Rosie F
Jun 14 '18 at 7:03