logo

Necessary and Sufficient Condition for a Prime to Leave a Remainder of 1 When Divided by 3 📂Number Theory

Necessary and Sufficient Condition for a Prime to Leave a Remainder of 1 When Divided by 3

Theorem

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

Explanation

Although $p=3$ is excluded, in fact $ 3= 2^2 - 2 \cdot 1 + 1^2$, so it would not matter much even if it were included in the theorem.

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

This fact is interesting in its own right, but it also has a deep connection with the Eisenstein integers, lifting number theory to a higher level.

Proof

$( \implies )$

$$ a^2 + 3 b^2 = ( a + b )^2 - ( a+ b) ( a - b) + (a - b) ^2 $$ so it suffices to show that there exist $a,b \in \mathbb{Z}$ satisfying $p = a^2 + 3b^2$.

Part 1.

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

Part 1-1. Gauss’s Quadratic Reciprocity Law

Gauss’s quadratic reciprocity law: For two distinct 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 quadratic reciprocity law, $$ \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 $p$ greater 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 exists $x=1$ satisfying $x^2 \equiv p \pmod{3 }$, so we must have $$ \left( { { p } \over { 3 } } \right) = 1 $$ Therefore, 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. $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. $k$ is odd
    • By Part 1-1, $\left( { { p } \over { 3 } } \right) \left( { { 3 } \over { p } } \right) = -1$, so $\displaystyle \left( { { p } \over { 3 } } \right) = - \left( { { 3 } \over { p } } \right)$
    • By Part 1-2, $\left( { { -1 } \over { p } } \right) = -1$, so $\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 either case, $-3$ is a quadratic residue modulo $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 we set $A := (cB)$, then for some $M \in \mathbb{Z}$, $$ A^2 + 3 B^2 = Mp $$ Moreover, $$ M = {{ A^2 + 3 B^2 } \over {p}} \le {{ (p-1)^2 - 3 \cdot 1^2 } \over {p}} = p - {{ 2p - 4 } \over {p}} < p $$ so $M < p$. If we keep reducing this $M$ until $M=1$, we can say that $p = a^2 + 3 b^2$ for some $a,b \in \mathbb{Z}$.

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}} $$ Consider $u,v \in \mathbb{Z}$ satisfying the above (for example, if $M=13$ and $A \equiv 10 \pmod{13}$, then $u \equiv -3 \pmod{13}$, so their existence is always guaranteed). 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 $u^2 + 3 v^2 = rM$ for some $r \in \mathbb{Z}$.

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 $$ so $r \le M$.

The case $M = r$ occurs only when $\displaystyle {{M} \over {2}} = \left| u \right| = \left| v \right| $, in which case $$ u^2 + 3 v^2 = 4u^2 = 4 v^2 = M^2 $$

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

To sum up, $u$ and $A$ must be both odd or both even, and $v$ and $B$ must also be both odd or both even. With this in mind, let us check whether the equation $$ A^2 + 3 B^2 = Mp = 2 |u| p $$ can hold.

  • Case 1. Both $A$ and $B$ are even
    Since $A$ is even, $|u|$ is also even and divisible by $2$. Dividing both sides of $A^2 + 3 B^2 = 2 |u| p$ by $4$ gives $$ \left( {{A} \over {2}} \right) ^2 + 3 \left( {{B} \over {2}} \right) ^2 = \left( {{ | u | } \over {2}} \right) p $$ This means that in Part 1 we chose $A,B,M$ excessively large. Take new $$ A ' := \left( {{A} \over {2}} \right) \\ B ' := \left( {{B} \over {2}} \right) \\ M’ := \left( {{ |u| } \over {2}} \right) $$ and restart Part 2.
  • Case 2. $A$ is even, $B$ is odd
    The left-hand side of $A^2 + 3 B^2 = 2 |u| p$ is odd while the right-hand side is even, so the equation $A^2 + 3 B^2 = Mp$ does not hold.
  • Case 3. $A$ is odd, $B$ is even
    The left-hand side of $A^2 + 3 B^2 = 2 |u| p$ is odd while the right-hand side is even, so the equation $A^2 + 3 B^2 = Mp$ does not hold.
  • Case 4. Both $A$ and $B$ are odd Set $A := 2n + 1$, $B := 2m +1$ for some $n,m \in \mathbb{Z}$. $$ 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 $| u |$ and $p$ are odd, $Mp = 2 | u | p$ cannot be a multiple of $4$, and the equation $A^2 + 3 B^2 = Mp$ does not hold.

Examining every possible case, Cases 2~4 show that $r < M$.

Part 2-2. $1 \le r$

If we assume $r = 0$, then $\begin{cases} 0 = u \equiv A \pmod{M} \\ 0 = v \equiv B \pmod{M} \end{cases}$, so $A, B$ are multiples of $M$ and $A^2 + 3 B^2$ must be a multiple of $M^2$. That is, $M$ must be a multiple of $p$, but this is impossible since Part 1 showed $M < p$. Therefore, $r$ must be greater than $0$.

Combining Part 2-1 and Part 2-2 yields $1 \le r < M$.

Part 3. Modified Cauchy-Schwarz Identity

$$ \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} $$ so $3 ( uA - vB )$ is a multiple of $M$. From Part 2, $$ ( uA + 3 vB ) \equiv AA + 3 BB \equiv 0 \pmod{M} $$ so $( 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 identity, $$ ( uA + 3 vB )^2 + 3 ( uA - vB )^2 = M^2 r p $$ Since $( uA + 3 vB )$ and $3 ( uA - vB )$ are multiples of $M$ by Part 3 above, dividing both sides by $M^2$ gives $$ \left( {{ uA + 3 vB } \over {M}} \right)^2 + 3 \left( {{ uA - vB } \over {M}} \right)^2 = r p $$

Now, defining new $$ A_{2} : = \left( {{ uA + 3 vB } \over {M}} \right) \\ B_{2} := \left( {{ uA - vB } \over {M}} \right) \\ M_{2} := r $$ we again obtain $A_{2}^{2} + 3 B_{2}^{2} = M_{2} p$. Therefore, for $k \in \mathbb{N}$, such $A_{k}, B_{k}, M_{k}$ have the same properties as the $A, B, M$ defined in Parts 1~3. Since $r < M$ in Part 2, $M_{k}$ becomes smaller each time $k$ increases, and since $1 \le r$, it stops exactly at $M=1$.

$( \impliedby )$

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

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

Therefore, in $\pmod{3}$, for any natural number $N$ that is not a multiple of $3$, we have $N^2 \equiv 1 \pmod{ 3 }$ in any case.

From now on, let us consider all possible combinations of $a$ and $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 $p$ would be a multiple of $3$, so 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 $p$ would be a multiple of $3$, so 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*} $$ Examining all the cases, in Case 01, Case 02, Case 11, and Case 22 we have $p \equiv 1 \pmod{3}$, and cases like Case 00 and Case 12 do not occur.

■

See Also