Primes Divisible by 3 with a Remainder of 1: Necessary and Sufficient Conditions 📂Number Theory

Primes Divisible by 3 with a Remainder of 1: Necessary and Sufficient Conditions

Theorem

$p \ne 3$ is a prime number. $p \equiv 1 \pmod{3}$ $\iff$ for some $a,b \in \mathbb{Z}$ $p = a^2 - ab + b^2$

Description

Though $p=3$ is excluded, in fact since $3= 2^2 - 2 \cdot 1 + 1^2$ , it wouldn’t matter much if it was included in the theorem.

For example, $13 \equiv 1 \pmod{4}$ is $13 = 1 - 4 + 16 = 1^2 - 1 \cdot 4 + 4^2$ $37 \equiv 1 \pmod{4}$ is $37 = 9 -21 + 49 = 3^2 - 3 \cdot 7+ 7^2$ $61 \equiv 1 \pmod{4}$ is $61 = 16 - 36 + 81 = 4^2 - 4 \cdot 9 + 9^2$

These facts are interesting in themselves, but also have deep connections with Eisenstein integers, taking number theory to a higher dimension.

Proof

$( \implies )$

$a^2 + 3 b^2 = ( a + b )^2 - ( a+ b) ( a - b) + (a - b) ^2$ Thus, it suffices to show the existence of $a,b \in \mathbb{Z}$ that satisfies $p = a^2 + 3b^2$ .

Part 1.

Since $p \equiv 1 \pmod{3}$ is odd, for some $k \in \mathbb{N}$ , it can be expressed as $p = 6k +1$ .

Part 1-1. Gauss’s Law of Quadratic Reciprocity

Gauss’s Law of Quadratic Reciprocity: For two different odd numbers $p , q$ ,
[2]: $\left( {{ p } \over { q }} \right) \left( {{ q } \over { p }} \right) = (-1)^{ { {p-1} \over {2} }{ {q-1} \over {2} } }$

By Gauss’s law of quadratic reciprocity, $\begin{align*} \left( { { p } \over { 3 } } \right) \left( { { 3 } \over { p } } \right) =& (-1)^{ { {p-1} \over {2} }{ {3-1} \over {2} } } \\ =& (-1)^{ {{ (6k + 1) - 1 } \over {2}} } \\ =& (-1)^{3k} \\ =& (-1)^{k} \end{align*}$

Part 1-2. Euler’s Criterion

Euler’s Criterion: $a^{{p-1} \over {2}} \equiv \left( {a \over p} \right) \pmod{p}$

By Euler’s criterion, $\left( {{-1} \over {p}} \right) \equiv (-1)^{ {{ p - 1 } \over {2}} } \equiv (-1)^{k} \pmod{p}$

Part 1-3. Multiplicative Property of the Legendre Symbol

Multiplicative Property of the Legendre Symbol: For a prime number $p$ larger than $2$ , $\left( { ab \over p } \right) = \left( { a \over p } \right) \left( { b \over p } \right)$

By the multiplicative property of the Legendre symbol, $\left( { { 3 } \over { p } } \right) = \left( { { -1 } \over { p } } \right) \left( { { -3 } \over { p } } \right)$ Since $p \equiv 1 \pmod{3}$ , there must exist $x=1$ satisfying $x^2 \equiv p \pmod{3 }$ , $\left( { { p } \over { 3 } } \right) = 1$ Hence, we obtain the following: $\left( { { p } \over { 3 } } \right) \left( { { 3 } \over { p } } \right) = \left( { { -1 } \over { p } } \right) \left( { { -3 } \over { p } } \right)$

Part 1-4.

Case 1. If $k$ is even
- By Part 1-1, $\displaystyle \left( { { p } \over { 3 } } \right) \left( { { 3 } \over { p } } \right) = 1$
- By Part 1-2, $\displaystyle \left( { { -1 } \over { p } } \right) = 1$
- By Part 1-3, $\displaystyle 1 = 1 \cdot \left( { { -3 } \over { p } } \right)$
Case 2. If $k$ is odd
- By Part 1-1, since $\left( { { p } \over { 3 } } \right) \left( { { 3 } \over { p } } \right) = -1$ , $\displaystyle \left( { { p } \over { 3 } } \right) = - \left( { { 3 } \over { p } } \right)$
- By Part 1-2, since $\left( { { -1 } \over { p } } \right) = -1$ , $\displaystyle \left( { { p } \over { 3 } } \right) = \left( { { -1 } \over { p } } \right) \left( { { 3 } \over { p } } \right) = \left( { { -3 } \over { p } } \right)$
- By Part 1-3, $\displaystyle 1 = \left( { { -3 } \over { p } } \right)$

In any case, $-3$ is a quadratic residue of $p$ , and there exists $c \in \mathbb{Z}$ satisfying $c^{2} \equiv -3 \pmod{p}$ . Multiplying both sides by $B^2$ and rearranging gives $(cB)^2 + 3 B^2 \equiv 0 \pmod{ p }$ and, if set $A := (cB)$ , for some $M \in \mathbb{Z}$ , $A^2 + 3 B^2 = Mp$ Also, $M = {{ A^2 + 3 B^2 } \over {p}} \le {{ (p-1)^2 - 3 \cdot 1^2 } \over {p}} = p - {{ 2p - 4 } \over {p}} < p$ thus $M < p$ . By continuously reducing $M$ to $M=1$ , for some $a,b \in \mathbb{Z}$ , $p = a^2 + 3 b^2$ can be said.

Part 2. $1 \le r < M$

$u \equiv A \pmod{M} \\ v \equiv B \pmod{M} \\ - {{M} \over {2}} \le u,v \le {{M} \over {2}}$ Considering $u,v \in \mathbb{Z}$ that satisfies (for instance, if $M=13$ and $A \equiv 10 \pmod{13}$ , then $u \equiv -3 \pmod{13}$ , its existence is always assured). Then, since $A^2 + 3B^2 = pM$ in Part 1, $u^2 + 3 v^2 \equiv A^2 + 3 B^2 \equiv 0 \pmod{M}$ and for some $r \in \mathbb{Z}$ , $u^2 + 3 v^2 = rM$ .

Part 2-1. $r < M$

$r = {{ u^2 + 3 v^2 } \over {M}} \le {{ (M/2)^2 + 3 (M/2)^2 } \over { M }} \le M$ Therefore, $r \le M$ .

In the case of $M = r$ , the only possibility is when $\displaystyle {{M} \over {2}} = \left| u \right| = \left| v \right|$ , $u^2 + 3 v^2 = 4u^2 = 4 v^2 = M^2$

Here, since $M = | 2u |$ is even, for some $\alpha \in \mathbb{Z}$ , $u = M \alpha + A = 2 |u| \alpha +A$ so, $u \equiv A \pmod{ 2 }$ .
Similarly, $M = | 2v |$ and, for some $\beta \in \mathbb{Z}$ , $v = M \beta + B = 2 |v| \beta +B$ so, $v \equiv B \pmod{ 2 }$ .

Summarizing, $u$ and $A$ must both be even or odd, and $v$ and $B$ must also be either both even or odd. Let’s check if the following equation can be satisfied. $A^2 + 3 B^2 = Mp = 2 |u| p$

Case 1. Both $A$ and $B$ are even
Since $A$ is even, $|u|$ is also even and can be divided by $2$ . Dividing both sides of $A^2 + 3 B^2 = 2 |u| p$ by $4$ yields $\left( {{A} \over {2}} \right) ^2 + 3 \left( {{B} \over {2}} \right) ^2 = \left( {{ | u | } \over {2}} \right) p$ This excessively presupposes $A,B,M$ in Part 1. A new $A ' := \left( {{A} \over {2}} \right) \\ B ' := \left( {{B} \over {2}} \right) \\ M’ := \left( {{ |u| } \over {2}} \right)$ should be set and Part 2 started again.
Case 2. $A$ is even, $B$ is odd
The left side of $A^2 + 3 B^2 = 2 |u| p$ is odd while the right side is even, so equation $A^2 + 3 B^2 = Mp$ cannot hold.
Case 3. $A$ is odd, $B$ is even
The left side of $A^2 + 3 B^2 = 2 |u| p$ is odd while the right side is even, so equation $A^2 + 3 B^2 = Mp$ cannot hold.
Case 4. Both $A$ and $B$ are odd Let $n,m \in \mathbb{Z}$ , $A := 2n + 1$ , $B := 2m +1$ , $A^2 + 3 B^3 = 4n^2 + 4n + 1 + 3( 4 m^2 + 4m + 1 ) = 4( n^2 + n + 3 m^2 + 3m + 1)$ is a multiple of $4$ . However, since both $| u |$ and $p$ are odd, $Mp = 2 | u | p$ cannot be a multiple of $4$ , and equation $A^2 + 3 B^2 = Mp$ cannot hold.

After examining all possible cases, Cases 2 to 4 show that $r < M$ can be inferred.

Part 2-2. $1 \le r$

Assuming $r = 0$ , since $\begin{cases} 0 = u \equiv A \pmod{M} \\ 0 = v \equiv B \pmod{M} \end{cases}$ , $A, B$ must be a multiple of $M$ , and $A^2 + 3 B^2$ must be a multiple of $M^2$ . Therefore, $M$ must be a multiple of $p$ , but since Part 1 showed $M < p$ , this is impossible. Thus, $r$ must be larger than $0$ .

Combining Part 2-1 and Part 2-2, we obtain $1 \le r < M$ .

Part 3. Modified Cauchy-Schwarz Inequality

$\begin{align*} & (u^2 + 3 v^2) ( A^2 + 3 B^2 ) \\ = & u^2 A^2 + 3 v^2 A^2 + 3 u^2 B^2 + 9 v^2 B^2 \\ = & ( u^2 A^2 + 6uAvB + 3v^2 B^2 ) + ( 3 v^2 A^2 - 6uAvB + 3 u^2 B^2 ) \\ = & ( uA + 3 vB )^2 + 3 ( uA - vB )^2 \end{align*}$ Meanwhile, $3 ( uA - vB ) \equiv 3 ( BA - AB ) \equiv 0 \pmod{M}$ therefore, $3 ( uA - vB )$ is a multiple of $M$ . From Part 2, $( uA + 3 vB ) \equiv AA + 3 BB \equiv 0 \pmod{M}$ thus, $( uA + 3 vB )$ is a multiple of $M$ .

Part 4.

Since $A^2 + 3 B^2 = Mp$ and $u^2 + 3 v^2 = Mr$ , $(u^2 + 3 v^2) ( A^2 + 3 B^2 ) = M^2 r p$ Using the modified Cauchy-Schwarz inequality, $( uA + 3 vB )^2 + 3 ( uA - vB )^2 = M^2 r p$ Since $( uA + 3 vB )$ and $3 ( uA - vB )$ from Part 3 are multiples of $M$ , dividing both sides by $M^2$ yields $\left( {{ uA + 3 vB } \over {M}} \right)^2 + 3 \left( {{ uA - vB } \over {M}} \right)^2 = r p$

With a new $A_{2} : = \left( {{ uA + 3 vB } \over {M}} \right) \\ B_{2} := \left( {{ uA - vB } \over {M}} \right) \\ M_{2} := r$ defined, we regain $A_{2}^{2} + 3 B_{2}^{2} = M_{2} p$ . Thus, such $A_{k}, B_{k}, M_{k}$ as defined in Parts 1~3 possesses the same properties for $k \in \mathbb{N}$ . Since $r < M$ in Part 2, $M_{k}$ decreases with each increment of $k$ , stopping exactly at $M=1$ .

$( \impliedby )$

Let the quotient of $a,b$ satisfying $p=a^2 - ab + b^2$ divided by $3$ be $n,m$ .

If $N_{0} = 3k + 0$ , $N_{0}^{2} \equiv 9k^2 \equiv 0 \pmod{ 3 }$
If $N_{1} = 3k + 1$ , $N_{1}^{2} \equiv \left( 9k^2 + 6k \right) + 1 \equiv 1 \pmod{ 3 }$
If $N_{2} = 3k + 2$ , $N_{0}^{2} \equiv \left( 9k^2 + 12k + 3 \right) + 1 \equiv 1 \pmod{ 3 }$

Therefore, for a natural number $N$ not a multiple of $3$ in regard to $\pmod{3}$ , any way $N^2 \equiv 1 \pmod{ 3 }$ is achieved.

From now, let’s consider all possible combinations of $a$ , $b$ .

Case 00. $a= 3n$ , $b = 3m$ $p = 9 n^2 - 9 nm + 9 m^2 = 3 ( 3 n^2 - 3 nm + 3 m^2)$ The prime number $p$ becomes a multiple of $3$ , thus this combination is impossible.
Case 01. $a= 3n$ , $b = 3m + 1$ $p \equiv 9 n^2 - 3n b + b^2 \equiv 1 \pmod{ 3 }$
Case 02. $a= 3n$ , $b = 3m + 2$ $p \equiv 9 n^2 - 3n b + b^2 \equiv 1 \pmod{ 3 }$
Case 11. $a= 3n + 1$ , $b = 3m + 1$ $p \equiv a^2 - ( 3n + 1 ) ( 3m + 1) + b^2 \equiv 1 - 9nm - 3n - 3m - 1 + 1 \equiv 1 \pmod{3}$
Case 12. $a= 3n + 1$ , $b = 3m + 2$ $\begin{align*} p =& (3n+1)^2 - ( 3n + 1 ) ( 3m + 2 ) + (3m+2)^2 \\ =& 9n^2 + 6n + 1 - 9nm - 6n - 3m - 2 + 9m^2 + 12m + 4 \\ =& 3 ( 3n^2 + 3m^2 - 3nm + 2n + 4m + 1 ) \end{align*}$ The prime number $p$ becomes a multiple of $3$ , thus this combination is impossible.
Case 22. $a= 3n + 2$ , $b = 3m + 2$ $\begin{align*} p \equiv& a^2 - ( 3n + 2 ) ( 3m + 2 ) + n^2 \\ \equiv& 1 - 9nm - 6n - 6m - 4 + 1 \\ \equiv& -2 \\ \equiv& 1 \pmod{3} \end{align*}$ Reviewing all cases, Case 01, Case 02, Case 11, and Case 22 occur when $p \equiv 1 \pmod{3}$ , and Case 00, Case 12 do not occur.

■