1) The Euclidean Algorithm and Primes Flashcards
What does the Euclidean Division theorem state about the division of two integers
Given any integers a and b with b /= 0, there exist unique integers q (quotient) and r (remainder) such that: a=qb+r, where 0 ≤r<∣b∣
Describe the proof of the Euclidean Division theorem
What does it mean for an integer b to divide another integer a
If there exists an integer x with a = bx, then we say that b divides a
What is a common divisor of two integers a and b, and how is the set of all common divisors represented
Let a, b ∈ Z. If d | a and d | b we say that d is a common divisor of a and b
D(a, b) denotes the set of all common divisors of a and b
How is the greatest common divisor represented
gcd(a,b)
How does the greatest common divisor relate to the Euclidean division equation a=mb+r
If a = mb + r , then D(a, b) = D(b, r). Moreover, if at least one of a or b is non-zero then gcd(a, b) = gcd(b, r)
How is it proven that D(a,b)=D(b,r) and that gcd(a,b)=gcd(b,r) when at least one of a or b is nonzero
What is Bézout’s lemma
Let a, b ∈ Z with at least one not equal to zero. There exist integers s, t ∈ Z such that as + bt = gcd(a, b)
What is the proof of Bézout’s lemma
What is a linear Diophantine equation
A linear Diophantine equation is an equation of the form a1x1 + · · · + anxn = c, where ai, c ∈ Z and we seek integer solutions (x1, . . . , xn)
What are the conditions for the equation ax+by=c to have integer solutions, and how can they be found
What is a prime number
An integer p > 1 is said to be prime if the only positive divisors of p are 1 and itself
What is Euclid’s lemma
Let a, b ∈ Z and let p be a prime. If p | ab then either p | a or p | b
Describe the proof of Euclid’s lemma
What is the Fundamental Theorem of Arithmetic
Every integer greater than 1 has a prime factorisation and this factorisation is unique up to reordering the factor
What is Euclid’s Theorem
There are infinitely many primes
Describe the proof that there are infinitely many primes
Suppose for contradiction that there are only finitely many primes, p1, . . . , pk, say. Let N = (p1 · · · pk) + 1.
We have N > 1, so by the Fundamental Theorem of Arithmetic, N has a prime factorisation. In particular, N has some prime factor q. But none of the primes pi can divide N
So q is a prime distinct from p1, . . . , pk. This contradicts our assumption that p1, . . . , pk are the only primes
