logo

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.

■

See Also