GCD, Euclid's algorithm and Bézout
GCD and LCM, Euclid's algorithm, coprime integers, Bézout's identity, Euclid's lemma (Gauss's theorem in France) and the integer equations ax + by = c.
- 25 cards
- 4 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
A few cards from the deck
GCD of a and b: what is it?
Show the answer
The largest integer that divides both a and b; it is computed without factorising, by Euclid's algorithm.
The common divisors of 84 and 30 are 1, 2, 3 and 6: the largest is 6. Every common divisor also divides the GCD.
What does this program print?
```python
a, b = 48, 18
while b:
a, b = b, a % b
print(a)`618120
Show the answer
6The successive pairs are (48, 18), (18, 12), (12, 6), (6, 0). The loop stops when b is 0, and a then holds the last non-zero remainder: 6.
Euclid's algorithm relies on the equality GCD(a, b) = GCD(b, …); it stops when the remainder is ….
Show the answer
Euclid's algorithm relies on the equality GCD(a, b) = GCD(b, a mod b); it stops when the remainder is 0.
For 252 and 198: GCD(252, 198) = GCD(198, 54) = GCD(54, 36) = GCD(36, 18) = GCD(18, 0) = 18.
LCM of a and b: what is it?
Show the answer
The smallest positive integer that is a multiple of both a and b.
For positive a and b, GCD × LCM = a × b: LCM(12, 18) = 12 × 18 / 6 = 36.