Euclidean Algorithm: GCD, Bézout Coefficients, and Applications

All flashcards

What is the greatest common divisor?

The greatest common divisor, or GCD, is the largest positive integer that divides each of two given integers without a remainder.

What does coprime mean?

Two integers are coprime when their GCD is 1. They may each be composite; they simply share no factor greater than 1.

What is the subtraction invariant?

For positive integers with $a>b$, $gcd(a,b)=gcd(b,a-b)$. The common divisors are unchanged by replacing the larger number with its difference from the smaller.

How does the GCD relate to square tiles?

The GCD is the largest side length of a square tile that can cover an $a$-by-$b$ rectangle exactly.

Why are 6 and 35 coprime?

Their prime factors are 2 and 3, and 5 and 7, respectively. They share no prime factor, so their only common positive divisor is 1.

Quiz questions

1. For integers $x$ and $y$ with $y>0$, which condition defines division with remainder $x=qy+r$?Answer: $q$ and $r$ are integers, and $0\le r<y$.
2. The Euclidean algorithm gives $1071=2\cdot462+147$, $462=3\cdot147+21$, and $147=7\cdot21+0$. What is $gcd(1071,462)$?Answer: 21
3. Why must the division-based Euclidean algorithm terminate for positive integer inputs?Answer: Each remainder is a nonnegative integer smaller than the preceding divisor.
4. For inputs $a=1071$ and $b=462$, which Bézout coefficients satisfy $gcd(a,b)=sa+tb=21$?Answer: $(s,t)=(-3,7)$
5. When does an integer $a$ have a multiplicative inverse modulo a positive integer $m$?Answer: When $gcd(a,m)=1$.