Review of Elementary Number Theory
When can we express a prime number as a sum of two squares? Let’s start by sorting the first dozen primes into those with such an expression, and the rest: p=a 2 +b 2 : 2,5,13,17,29,37 . p=a 2 +b 2 : 3,7,11,19,23,31 .
Pierre de Fermat, an 18th-century French mathematician, posed a question that may seem like a mere riddle, similar to his renowned Last Theorem However, the beauty of number theory lies in how such riddles can lead to significant and intriguing discoveries Fermat's inquiry highlights the importance of exploring divisibility, prime numbers, and factorizations within mathematical structures that extend beyond the integers.
In Ch 1 we will look at concrete examples of such “higher” arithmetic.
To understand them you only need to know the definition of a ring and a field.
Understanding ideals is beneficial, but we will explore them in detail in the next chapter For the purposes of this discussion, we will assume that all rings are commutative and possess a multiplicative identity.
An integer \( p = 0, \pm 1 \) is considered prime if it has no integer divisors other than \( \pm 1 \) and \( \pm p \) When a prime \( p \) can be expressed as the sum of two squares, specifically \( p = a^2 + b^2 \) for integers \( a, b \in \mathbb{Z} \), it demonstrates that \( p \) can be factored nontrivially as \( (a + bi)(a - bi) \) when we include factors from the complex number set.
Fermat’s Last Theorem, which states that the equation x^n + y^n = z^n has no integer solutions for n ≥ 3, remained a conjecture for 350 years The proof of this theorem, discovered in the mid-1990s, is regarded as one of the most significant accomplishments in twentieth-century mathematics.
M Trifkovi´ c, Algebraic Theory of Quadratic Numbers, Universitext,
DOI 10.1007/978-1-4614-7717-4 1, © Springer Science+Business Media New York 2013
A ring, similar to the integers (Z), is a mathematical structure closed under addition, subtraction, and multiplication, but not necessarily division This article explores the fundamental question of how a prime number (p) can be factored within these rings, particularly in quadratic rings such as Z[i], which are formed by adding solutions to quadratic equations like x² + 1 = 0 to Z The book aims to rigorously address these questions, while general algebraic number theory extends this inquiry to polynomial equations of any degree Notably, many characteristics of algebraic number theory are already evident in the simpler context of quadratic rings The cornerstone of elementary arithmetic is encapsulated in a well-known theorem that underpins these concepts.
1.1.1 Theorem (Unique Factorization inZ) Any integer other than 0 and ±1can be written as a product of primes, uniquely up to permuting the prime factors and changing their signs.
The proof of Thm.1.1.1will be our template for extending arithmetic to rings such asZ[i] It proceeds through a chain of propositions.
1.1.2 Proposition(Division Algorithm) Given a, b∈Z, b= 0, there exist uniqueq, r∈Zsuch that a=qb+rand0≤r 0 Check that the set
S={n∈Z:n≥0 andn=a−sbfor somes∈Z} is nonempty By the Well-Ordering Principle, S has a minimal element r, which must be of the formr=a−qbfor someq∈Z If we hadb≤r, then
0≤r−b=a−qb−b=a−(q+ 1)b, so thatr−b∈S We also haver−b < r
(sinceb >0), which contradicts the choice ofras the minimum ofS.
Ifb 0 \), it would imply that \( r \) is a positive element of \( I \) that is smaller than \( d \), which contradicts the definition of \( d \) Therefore, we conclude that \( r = 0 \), leading to the result that \( d \) divides \( a \) A similar argument can be applied to show that \( d \) also divides \( b \).
Next, we show that d satisfies condition (1.1.4) Take c ∈ Z with c | a andc |b Thenc |ra+sb =d In particular, cis no bigger than d, so that d= gcd(a, b)
Check that the set I in the proof is closed under addition, and that it
“absorbs multiplication”: if n ∈ Z and x ∈ I, then nx ∈ I also In the terminology of Def.2.2.1,I is our first example of an ideal (of the ringZ).
To find the greatest common divisor (g.c.d.) of 598 and 273, we can illustrate the algorithm mentioned in Proposition 1.1.3 This algorithm involves a process of iterative division with remainders, which effectively determines the g.c.d through a series of calculations.
In the process of finding the greatest common divisor (g.c.d.) of two numbers, the divisor and remainder from each step serve as the dividend and divisor for the subsequent line For example, when calculating gcd(598, 273), the last non-zero remainder we obtain is 13 By tracing back from the next-to-last line, we can express the remainder based on the previous calculations, adhering to the principles outlined in Proposition 1.1.3.
Writing gcd(a, b) as a linear combination ofaandbgives us a good alge- braic handle on questions of divisibility The proof of the next proposition is an example.
1.1.6 Proposition (Euclid’s Lemma) For any prime pand any a, b∈ Z, p|abimplies p|aorp|b.
Proof Assume thatp|abandpa Sincepis prime, gcd(a, p) is 1 orp In the latter case, we’d havep= gcd(a, p)|a, contradicting the second assumption.
Thus, gcd(a, p) = 1, and Prop.1.1.3providesr, s∈Zsuch that 1 =rp+sa.
Then b = bã1 = p(br) + (ab)s is divisible by p, by the assumption that p|ab
We are prepared to establish the final component of the proof for Theorem 1.1.1 A straightforward inductive argument demonstrates the existence of a prime factorization However, the uniqueness of this factorization is grounded in Euclid’s Lemma, which provides a deeper understanding of the concept.
The proof of unique factorization in the set of integers (Z) establishes that every integer greater than 1 can be expressed as a product of positive prime numbers Furthermore, it demonstrates that any two distinct factorizations of the same integer will vary solely in the arrangement of these prime factors.
Existence of a prime divisor:Letnbe an integer greater than 1, and letp be the smallest divisor ofnwhich is greater than 1 We claim thatpis prime.
If not, it’s divisible by somexwith 1 < x < p By construction of p, those inequalities implyxn, contradictingx|p|n.
Existence of a prime factorization:We want to show that the set
The set S, defined as {x ∈ N \ {1} : x cannot be expressed as a product of primes}, is empty According to the Well-Ordering Principle, if S were not empty, there would exist a minimal element n in S Since any number m can be expressed as m = pn for some prime p, if n equals 1, then m would simply be a prime, contradicting the premise that m is in S Therefore, it follows that 1 < n < m, which implies that n cannot belong to S This indicates that n indeed has a prime factorization n = p1 × × pr Consequently, m can also be expressed as m = p × p1 × × pr, providing a prime factorization for m, which again contradicts the initial assumption that m is in S.
The uniqueness of prime factorization is established through Euclid's Lemma, which states that if two prime factorizations exist, such as n = p₁ × × pᵣ and n = q₁ × × qₛ, then the first prime, p₁, must divide the first prime of the second factorization, q₁ Since both p₁ and q₁ are primes, it follows that p₁ equals q₁ By canceling these primes, we obtain shorter factorizations, p₂ × × pᵣ = q₂ × × qₛ This process continues until each prime in the first factorization is paired with a corresponding prime in the second, confirming the uniqueness of prime factorization.
We would like to have an analog of unique factorization for quadratic numbers, solutions to equations of the formax 2 +bx+c= 0 witha, b, c∈Z.
To solve equations in modular arithmetic, particularly those of the form modulo n, we can evaluate all elements in Z/nZ However, a more efficient method involves utilizing the theory of quadratic residues, which we will outline here without providing a proof.
1.1.7 Definition Let p∈Nbe a positive odd prime, and leta∈Z We say that “ais a square mod p” whena≡b 2 (mod p) for someb∈Z We define the Legendre symbol by a p ⎧⎪
1 if ais a nonzero square mod p
−1 if ais not a square mod p
1.1.8 Example Let’s find “by hand” the Legendre symbols 3
We compute all squares inZ/11Z: x mod 11 0±1±2±3±4±5 x 2 mod 11 0 1 4 9 5 3
From this we see that 3 is a square modulo 11, but 7 isn’t: 3
The following theorem is an efficient alternative to calculating the Legen- dre symbol by brute force.
1.1.9 Theorem Let a, b∈Z, and take p, q ∈Nto be distinct positive odd primes The Legendre symbol satisfies the following properties:
The Field Q [i] and the Gauss Integers
Theorem 1.2.18 addresses Fermat's question regarding the conditions under which a prime number can be expressed as a sum of two squares To explore this, we will examine arithmetic within the ring Z[i] = {a + bi : a, b ∈ Z} This ring serves as the optimal subring of the field Q[i] = {a + bi : a, b ∈ Q} for conducting arithmetic, similar to how Z functions for Q The primary objective of this section is to demonstrate that unique factorization is valid in Z[i].
Gauss integers, denoted as Z[i], represent a two-dimensional, discrete array of points in the complex plane, forming a lattice structure This lattice is exemplified by a fundamental parallelogram with vertices at 0, 1, i, and 1+i, which tiles the plane without overlapping when translated by lattice points Fermat's question investigates the existence of a point within the Z[i] lattice that lies on a circle of radius √p centered at the origin While a geometric solution will be explored in Exercise 5.2.1, our current focus is on an algebraic approach to this problem.
Fig 1.1 The Gauss integers Z [i], with a fundamental parallelogram shaded in The dashed edges, including the vertices 1, i and 1 + i, do not belong to the fundamental parallelogram.
This ensures that any two of its translates by points in Z [i] are disjoint.
In a ring, a unit is defined as an element that possesses a multiplicative inverse, and the collection of these units forms a group under multiplication, represented as R × For instance, in any field F, the group of units is denoted as F × = F\0 Additionally, for the integers, the group of units is Z × = {±1}, which highlights that the prime factorization of an integer is unique, aside from the multiplication and rearrangement of its factors by units.
To find the units inZ[i], we use the following simple but versatile tool.
1.2.1 Definition The norm ofα=a+bi∈Q[i]isNα=α¯α=a 2 +b 2 ∈Q.
The norm Nα in the complex plane is always positive, representing the square of the distance from α to the origin This norm serves as a homomorphism of the multiplicative groups Q[i] × to Q ×, allowing for the mapping of Z[i] to Z Consequently, this reduction simplifies the analysis of divisibility in Z[i] to more manageable questions within Z.
The term "Gaussian integers" is commonly used in literature to refer to the ring Z[i], but I prefer to omit the -ian suffix This choice is based on the unnecessary nature of the ending, its inconsistent application, and the difficulty it poses in pronunciation for certain non-English names.
1.2.3 Proposition An ε∈Z[i] is a unit if and only ifNε=±1.
Proof Ifε∈Z[i] × , there is aυ∈Z[i] withευ= 1 Taking the norm, we get
NεãNυ = 1, so that Nε ∈Z ì Conversely, if Nε =ε¯ε = ±1, we find that ε − 1 =±ε¯∈Z[i], as desired
All other quadratic fields have a norm homomorphism, so the preceding two propositions hold in them as well.
1.2.4 Proposition The group of units inZ[i] is given by
Proof Putε=a+biwitha, b∈Z By Prop.1.2.3,εis a unit if and only if
Nε=a 2 +b 2 =±1 This can happen only if (a, b) is (±1,0) or (0,±1), since a 2 +b 2 ≥2 if bothaandb are non-zero β α β α θ θ θ + i θ + i + 1 θ + i θ + 1 θ + 1 θ + i + 1
Fig 1.2 α/β falls inside at least one of the circles of radius 1 centered at nearby lattice points (left) In fact, there is a point in Z [i] whose distance from α/β is at most √
The division algorithm in the integers (Z) enables division with a remainder that is smaller in absolute value than the divisor By substituting absolute value with norm, we can extend this concept to the Gaussian integers (Z[i]), resulting in a corresponding division algorithm.
1.2.5 Proposition Given α, β ∈ Z[i], β = 0, there exist κ, λ ∈ Z[i] such thatα=κβ+λ, withNλ