Divisibility, Euclid's algorithm and unique factorisation

يعتمد على

عدد المتطلبات السابقة الإلزامية (حتى الأساس): 11

ستتعلّم

• Compute gcd(a, b) with Euclid's algorithm and express it as ax + by.
• Prove Euclid's lemma: if a prime p divides ab, then p divides a or p divides b.
• Prove the existence and uniqueness of prime factorisation.

تعريف

• a | b means b = ak for some integer k.
• gcd(a, b), for a and b not both zero, is the greatest integer dividing both.
• Integers a and b are coprime if gcd(a, b) = 1.

مبرهنة

• Bézout: if a and b are not both zero, there are integers x and y with ax + by = gcd(a, b).
• Euclid's lemma holds for every prime p.
• Fundamental theorem of arithmetic: every integer n > 1 is a product of primes, uniquely apart from order.
• Euclid's algorithm terminates because the remainders strictly decrease.

مفاهيم خاطئة شائعة

• Thinking unique factorisation is obvious; it fails in some number systems and needs proof.
• Assuming that if d divides ab then d divides a or b when d is not prime; 4 divides 2 · 2 but not 2.
• Confusing the greatest common divisor with the least common multiple.

يقود إلى

اكتشافات اختيارية

• Rings, ideals and fields Euclid's algorithm works in any Euclidean domain, such as polynomials over a field or the Gaussian integers ℤ[i], which therefore also have unique factorisation.
• Algorithms, correctness and efficiency Lamé's theorem: the number of division steps in Euclid's algorithm is at most five times the number of decimal digits of the smaller number.

قراءات إضافية

• G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers (1938)
• Ivan Niven, Herbert S. Zuckerman and Hugh L. Montgomery, An Introduction to the Theory of Numbers