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,1

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.

Links

Table of n, a(n) for n=1..43.

Formula

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

Example

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

Prog

(C++)
#include <bits/stdc++.h>
using namespace std;
bool isPrime(int n)
{
    if (n <= 1)
        return false;
    for (int i = 2; i < n; i++)
        if (n % i == 0)
            return false;
    return true;
}
int main()
{
    for (int p = 1; p <= 100; p++)
    {
        if (isPrime(p)){
            if(p%4 == 1) cout<< (p-1)*(p-1) << endl;
            else if(p%4==3) cout<< (p*p - 1) << endl;
            else cout << 2 << endl; // when p = 2
        }
    }
}

Crossrefs

Cf. A000040, A079458.

Sequence in context: A323351 A134353 A280229 * A336127 A076508 A162584

Adjacent sequences: A360320 A360321 A360322 * A360324 A360325 A360326

Keyword

nonn

Author

Paavan Mayurkumar Parekh and Param Mayurkumar Parekh, Feb 03 2023

Status

approved