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

Author

Lenny Jones, Mar 30 2014

Keywords

• nonn

Examples

			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).
		

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.

Programs

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 *)

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