A227781 Least number of squares which add to -1 mod n.

0, 1, 2, 3, 1, 2, 2, 4, 2, 1, 2, 3, 1, 2, 2, 4, 1, 2, 2, 3, 2, 2, 2, 4, 1, 1, 2, 3, 1, 2, 2, 4, 2, 1, 2, 3, 1, 2, 2, 4, 1, 2, 2, 3, 2, 2, 2, 4, 2, 1, 2, 3, 1, 2, 2, 4, 2, 1, 2, 3, 1, 2, 2, 4, 1, 2, 2, 3, 2, 2, 2, 4, 1, 1, 2, 3, 2, 2, 2, 4, 2, 1, 2, 3, 1, 2, 2, 4, 1, 2, 2, 3, 2, 2

Offset

1,3

Comments

Pfister proved that a(p) <= 2 for all primes p; then a(p) is called the stufe of the field Z/pZ.

Conjecture: a(n) = 4 if and only if n is divisible by 8 and a(n) = 3 if and only if n is 4 mod 8. Together with A008784 this would completely define the sequence.

References

Albert Pfister, Zur Darstellung von -1 Als Summe von Quadraten in einem Korper, J. London Math. Society, 40 (1965), pp. 159-165.

A. R. Rajwade, Squares, Cambridge Univ. Press, 1983.

Links

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Formula

a(n) <= A002828(n-1) <= 4.

a(n) = 1 if and only if n > 1 is in A008784. a(4n) >= 3 for all n.

Example

a(3) = 2: 1^2 + 1^2 = -1 mod 3.
a(15) = 2: 2^2 + 5^2 = -1 mod 15.

Prog

(PARI) isA008784(n)=if(n%2==0, if(n%4, n/=2, return(0))); n==1||vecmax(factor(n)[, 1]%4)==1
a(n)=if(isA008784(n), return(n>1)); if(isprime(n), return(2)); if(n%8==0, return(4)); my(N, cur, new, k=1); for(i=1, n\2, cur=N=bitor(1<<(i^2%n), N)); while(!bittest(cur, n-1), new=0; for(i=1, n\2, t=cur<<(i^2%n); t=bitor(bitand(t, (1<<n)-1), t>>n); new=bitor(new, t)); k++; cur=new); k

Crossrefs

Cf. A008784, A002828.

Sequence in context: A358638 A236855 A244232 * A366294 A351441 A254761

Adjacent sequences: A227778 A227779 A227780 * A227782 A227783 A227784

Keyword

nonn

Author

Charles R Greathouse IV, Jul 31 2013

Status

approved