cp's OEIS Frontend

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.

%I A360323 #25 Feb 16 2023 05:30:58
%S A360323 2,8,16,48,120,144,256,360,528,784,960,1296,1600,1848,2208,2704,3480,
%T A360323 3600,4488,5040,5184,6240,6888,7744,9216,10000,10608,11448,11664,
%U A360323 12544,16128,17160,18496,19320,21904,22800,24336,26568,27888,29584,32040,32400,36480
%N 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.
%C A360323 The prime numbers can be divided into 3 classes as follows, where 0 <= a,b <= p-1.
%C A360323 1. p = 2: The solutions are (0,1), (1,0).
%C A360323 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.
%C A360323 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.
%F A360323 a(n) = A079458(A000040(n)).
%e A360323 a(2) = A079458(A000040(2)) = A079458(3) = 8.
%o A360323 (C++)
%o A360323 #include <bits/stdc++.h>
%o A360323 using namespace std;
%o A360323 bool isPrime(int n)
%o A360323 {
%o A360323     if (n <= 1)
%o A360323         return false;
%o A360323     for (int i = 2; i < n; i++)
%o A360323         if (n % i == 0)
%o A360323             return false;
%o A360323     return true;
%o A360323 }
%o A360323 int main()
%o A360323 {
%o A360323     for (int p = 1; p <= 100; p++)
%o A360323     {
%o A360323         if (isPrime(p)){
%o A360323             if(p%4 == 1) cout<< (p-1)*(p-1) << endl;
%o A360323             else if(p%4==3) cout<< (p*p - 1) << endl;
%o A360323             else cout << 2 << endl; // when p = 2
%o A360323         }
%o A360323     }
%o A360323 }
%Y A360323 Cf. A000040, A079458.
%K A360323 nonn
%O A360323 1,1
%A A360323 _Paavan Mayurkumar Parekh_ and _Param Mayurkumar Parekh_, Feb 03 2023