I have been using PARI-GP to find the squares of a prime number. For example
for(JJ=0,7,print1(JJ^2%8"\t"))
in PARI gives
0 1 4 1 0 1 4 1
from which I know that the squares modulo 8 are 1 and 4. Now that I need to find the squares modulo large prime, I was wondering is there a way SAGE can give me a complete list without repeating the values.
This answer sort of cheats, but:
sage: p = 17
sage: quadratic_residues(p)
[0, 1, 2, 4, 8, 9, 13, 15, 16]
This is, after all, a well-known concept.
This works for your example too, even though 8 isn't prime
sage: quadratic_residues?
Signature: quadratic_residues(n)
Docstring:
Return a sorted list of all squares modulo the integer n in the
range 0<= x < |n|.
Given that $(n + p)^2 = n^2 + 2np + p^2 = n^2 \mbox{ mod } p$, you just have to compute the numbers $n^2 \mbox{ mod } p$ for all integers between $0$ and $p-1$. If you want to avoid repetitions, you just have to put them in a set. Here is how:
sage: p = 17
sage: S = {n^2 % p for n in range(p)}
sage: S
{0, 1, 2, 4, 8, 9, 13, 15, 16}
sage: p = 123457
sage: S = {n^2 % p for n in range(p)}
sage: len(S)
61729
Sorry, I thought you were somehow getting True or False. You would want to look for n such that it was not in this list. Anyway, an easier way to do this with Thierry's syntax is just set(range(p)).difference(S). You need the set because then you get set difference.
Asked: 2016-09-05 11:07:55 +0200
Seen: 500 times
Last updated: Sep 13 '16
Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
