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.
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
KEYWORD
nonn
AUTHOR
Paavan Mayurkumar Parekh and Param Mayurkumar Parekh, Feb 03 2023
STATUS
approved