login
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.
0
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.
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
Sequence in context: A323351 A134353 A280229 * A336127 A076508 A162584
KEYWORD
nonn
STATUS
approved