Abstract

It is a well-known result that prime numbers congruent to 1 modulo 4 are representable as a sum of two squares. A recent article shows that the number of representations can imply the primality of square-free integers congruent to 1 modulo 4. However, the authors did not clarify the distinctness of the construction of representations in the proof of the main theorem. We provide a complementary proof to clarify this construction and also present an alternative proof based on Jacobi’s two square theorem.

Keywords

Fermat’s Two Square Theorem, Primality, Sum of Two Squares

Share and Cite:

1. Introduction

Fermat’s two square theorem states that an odd prime $p$ can be represented as a sum of two squares if and only if $p\equiv 1$ (mod 4) [1]. However, this classical theorem only reveals the property of representability as a sum of two squares for primes congruent to 1 modulo 4, while little attention has been paid to the complete picture: using the number of such representations to detect primality for a general positive integer congruent to 1 modulo 4.

The recent article [2] presents a criterion for testing the primality of square-free positive integers congruent to 1 modulo 4, based on the uniqueness of representations as a sum of two squares. It goes beyond Fermat’s theorem and establishes a two-way connection between uniqueness of representation as a sum of two squares and primality. Modern primality tests include the deterministic, polynomial-time AKS algorithm [3] and the probabilistic Miller-Rabin test [4] [5], whose error probability can be reduced through repeated rounds. Unlike these computational algorithms, the theorem in [2] connects primality to the uniqueness of representation as a sum of two squares.

Unfortunately, the proof of the main theorem relies on the implicit assumption that the constructed representations are pairwise distinct, but a justification was not provided.

In this paper, we further clarify the counting step in the proof of the main theorem in [2], showing that the representations generated in Step 2 of Section 3 are pairwise distinct up to order and signs.

2. Two Supplementary Proofs of the Theorem

We first recall the main theorem of [2].

Two integer pairs are regarded as equivalent if one can be obtained from the other by changing order and signs independently. The representation of an integer $a$ as a sum of two squares is considered unique if all integer solutions of $a=c^2+d^2$ form exactly one equivalence class under this relation.

Theorem Let $a$ be a square-free positive integer larger than 1 and $a\equiv 1$ (mod 4). If $a=c^2+d^2$ has a unique representation as a sum of two squares for a pair of integers $c$ and $d$ , then $a$ is prime.

The authors of [2] prove the theorem by offering the following method to construct $2^{k-1}$ candidate representations as a sum of two squares for $a=p_1{p}_2\cdots p_k$ . Since such a representation exists, every prime factor congruent to 3 modulo 4 must occur with an even exponent. Combined with the fact that $a$ is square-free, $p_j$ ’s are all distinct primes congruent to 1 modulo 4.

The first factor $p_1$ has a representation $p_1=x_1^2+y_1^2$ by Fermat’s two square theorem.

Assume that $p_j$ has a representation $p_j=x_j^2+y_j^2$ , where $x_j,y_j>0$ , and a representation $A^2+B^2$ of $p_1\cdots p_{j-1}$ has already been obtained. The Brahmagupta-Fibonacci Identity gives two representations for $p_1\cdots p_j$ :

$\left(A^2+B^2\right)\left(x_j^2+y_j^2\right)={\left(A{x}_j-B{y}_j\right)}^2+{\left(A{y}_j+B{x}_j\right)}^2={\left(A{x}_j+B{y}_j\right)}^2+{\left(A{y}_j-B{x}_j\right)}^2.$

After incorporating all $k$ factors, this process generates $2^{k-1}$ candidate representations.

In [2], these $2^{k-1}$ candidate representations are regarded as pairwise distinct up to order and signs in the proof of the main theorem, but this does not immediately follow. We now provide two ways to justify this counting step.

The first is to justify that the candidate representations are pairwise distinct up to order and signs by the following lemma.

Lemma The $2^{k-1}$ candidate representations as a sum of two squares are pairwise distinct, where we consider two representations the same if they differ only in the order of the summands or in signs.

Proof:

We prove the lemma by induction. The first prime factor $p_1$ has a unique representation class by Fermat’s Theorem. Suppose that $p_1\cdots p_{j-1}$ has $2^{j-2}$ distinct representation classes $\left(A,B\right)$ . Using the construction in [2], we obtain $2^{j-1}$ representations of $p_1\cdots p_{j-1}{p}_j=\left(A^2+B^2\right)\left(x_j^2+y_j^2\right)$ . We show that each of these $2^{j-1}$ representations $\left(s,t\right)$ is generated uniquely from a pair $\left(A,B\right)$ along with one of the two Brahmagupta-Fibonacci identities.

Any representation $\left(A,B\right)$ of $p_1\cdots p_{j-1}$ that generates representation $\left(s,t\right)$ of $p_1\cdots p_j$ must satisfy

$s=A{y}_j+B{x}_j,t=\left|A{x}_j-B{y}_j\right|$

or

$s=\left|A{y}_j-B{x}_j\right|,t=A{x}_j+B{y}_j.$

By solving four linear systems arising from the sign choices in the absolute values, we obtain the following two possible solutions of $\left(A,B\right)$ (the remaining two candidates have non-positive components and are discarded):

$\left(A,B\right)=\left(\frac{y_{j}s+x_{j}t}{p_j},\frac{\left|x_{j}s-y_{j}t\right|}{p_j}\right),\left(\frac{\left|y_{j}s-x_{j}t\right|}{p_j},\frac{x_{j}s+y_{j}t}{p_j}\right).$

If both of the solutions for A and B are feasible, then $p_j$ divides both $s$ and $t$ . Hence $p_j^2$ divides $s^2+t^2=p_1\cdots p_{j-1}{p}_j$ , which forces $p_j$ to divide $p_1\cdots p_{j-1}$ , contradicting that the prime factors $p_1,p_2,\cdots ,p_j$ are distinct. Therefore, $\left(s,t\right)$ is generated in exactly one way. Hence each induction step doubles the number of distinct representation classes. This proves the lemma. ■

The lemma justifies the distinctness, up to order and signs, of the representations generated by the iterative construction in [2]. Therefore, at least $2^{k-1}$ representations are found by this construction. From this, unique representation as a sum of two squares leads to primality.

Another direct way is to prove the main theorem of [2] without the construction. In fact, we can get the number of representations from Jacobi’s two square theorem [6] [7]. Jacobi’s theorem states that the number of integer solutions $\left(x,y\right)\in {\mathbb{Z}}^2$ of $a=x^2+y^2$ is $4\left(d_1\left(a\right)-d_3\left(a\right)\right)$ , where $d_1\left(a\right)$ and $d_3\left(a\right)$ denote the numbers of positive divisors of $a$ congruent to 1 and 3 (mod 4) respectively. As demonstrated in Step 1 of [2], the integer $a=p_1{p}_2\cdots p_k$ in the main theorem has only distinct prime factors congruent to 1 modulo 4. Therefore, the number of such solutions is

$4\left(d_1\left(a\right)-d_3\left(a\right)\right)=4\times \left(2^k-0\right)=2^{k+2}.$

On the other hand, if the representation of $a$ as a sum of two squares is unique, then it has exactly eight integer solutions $\left(x,y\right)$ , since neither coordinate can be zero when $a$ is square-free, and their absolute values cannot be equal when $a$ is odd. Thus, $2^{k+2}=8$ leads to $k=1$ . This proves the theorem.

3. Conclusion

We justify that the representations constructed in the proof of [2] are pairwise distinct, and we also provide an alternative proof based on Jacobi’s two square theorem. The main contribution of [2], together with the supplementary proofs presented in this paper, is to extend the scope of Fermat’s two square theorem by developing the representability of integers as sums of two squares from a property of primes into a criterion for primality testing.

Acknowledgements

The author thanks Way Kuo for insightful discussions. This research is supported by City University of Hong Kong project No. 9610556.

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

References