Problem 2 - A Computational Introduction to Number Theory and Algebra

Question

Let \(p\) be an odd prime. Show that the following are equivalent: (a) \((-2 \mid p)=1 ;\) (b) \(p \equiv 1\) or \(3(\bmod 8) ;\) (c) \(p=r^{2}+2 t^{2}\) for some \(r, t \in \mathbb{Z}\)

Step-by-Step Solution

Answer

Q: Based on the given step-by-step solution, prove that the statements (a), (b), and (c) are equivalent for an odd prime number p. A: The given solution proceeds in three steps to prove that the statements (a), (b), and (c) are equivalent for an odd prime number p: 1. First, Case 1 is shown, which demonstrates that statement (a) implies statement (b). This is done by assuming statement (a) to be true and using Fermat's Little Theorem and the order properties in modular arithmetic to deduce that p must be congruent to either 1 or 3 modulo 8, thus proving statement (b). 2. Next, Case 2 is proven, which is that statement (b) implies statement (c). This is done by first considering the congruence of p modulo 4 and using Fermat's two-square theorem to deduce that p can be expressed as a sum of two squares if p is congruent to 1 modulo 4. For the case when p is congruent to 3 modulo 4, Hensel's Lemma is applied to show that p can still be expressed as a sum of the form r^2 + 2t^2. 3. Finally, Case 3 is shown, which demonstrates that statement (c) implies statement (a). This is done by assuming that p can be expressed as r^2 + 2t^2 for some integers r and t and then showing that the equation x^2 ≡ -2 mod p has a solution (x=r), which implies that (-2 | p) = 1, thus proving statement (a). By demonstrating the implications of Case 1, Case 2, and Case 3, it is proven that statements (a), (b), and (c) are equivalent for an odd prime number p.

Step 1: Case 1: (a) implies (b)

Since \((-2 \mid p) = 1\), the equation \(x^2 \equiv -2 \pmod p\) has a solution. Let \(x_0\) be a solution. We combine this with Fermat's Little Theorem, which says that \(x_0^{p - 1} \equiv 1 \pmod p\). Squaring both sides and using the fact that \(x_0^2 \equiv -2 \pmod p\), we get $$x_0^{2p - 2} \equiv (-2)^{p - 1} \pmod p.$$ By Fermat's Little Theorem, we can rewrite this as \((-2)^{p - 1} \equiv 1\pmod p\). Now, we know that \(p\) is odd. We can rewrite \((-2)^{p - 1}\) as \((-1)^{p - 1} \cdot 2^{p - 1}\). Since \(p\) is odd, \((-2)^{p-1}=2^{p-1} \pmod p\). Thus, \(2^{p - 1} \equiv 1 \pmod p\). Using the order properties in \(\mathbb Z_p\), \(2^{p - 1}\) must divide \(\phi(p)=p-1\). Thus, \(p-1\) has a factor of 2. We will therefore have two cases: 1. The order of 2 modulo \(p\) is 1: for this to happen, we would require \(2\equiv 1\pmod p\). This is not possible, as p is an odd prime and \(p\neq 1\). 2. The order of 2 modulo \(p\) is 2: This means \(p-1=2\cdot t\) for some \(t\in \mathbb{Z}\). Consequently, \(p = 2t+1\), for which we can deduce \(p \equiv 1 (\bmod 8)\) or \(p \equiv 3 (\bmod 8)\). Thus, statement (a) implies statement (b).

Step 2: Case 2: (b) implies (c)

Let \(p\) be an odd prime such that \(p \equiv 1\) or \(3 (\bmod 8)\). We can use Fermat's two-square theorem which states that an odd prime can be expressed as a sum of two squares if and only if it is congruent to \(1\bmod 4\). Therefore, if \(p\equiv 1 (\bmod 4)\), we are certain that it has such a representation. If, however, it is of the form \(p\equiv 3 (\bmod 4)\), we know that \(p\) cannot be expressed as a sum of two squares. We attempt to rewrite \(p\) as a sum of squares in another way: $$p = r^2 + 2t^2.$$ Now we consider the congruence of \(p\) modulo 8. If \(p\equiv 1 (\bmod 8)\), then \(p\) can be expressed as \(4m+1\) for some integer \(m\). Since \(p \equiv 1 (\bmod 4)\), we know that it can be expressed as the sum of two squares, say \(p = a^2 + b^2\). Notice that if both \(a\) and \(b\) are odd, then \(a^2\equiv 1 (\bmod 8)\) and \(b^2\equiv 1 (\bmod 8)\), which together shows that \(p \equiv 2 (\bmod 8)\). This contradicts our initial assumption, so we know that one of \(a\) and \(b\) must be even, say \(a=2r\) and \(b=2t\). Then we have \(p = 4r^2 + 2t^2\) or \(p = r^2+2t^2\). On the other hand, if \(p\equiv 3 (\bmod 8)\), then \(p\) can be expressed as either \(8m+3\) or \(8m+7\). Using Hensel's Lemma for sums of squares and noting that \(3\equiv 7\equiv 3 (\bmod 4)\), we can show that \(p\) can be expressed as a sum of the form \(r^2+2t^2\). Thus, statement (b) implies statement (c).

Step 3: Case 3: (c) implies (a)

Suppose \(p = r^2 + 2t^2\) for some integers \(r\) and \(t\). Then \((-2 \mid p) = 1\) if and only if the equation \(x^2 \equiv -2 \pmod p\) has a solution. Observe that \(r^2 \equiv -2t^2\pmod p\), which means \(((-2t^2) \mid p) = r^2\). Since \(p\) is an odd prime and \(r\) is an integer, \(r^2\) is a nonzero integer modulo \(p\). Thus, we have shown that the equation \(x^2 \equiv -2 \pmod p\) has a solution \(x=r\), which implies \((-2 \mid p) = 1\). Hence, statement (c) implies statement (a). By demonstrating Case 1, Case 2, and Case 3, we have shown that the statements (a), (b), and (c) are equivalent for an odd prime \(p\).

Key Concepts

Fermat's Little Theorem

Fermat's Little Theorem is a simple yet powerful tool in number theory. It states that if you have a prime number \( p \) and an integer \( a \) that is not divisible by \( p \), then the following congruence holds:

• \( a^{p-1} \equiv 1 \pmod{p} \)

This theorem is central to working with modular arithmetic because it provides insights into the periodicity of powers modulo a prime.

In the context of the given exercise, Fermat's Little Theorem helps establish that if \((-2 \mid p) = 1\), meaning \(-2\) is a quadratic residue modulo \( p \), then by Fermat's Little Theorem \((-2)^{p - 1} \equiv 1 \pmod{p}\).

This theorem's essence is used to show that if the equation \( x^2 \equiv -2 \pmod{p} \) has a solution, it implies conditions such as \( p \equiv 1 \) or \( p \equiv 3 \pmod{8} \), which connects to the concept of quadratic residues explored below.

Quadratic Residues

Quadratic residues are numbers that can be expressed as the square of some integer modulo \( n \). More formally, a number \( a \) is a quadratic residue modulo \( n \) if there exists an integer \( x \) such that

• \( x^2 \equiv a \pmod{n} \)

In number theory, especially in problems involving primes, determining whether a number is a quadratic residue modulo a prime is crucial.

The Legendre symbol \((-2 \mid p)\) is used to represent whether \(-2\) is a quadratic residue modulo \( p \). When \((-2 \mid p) = 1\), it suggests that there is an integer \( x \) for which \( x^2 \equiv -2 \pmod{p} \).

In the exercise context, knowing that \(-2\) is a quadratic residue provides insights into the equivalences between multiple forms of \( p \). Specifically, it ties closely with the conditions given in parts (a), (b), and (c) of the exercise, which connect through the ability to express \( p \) in particular forms, whether congruence or sums of squares.

Fermat's Two-Square Theorem

Fermat's Two-Square Theorem is another fundamental principle in number theory. It states that a prime number can be expressed as a sum of two squares if and only if it is congruent to \( 1 \pmod{4} \).

This means if \( p \equiv 1 \pmod{4} \), then there exist integers \( a \) and \( b \) such that:

• \( p = a^2 + b^2 \)

This theorem provides a way to represent primes, especially odd primes, in different forms and is often used in combination with other number-theoretic tools.

In the problem you studied, although Fermat's Two-Square Theorem directly addresses sums of two squares, the exercise looks at expressing \( p \) as \( r^2 + 2t^2 \). This is a variant influenced by quadratic residues and more complex congruences like \( p \equiv 1 \) or \( p \equiv 3 \pmod{8} \). These equivalences form a bridge from Fermat's classical scenarios to broader scenarios involving the combination of squares and other integers as factors.