A240109 Positive integers n such that every element in the ring of integers modulo n can be written as the sum of two nonzero squares modulo n.

10, 13, 17, 26, 29, 30, 34, 37, 39, 41, 50, 51, 53, 58, 61, 65, 70, 73, 74, 78, 82, 85, 87, 89, 91, 97, 101, 102, 106, 109, 110, 111, 113, 119, 122, 123, 125, 130, 137, 143, 145, 146, 149, 150, 157, 159, 169, 170, 173, 174, 178, 181, 182, 183, 185, 187, 190, 193, 194, 195, 197

Offset

1,1

Links

Giovanni Resta and Charles R Greathouse IV, Table of n, a(n) for n = 1..10000 (first 5000 terms from Giovanni Resta)

Joshua Harrington, Lenny Jones, and Alicia Lamarche, Representing integers as the sum of two squares in the ring Z_n, arXiv:1404.0187 (2014) and J. Int. Seq. 17 (2014) # 14.7.4.

Example

13 is a member since 0=1^2+5^2, 1=2^2+6^2, 2=1^2+1^2, 3=2^2+5^2, 4=1^2+4^2, 5=1^2+2^2, 6=3^2+6^2, 7=2^2+4^2, 8=2^2+2^2, 9=5^2+6^2, 10=1^2+3^2, 11=1^2+6^2, and 12=3^2+4^2 mod 13.
5 is not a member since there are no nonzero x and y such that x^2 + y^2 = 4 (mod 5).

Mathematica

ok[n_] := Block[{t = Union@ Select[Mod[ Range[n]^2, n], # > 0 &], f = Range[n] 0}, Do[ f[[1 + Mod[t[[i]] + t[[j]], n]]]++, {i, Length@t}, {j, i}]; Position[f, 0] == {}]; Select[Range[2, 200], ok] (* Giovanni Resta, Apr 01 2014 *)

Prog

(PARI) is(n)=my(f=factor(n), P=#select(k->k%4==1, f[, 1])); if(P==0, return(0)); for(i=1, #f~, if(f[i, 2]>1 && f[i, 1]%4>1, return(0))); P>1 || n%2==0 || n%5 || n%125==0 \\ Charles R Greathouse IV, Apr 04 2014

Crossrefs

Sequence in context: A339077 A373278 A335016 * A163652 A081642 A174274

Adjacent sequences: A240106 A240107 A240108 * A240110 A240111 A240112

Keyword

nonn

Author

Lenny Jones, Mar 30 2014

Status

approved