A105612 Number of nonzero quadratic residues (mod n) (cf. A000224).

0, 1, 1, 1, 2, 3, 3, 2, 3, 5, 5, 3, 6, 7, 5, 3, 8, 7, 9, 5, 7, 11, 11, 5, 10, 13, 10, 7, 14, 11, 15, 6, 11, 17, 11, 7, 18, 19, 13, 8, 20, 15, 21, 11, 11, 23, 23, 7, 21, 21, 17, 13, 26, 21, 17, 11, 19, 29, 29, 11, 30, 31, 15, 11, 20, 23, 33, 17, 23, 23, 35, 11, 36, 37, 21, 19, 23

Offset: 1

Author

Eric W. Weisstein, Apr 15 2005

Keywords

• nonn

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
• S. R. Finch and Pascal Sebah, Squares and Cubes Modulo n, arXiv:math/0604465 [math.NT], 2006-2016.
• E. J. F. Primrose, The number of quadratic residues mod m, Math. Gaz. v. 61 (1977) n. 415, 60-61.
• W. D. Stangl, Counting Squares in Z_n, Mathematics Magazine, pp. 285-289, Vol. 69 No. 4 (October 1996).
• Eric Weisstein's World of Mathematics, Quadratic Residue

Programs

Haskell

a105612 = (subtract 1) . a000224  -- Reinhard Zumkeller, Aug 01 2012

Mathematica

a[n_]:=Count[Union[Mod[Range[Floor[n/2]]^2,n]],?Positive];Table[a[n],{n,1,80}] (* _Jean-François Alcover,  Feb 09 2011 *)

PARI

/* based on code by Franklin T. Adams-Watters, see A000224 */
A105612(n)=local(v,i);v=vector(n,i,0);for(i=0,floor(n/2),v[i^2%n+1]=1);sum(i=2,n,v[i]) \\ Michael B. Porter, May 04 2010

PARI

a(n)=my(f=factor(n)); prod(i=1, #f[, 1], if(f[i, 1]==2, 2^f[1, 2]\6+2, f[i, 1]^(f[i, 2]+1)\(2*f[i, 1]+2)+1))-1 \\ Charles R Greathouse IV, Sep 10 2013

Formula

a(n) = A000224(n) - 1.

If p is an odd prime, then a(p) = (p - 1)/2. - Thomas Ordowski, Apr 09 2025