|
%I #14 Feb 28 2018 14:56:11
%S 10,13,17,26,29,30,34,37,39,41,50,51,53,58,61,65,70,73,74,78,82,85,87,
%T 89,91,97,101,102,106,109,110,111,113,119,122,123,125,130,137,143,145,
%U 146,149,150,157,159,169,170,173,174,178,181,182,183,185,187,190,193,194,195,197
%N 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.
%H Giovanni Resta and Charles R Greathouse IV, <a href="/A240109/b240109.txt">Table of n, a(n) for n = 1..10000</a> (first 5000 terms from Giovanni Resta)
%H Joshua Harrington, Lenny Jones, and Alicia Lamarche, <a href="http://arxiv.org/abs/1404.0187">Representing integers as the sum of two squares in the ring Z_n</a>, arXiv:1404.0187 (2014) and <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Jones/jones14.html">J. Int. Seq. 17 (2014) # 14.7.4</a>.
%e 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.
%e 5 is not a member since there are no nonzero x and y such that x^2 + y^2 = 4 (mod 5).
%t 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 *)
%o (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
%K nonn
%O 1,1
%A _Lenny Jones_, Mar 30 2014
|
