Euclidean algorithm, Bezout identity, modular arithmetic, linear congruences, Chinese remainder theorem and Fermat and Euler theorems.
39 cards · basic cards · AI-written, checked twice. Edit anything.
- What is the Euclidean algorithm?
Show answer
An algorithm to compute the greatest common divisor of two integers using repeated division with remainder.- What is the greatest common divisor (gcd) of two integers a and b?
Show answer
The largest positive integer that divides both a and b.- In the Euclidean algorithm, the process terminates when the remainder equals what?
Show answer
Zero. At that point, the gcd is the last nonzero remainder.- Calculate gcd(48, 18) using the Euclidean algorithm.
Show answer
6. (48 = 18*2 + 12, 18 = 12*1 + 6, 12 = 6*2 + 0)- What does it mean if gcd(a, b) = 1?
Show answer
a and b are coprime (relatively prime), sharing no common positive divisor other than 1.- The Euclidean algorithm terminates in O(log(min(a,b))) time.
Show answer
True. This is shown by Lame's theorem.- State Bezout's identity.
Show answer
For any integers a and b, there exist integers x and y such that ax + by = gcd(a,b).- When do Bezout coefficients x and y exist satisfying ax + by = gcd(a,b)?
Show answer
Always, for any two integers a and b.- How are Bezout coefficients found?
Show answer
Using the extended Euclidean algorithm, working backward through the steps of the standard Euclidean algorithm.- Name one application of Bezout's identity.
Show answer
Finding modular inverses. If ax + by = 1, then ax ≡ 1 (mod b), so x is a modular inverse of a mod b.- What does a ≡ b (mod n) mean?
Show answer
a is congruent to b modulo n, equivalently, n divides (a - b).- If a ≡ b (mod n) and d divides n, what can we conclude about a and b modulo d?
Show answer
a ≡ b (mod d). Congruence modulo n implies congruence modulo any divisor of n.- If a ≡ b (mod n) and c ≡ d (mod n), then a + c ≡ ____ (mod n).
Show answer
b + d- If a ≡ b (mod n) and c ≡ d (mod n), then ac ≡ ____ (mod n).
Show answer
bd- If a ≡ b (mod n), then for any integer c, ac ≡ ____ (mod n).
Show answer
bc
FlashKeepers