|
|
A046073
|
|
Number of squares in multiplicative group modulo n.
|
|
23
|
|
|
1, 1, 1, 1, 2, 1, 3, 1, 3, 2, 5, 1, 6, 3, 2, 2, 8, 3, 9, 2, 3, 5, 11, 1, 10, 6, 9, 3, 14, 2, 15, 4, 5, 8, 6, 3, 18, 9, 6, 2, 20, 3, 21, 5, 6, 11, 23, 2, 21, 10, 8, 6, 26, 9, 10, 3, 9, 14, 29, 2, 30, 15, 9, 8, 12, 5, 33, 8, 11, 6, 35, 3, 36, 18, 10, 9, 15, 6, 39, 4, 27, 20, 41, 3, 16, 21
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,5
|
|
COMMENTS
|
a(n) is the number of different diagonal elements in Cayley table for multiplicative group modulo n. But the fact that the same number of different elements are on the diagonal of the Cayley table does not mean in every case that these groups are isomorphic. - Artur Jasinski, Jul 03 2010
The number of quadratic residues modulo n that are coprime to n. These residues are listed in A096103. - Peter Munn, Mar 10 2021
|
|
REFERENCES
|
Daniel Shanks, Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, p. 95, 1993.
|
|
LINKS
|
|
|
FORMULA
|
a(n) * A060594(n) = A000010(n) = phi(n) (This gives a formula for a(n) using the one in A060594(n) ). - Sharon Sela (sharonsela(AT)hotmail.com), Mar 09 2002
Multiplicative with a(2^e) = 2^max(e-3,0), a(p^e) = (p-1)*p^(e-1)/2 for p an odd prime.
Sum_{k=1..n} a(k) ~ c * n^2/sqrt(log(n)), where c = (43/(80*sqrt(Pi))) * Product_{p prime} (1+1/(2*p))*sqrt(1-1/p) = 0.24627260085060864229... (Finch and Sebah, 2006). - Amiram Eldar, Oct 18 2022
|
|
MAPLE
|
F:= n -> nops({seq}(`if`(igcd(t, n)=1, t^2 mod n, NULL), t=1..floor(n/2))):
# 2nd program
local a, p, e, pf;
a := 1;
for pf in ifactors(n)[2] do
p := op(1, pf) ;
e := op(2, pf) ;
if p = 2 then
a := a*p^max(e-3, 0) ;
else
a := a*(p-1)/2*p^(e-1) ;
end if;
end do:
a ;
|
|
MATHEMATICA
|
Table[EulerPhi[n]/Sum[Boole[Mod[k^2, n] == 1] + Boole[n == 1], {k, n}], {n, 86}] (* or *)
Table[Apply[Times, FactorInteger[n] /. {p_, e_} /; p > 0 :> Which[p == 1, 1, p == 2, 2^Max[e - 3, 0], True, (p - 1) p^(e - 1)/2]], {n, 86}] (* Michael De Vlieger, Jul 18 2017 *)
|
|
PROG
|
(PARI)
(PARI) A046073(n)=if(n>4, (n=znstar(n))[1]>>#n[3], 1) \\ Avoids duplicate computation of phi(n). - M. F. Hasler, Nov 27 2017, typo fixed Mar 11 2021
(Python)
from sympy import factorint, prod
def a(n): return 1 if n==1 else prod([2**max(e - 3, 0) if p==2 else (p - 1)*p**(e - 1)//2 for p, e in factorint(n).items()])
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy,mult
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|