cp's OEIS Frontend

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.

Number of solutions to gcd(x*y*z, n) = 1 such that 0 <= x,y,z <= n-1.

x*y*z == t (mod n) where t is a unit (invertible element) in Z_n. Since t is a unit, all x,y,z must be units. Here there are A000010(n) possibilities for each x,y,z so there are a total of A000010(n)^3 ways to get t as a unit.