# Confirmation of Proof: $\forall n \in \mathbb{N}^*, \ p = 4261 + 2308n : \text{prime} \Rightarrow p = \{a^2 + b^2 \mid \gcd(a, b) = 1\}$

I developed a conjecture which I would like to confirm whether or not it holds truth for all members $n$ of the set of $\mathbb{N}^* = \mathbb{N} \ \cup \ \{0\}$.

$$\forall n \in \mathbb{N}^*, \ p = 4261 + 2308n : \text{prime} \Rightarrow p = \{a^2 + b^2 \mid \gcd(a, b) = 1\}$$

This statement holds truth for $n \in \{0, 1, 9, 12, 16, 25, 37, 39, 40, 42, 49, 52, 66,\ldots, 2^{232} - 1\}$. I do not know if the statement holds truth for higher values of $n$, so I attempted to prove this statement by assuming it was true.

My Attempt:

\begin{align} 4261 + 2308n &= a^2 + b^2 \\ \Leftrightarrow \ 4261 + 2308n - 2b^2 &= a^2 - b^2 \\ \Leftrightarrow \ 4261 + 2(34^2n - b^2) &= a^2 - ab + ab - b^2 \\ \Leftrightarrow \ 4261 + 2(34\sqrt n + b)(34\sqrt n - b) &= (a + b)(a - b)\end{align} For a value $x$, if $\pi(x) = y$ and $\pi (x - 1) = y - 1$ then by definition of the function, $x$ is prime. Therefore, I need to prove that if $\pi(\text{LHS} - 1) = \pi(\text{LHS}) - 1$, then the same applies for the $\text{RHS}$. However, I do not know what steps to do from here to achieve such a statement. Could somebody please help me?

Thank you.

An odd prime $p$ is a sum of two squares $a^2+b^2$ if and only if $p\equiv 1 \pmod 4$. This is the Fermat's theorem on sums of two squares.
Observe that the definition of your $p$ gives $$p=4261+2308n \equiv 1 \pmod 4$$
Hence whenever $p$ is prime it trivially satisfies the theorem, whence you will be able to find a decomposition into sum of two squares $$p = a^2+b^2$$ (Therefore the prove of the decomposition comes from the theorem and not so much from your formula. There are several proofs of the theorem here.)
The extra condition you have given: $\gcd(a,b)=1$ is always true since $d=\gcd(a,b)$ must divide $p$: $$p = a^2+b^2 \equiv 0 \pmod d$$ and the only possibility is $d=1$. ($d\neq p$, otherwise $a^2+b^2>p$.)
• Yes. I was looking at other sorts of primes being the sum of two squares, and I realised that Pythagorean primes were of that sort, for which they were one more than a multiple of $4$. Thank you very much though! I can't upvote now, for I have to wait $16$ hours, but I will definitely give you a $\ \color{green}{\checkmark}$ – Mr Pie Jan 10 '18 at 7:45