[math-fun] Integers that are squares mod p for all p
I’m pretty sure that a positive integer n that is a square mod p^k for all prime powers p^k must be a square in Q (as a consequence of the local-to-global principle for quadratic forms), from which it follows that n must be a square in Z. But what if all we know is that n is a square mod p for every prime p? And what if we don’t know that n is positive? This question was raised by Alaric Stephen ( https://aperiodical.com/2019/07/the-big-internet-math-off-2019-group-1-alex-... ). Jim Propp
There’s something called Henkel lifting that takes roots of equations mod p and turns them into roots mod p^k… does that help? - Cris
On Jul 17, 2019, at 2:43 PM, James Propp <jamespropp@gmail.com> wrote:
I’m pretty sure that a positive integer n that is a square mod p^k for all prime powers p^k must be a square in Q (as a consequence of the local-to-global principle for quadratic forms), from which it follows that n must be a square in Z.
But what if all we know is that n is a square mod p for every prime p? And what if we don’t know that n is positive?
This question was raised by Alaric Stephen ( https://aperiodical.com/2019/07/the-big-internet-math-off-2019-group-1-alex-... ).
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
That might be relevant. Note however that not every n that's a square mod p and mod p^2 is also a square mod p^3 (consider n=5, p=2). Jim On Wed, Jul 17, 2019 at 4:51 PM Cris Moore <moore@santafe.edu> wrote:
There’s something called Henkel lifting that takes roots of equations mod p and turns them into roots mod p^k… does that help? - Cris
On Jul 17, 2019, at 2:43 PM, James Propp <jamespropp@gmail.com> wrote:
I’m pretty sure that a positive integer n that is a square mod p^k for all prime powers p^k must be a square in Q (as a consequence of the local-to-global principle for quadratic forms), from which it follows that n must be a square in Z.
But what if all we know is that n is a square mod p for every prime p? And what if we don’t know that n is positive?
This question was raised by Alaric Stephen (
https://aperiodical.com/2019/07/the-big-internet-math-off-2019-group-1-alex-...
).
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
This is a classic result (and it's "Hensel", not "Henkel"). You can find it in many elementary number theory books. Googling I found https://math.stackexchange.com/questions/646094/is-every-non-square-integer-... https://math.stackexchange.com/questions/1009090/if-a-is-a-quadratic-residue... for example. On 7/17/19 5:13 PM, James Propp wrote:
That might be relevant. Note however that not every n that's a square mod p and mod p^2 is also a square mod p^3 (consider n=5, p=2).
Jim
On Wed, Jul 17, 2019 at 4:51 PM Cris Moore <moore@santafe.edu> wrote:
There’s something called Henkel lifting that takes roots of equations mod p and turns them into roots mod p^k… does that help? - Cris
On Jul 17, 2019, at 2:43 PM, James Propp <jamespropp@gmail.com> wrote:
I’m pretty sure that a positive integer n that is a square mod p^k for all prime powers p^k must be a square in Q (as a consequence of the local-to-global principle for quadratic forms), from which it follows that n must be a square in Z.
But what if all we know is that n is a square mod p for every prime p? And what if we don’t know that n is positive?
This question was raised by Alaric Stephen (
https://aperiodical.com/2019/07/the-big-internet-math-off-2019-group-1-alex-...
).
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I fear that I'm misunderstanding something. We are looking for an integer whose remainder, when divided by any prime, yields a square? Are there any positive examples besides 0, 1, and 4? I think any such would have to be a square itself (because it's its own modulus when divided by primes that exceed it). 16 is 2 mod 7 25 is 3 mod 11 36 is 3 mod 11 49 is 5 mod 11 81 is 3 mod 13 100 is 2 mod 7 121 is 2 mod 7 144 is 8 mod 17 As we get higher, it looks like the conditions get more and more stringent -- at this point I'd bet that there were no more examples. On Wed, Jul 17, 2019 at 5:32 PM Jeffrey Shallit <shallit@uwaterloo.ca> wrote:
This is a classic result (and it's "Hensel", not "Henkel").
You can find it in many elementary number theory books. Googling I found
https://math.stackexchange.com/questions/646094/is-every-non-square-integer-...
https://math.stackexchange.com/questions/1009090/if-a-is-a-quadratic-residue...
for example.
On 7/17/19 5:13 PM, James Propp wrote:
That might be relevant. Note however that not every n that's a square mod p and mod p^2 is also a square mod p^3 (consider n=5, p=2).
Jim
On Wed, Jul 17, 2019 at 4:51 PM Cris Moore <moore@santafe.edu> wrote:
There’s something called Henkel lifting that takes roots of equations
mod
p and turns them into roots mod p^k… does that help? - Cris
On Jul 17, 2019, at 2:43 PM, James Propp <jamespropp@gmail.com> wrote:
I’m pretty sure that a positive integer n that is a square mod p^k for all prime powers p^k must be a square in Q (as a consequence of the local-to-global principle for quadratic forms), from which it follows that n must be a square in Z.
But what if all we know is that n is a square mod p for every prime p? And what if we don’t know that n is positive?
This question was raised by Alaric Stephen (
https://aperiodical.com/2019/07/the-big-internet-math-off-2019-group-1-alex-...
).
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Jeffrey Shallit pointed out privately that I had indeed misunderstood the question. The intended requirement is that n be a square in the group Zp, not that it be a square in Z. Thank you for the clarification! On Wed, Jul 17, 2019, 6:27 PM Allan Wechsler <acwacw@gmail.com> wrote:
I fear that I'm misunderstanding something. We are looking for an integer whose remainder, when divided by any prime, yields a square?
Are there any positive examples besides 0, 1, and 4? I think any such would have to be a square itself (because it's its own modulus when divided by primes that exceed it).
16 is 2 mod 7 25 is 3 mod 11 36 is 3 mod 11 49 is 5 mod 11 81 is 3 mod 13 100 is 2 mod 7 121 is 2 mod 7 144 is 8 mod 17
As we get higher, it looks like the conditions get more and more stringent -- at this point I'd bet that there were no more examples.
On Wed, Jul 17, 2019 at 5:32 PM Jeffrey Shallit <shallit@uwaterloo.ca> wrote:
This is a classic result (and it's "Hensel", not "Henkel").
You can find it in many elementary number theory books. Googling I found
https://math.stackexchange.com/questions/646094/is-every-non-square-integer-...
https://math.stackexchange.com/questions/1009090/if-a-is-a-quadratic-residue...
for example.
On 7/17/19 5:13 PM, James Propp wrote:
That might be relevant. Note however that not every n that's a square mod p and mod p^2 is also a square mod p^3 (consider n=5, p=2).
Jim
On Wed, Jul 17, 2019 at 4:51 PM Cris Moore <moore@santafe.edu> wrote:
There’s something called Henkel lifting that takes roots of equations
mod
p and turns them into roots mod p^k… does that help? - Cris
On Jul 17, 2019, at 2:43 PM, James Propp <jamespropp@gmail.com> wrote:
I’m pretty sure that a positive integer n that is a square mod p^k for all prime powers p^k must be a square in Q (as a consequence of the local-to-global principle for quadratic forms), from which it follows that n must be a square in Z.
But what if all we know is that n is a square mod p for every prime p? And what if we don’t know that n is positive?
This question was raised by Alaric Stephen (
https://aperiodical.com/2019/07/the-big-internet-math-off-2019-group-1-alex-...
).
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
Allan Wechsler -
Cris Moore -
James Propp -
Jeffrey Shallit