Algorithms
Algorithm implementations and analysis.
Notes / Module
Algorithms
Algorithm implementations and analysis.
1 ordinary note and 1 index note in this branch.
Entrance
Index Note
The readable index note for this branch stays at its flat canonical URL.
Notes
Notes in This Module
Ordinary notes link to their unchanged flat note URLs.
最大公约数与最小公倍数
定理：gcd(a,b) = gcd(b,a mod b) 证明：a可以表示成a = kb + r，则r = a mod b 假设d是a,b的一个公约数，则有 d a, d b，而r = a - kb，因此d r 因此d是(b,a mod b)的公约数 假设d 是(b,a mod b)的公约数，则 d b , d r ，但是a = kb +r 因此d也是(a,b)的公约数 因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证