Question

Let \(p \in\) N be an odd prime. (i) Prove that 4 divides \(p-1\) if \(-1\) is a square modulo \(p\). (ii) Prove the converse of (i). Hint: Consider \(a^{(p-1) / 4}\) for a nonsquare \(a \in \mathbb{R}_{p}^{x}\). (iii) Conclude that the Legendre symbol \(\left(\frac{-1}{n}\right)\) is \(I\) if and only if \(p \equiv 1 \bmod 4\).

Short answer

\(-1\) is a square mod \(p\) if and only if \(p \equiv 1 \pmod{4}\).

Step-by-step solution

Understanding the Legendre Symbol

The Legendre symbol, denoted by \(\left(\frac{a}{p}\right)\), is a notation that determines whether an integer \(a\) is a quadratic residue modulo \(p\). If it's a residue, \(\left(\frac{a}{p}\right) = 1\); if not, \(\left(\frac{a}{p}\right) = -1\). Specifically, \(\left(\frac{-1}{p}\right)\) is 1 if \(-1\) is a quadratic residue modulo \(p\), and -1 otherwise.

Proving Part (i) - Assume \(-1\) is a Square Modulo \(p\)

If \(-1\) is a square modulo \(p\), there exists an integer \(x\) such that \(x^2 \equiv -1 \pmod{p}\). This implies \(x^4 \equiv 1 \pmod{p}\). According to Fermat's Little Theorem, \(x^{p-1} \equiv 1 \pmod{p}\). Since \(x^4 \equiv 1\), it follows that \(p-1\) must be divisible by 4 (i.e., \(p-1 \equiv 0 \pmod{4}\)). Thus, \(4\) divides \(p-1\).

Proving Part (ii) - Prove the Converse Using an Nonsquare

For the converse, suppose \(4\) divides \(p-1\), i.e., \(p-1 = 4k\) for some integer \(k\). Let \(a\) be a nonsquare modulo \(p\). Then, \(a^{\frac{p-1}{4}}\) is either \(1\) or \(-1\). Since \(a\) is not a square, it follows that \(a^{\frac{p-1}{4}} = -1\). By Fermat’s Little Theorem, \(a^{p-1} \equiv 1 \pmod{p}\), so computing the power we find \(\left(a^{\frac{p-1}{4}}\right)^4 \equiv 1\), confirming \(a^{\frac{p-1}{4}} = \pm i\) if and only if \(-1\) is a square modulo \(p\).

Conclusion for Part (iii) - Legendre Symbol Implication

We conclude that \(\left(\frac{-1}{p}\right) = 1\) if and only if \(p \equiv 1 \pmod{4}\). This is because \(-1\) is a quadratic residue modulo \(p\) precisely when \(p - 1\) is divisible by 4, which corresponds to \(p \equiv 1 \pmod{4}\).

Key concepts

Legendre Symbol

The Legendre Symbol is a compact way to express whether an integer is a quadratic residue modulo a prime number. Given an odd prime \( p \) and integer \( a \), the Legendre symbol is denoted as \( \left(\frac{a}{p}\right) \).

• \( \left(\frac{a}{p}\right) = 1 \) means that \( a \) is a quadratic residue modulo \( p \). In simple terms, it means there exists an integer \( x \) such that \( x^2 \equiv a \pmod{p} \).
• \( \left(\frac{a}{p}\right) = -1 \) means that \( a \) is not a quadratic residue modulo \( p \). In other words, no such \( x \) exists.
• If \( a \equiv 0 \pmod{p} \), then \( \left(\frac{a}{p}\right) = 0 \).

This symbol is used to understand many properties in number theory, particularly when dealing with quadratic residues.

Quadratic Residue

A quadratic residue is a number that can be expressed as the square of another integer modulo \( p \), where \( p \) is a prime number. For a given integer \( a \), it is termed quadratic residue modulo \( p \) if there exists an integer \( x \) such that:

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

If such an \( x \) exists, \( a \) is a quadratic residue; if not, it is a non-residue.

Quadratic residues have many applications across number theory. They play a key role in determining properties related to the divisibility of numbers in modular arithmetic settings. Understanding them is crucial for solving problems involving congruences and primes.

Fermat's Little Theorem

Fermat's Little Theorem is a fundamental theorem in number theory that reveals properties of prime numbers. It states that if \( p \) is a prime number and \( a \) is an integer not divisible by \( p \), then:

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

This theorem has profound implications for modular arithmetic and cryptography. It helps to simplify calculations involving large powers in modular arithmetic, reducing complex expressions to more manageable results.
Moreover, Fermat's Little Theorem is the basis for more advanced results in number theory, including the development of RSA encryption, which is a cornerstone of modern cryptography.

Modular Arithmetic

Modular Arithmetic is a system of arithmetic for integers, where numbers wrap around after reaching a certain value, known as the modulus. It’s like a clock that resets after 12 hours - once you reach 12 on the clock, the next hour is 1 again.

The key concepts of modular arithmetic include:

• Congruence: Two numbers \( a \) and \( b \) are said to be congruent modulo \( n \) if their difference is a multiple of \( n \), denoted \( a \equiv b \pmod{n} \).
• Addition and Multiplication: You can add or multiply numbers and then take the result modulo \( n \). For example, \((a + b) \equiv (a \mod n + b \mod n) \pmod{n} \).

Understanding modular arithmetic is essential for topics involving number theory, especially in proofs and exercises involving congruences and divisibility on the integer set.