因數和互質
sjLin
February 27, 2022
最最最大大大公公公因因因數數數- 定定定義義義
假設m, n ∈ Z, m, n ̸= 0, 則g|m且g|n的最大整數稱為m, n的最大公因數(greatest common divisor)，記作g = gcd(m, n)，
有時簡記為g = (m, n)
互互互質質質- 定定定義義義
假設m, n ∈ Z, 若gcd(m, n) = 1, 則稱m與n互質(relatively prime).
定定定理理理
⋇輾轉相除法(Euclidean algorithm)會使用到。
假設m, n ∈ Z且m = an + b，其中a, b ∈ Z, 則gcd(m, n) = gcd(n, b).
gcd(m, n) = gcd(n, m mod n)
1
