A360323 a(n) is the number of solutions to gcd(a^2 + b^2, p) = 1 where p is the n-th prime and 0 <= a,b <= p-1.

2, 8, 16, 48, 120, 144, 256, 360, 528, 784, 960, 1296, 1600, 1848, 2208, 2704, 3480, 3600, 4488, 5040, 5184, 6240, 6888, 7744, 9216, 10000, 10608, 11448, 11664, 12544, 16128, 17160, 18496, 19320, 21904, 22800, 24336, 26568, 27888, 29584, 32040, 32400, 36480

Offset: 1

Author

Paavan Mayurkumar Parekh and Param Mayurkumar Parekh, Feb 03 2023

Keywords

• nonn

Comments

The prime numbers can be divided into 3 classes as follows, where 0 <= a,b <= p-1.

1. p = 2: The solutions are (0,1), (1,0).

2. p == 1 (mod 4): The number of solutions = p^2 - (number of solutions to a^2 + b^2 == 0 (mod p)). These primes can be written as the sum of two squares, so p = a^2 + b^2 == 0 (mod p). Hence, the number of possible values of (a,b) such that a^2 + b^2 == 0 (mod p) is 2*p - 1, so the final answer is p^2 - (2*p - 1) = (p-1)^2.

3. p == 3 (mod 4): These primes can't be written as the sum of two squares, so the number of possible values of (a,b) such that a^2 + b^2 == 0 (mod p) is 1 (that is, (0,0) only). Hence, the number of solutions for this case is p^2 - 1.

Examples

			a(2) = A079458(A000040(2)) = A079458(3) = 8.
		

Crossrefs

Cf. A000040, A079458.

Formula

a(n) = A079458(A000040(n)).