九至十二年级Number计划中
Divisibility, Euclid's algorithm and unique factorisation
Divisibility of integers, greatest common divisors, Euclid's algorithm, Bézout's identity and a proof of the fundamental theorem of arithmetic.
math.number.divisibility-gcd
本主题的课程尚未编写。下面的提纲是课程地图的一部分，尚未经过审校。
前置知识
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