A319099 Number of solutions to x^5 == 1 (mod n).

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 1, 1, 5, 1, 1, 1, 1, 1, 5, 1, 5, 1, 1, 1, 1, 1, 1, 1, 5, 1, 1, 5, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1, 5, 5, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, 5, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1

Offset: 1

Author

Jianing Song, Sep 10 2018

Keywords

• nonn
• easy
• mult

Comments

All terms are powers of 5. Those n such that a(n) > 1 are in A066500.

Examples

			Solutions to x^5 == 1 (mod 11): x == 1, 3, 4, 5, 9 (mod 11).
Solutions to x^5 == 1 (mod 25): x == 1, 6, 11, 16, 21 (mod 25) (x == 1 (mod 5)).
Solutions to x^5 == 1 (mod 31): x == 1, 2, 4, 8, 16 (mod 31).
		

Links

• Jianing Song, Table of n, a(n) for n = 1..10000

Crossrefs

Number of solutions to x^k == 1 (mod n): A060594 (k=2), A060839 (k=3), A073103 (k=4), this sequence (k=5), A319100 (k=6), A319101 (k=7), A247257 (k=8).

Cf. A030430, A066500, A293482, A000010.

Mobius transform gives A307380.

Programs

Mathematica

f[p_, e_] := If[Mod[p, 5] == 1, 5, 1]; f[5, 1] = 1; f[5, e_] := 5; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Aug 10 2023 *)

PARI

a(n)=my(Z=znstar(n)[2]); prod(i=1,#Z,gcd(5,Z[i]));

Formula

Multiplicative with a(5) = 1, a(5^e) = 5 if e >= 2; for other primes p, a(p^e) = 5 if p == 1 (mod 5), a(p^e) = 1 otherwise.

If the multiplicative group of integers modulo n is isomorphic to C_{k_1} x C_{k_2} x ... x C_{k_m}, where k_i divides k_j for i < j; then a(n) = Product_{i=1..m} gcd(5, k_i).

a(n) = A000010(n)/A293482(n). - Jianing Song, Nov 10 2019