4. Các định lí số học quan trọng

Ta nhắc lại một số tính chất của ước chung lớn nhất và bội chung nhỏ nhất.

Gọi \(\gcd(a, b)\) là ước chung lớn nhất của hai số nguyên \(a\) và \(b\).

1. Với mọi số nguyên dương \(a\), \(\gcd(a, a) = a\).

2. Với mọi số nguyên \(a\) và \(b\) thì \(\gcd(a, b) = \gcd(b, a)\). Đây là tính giao hoán của ước chung lớn nhất.

3. Mọi ước chung của \(a\) và \(b\) sẽ chia hết \(\gcd(a, b)\).

4. Với mọi số nguyên \(m\) thì \(\gcd(a + m b, b) = \gcd(a, b)\). Tương tự, \(\gcd(a \bmod b, b) = \gcd(a, b)\).

5. Với mọi số nguyên \(m\) thì \(\gcd(m a, m b) = m\gcd(a, b)\).

6. Nếu \(\gcd(a, b) = d\) thì \(\gcd(a/d, b/d) = 1\).

Định lý 4.1

Với mọi số nguyên dương \(a\), \(m\), \(n\) ta có

\[\gcd(a^m - 1, a^n - 1) = a^{\gcd(m, n)} - 1.\]

Chứng minh

Không mất tính tổng quát, giả sử \(m \geqslant n\). Ta có

\[\begin{split}\gcd(a^m - 1, a^n - 1) & = \gcd(a^m - 1 - (a^n - 1), a^n - 1) \quad (\text{tính chất} \ \gcd(a, b) = \gcd(a + mb, b)) \\ & = \gcd(a^{n}(a^{m-n} - 1) + a^n - 1, a^n - 1),\end{split}\]

mà \(\gcd(a^n, a^n - 1) = 1\) nên

\[\gcd(a^n(a^{m-n} - 1), a^n - 1) = \gcd(a^{m-n} - 1, a^n - 1).\]

Thực hiện tương tự, cuối cùng ta có

\[\gcd(a^m - 1, a^n - 1) = \gcd(a^{m \bmod n} - 1, a^n - 1).\]

Đặt \(m_1 = m \bmod n\), lúc này \(m_1 < n\). Thực hiện tương tự nhưng với chiều ngược lại

\[\gcd(a^{m_1} - 1, a^n - 1) = \gcd(a^{m_1} - 1, a^{n - m_1} - 1) = \cdots = \gcd(a^{m_1} - 1, a^{n \bmod m_1} - 1).\]

Đây chính là thuật toán Euclid nhằm tìm ước chung lớn nhất (ở đây thực hiện trên số mũ). Do đó số mũ cuối cùng sẽ là ước chung lớn nhất giữa \(m\) và \(n\).