Chứng minh rằng tồn tại số nguyên dương k sao cho 29^k- 1 chia hết cho 10^4

Để chứng minh rằng tồn tại số nguyên dương \( k \) sao cho \( 29^k - 1 \) chia hết cho \( 10^4 \), chúng ta sẽ chứng minh điều này bằng cách áp dụng định lý chu kỳ nhỏ (Lifting The Exponent Lemma) và định lý số dư Trung bình (Chinese Remainder Theorem).

Trước tiên, chúng ta cần phân tích số \( 10^4 \):

\[
10^4 = 2^4 \cdot 5^4
\]

Vậy nhiệm vụ của chúng ta là chứng minh rằng:

1. \( 29^k - 1 \) chia hết cho \( 2^4 \)
2. \( 29^k - 1 \) chia hết cho \( 5^4 \)

### 1. Chứng minh \( 29^k - 1 \) chia hết cho \( 2^4 \)

Ta sẽ tìm chu kỳ của \( 29 \) modulo \( 16 \) (bởi vì \( 2^4 = 16 \)).

\[
29 \equiv 13 \mod 16
\]

Ta sẽ tính một vài lũy thừa của \( 13 \) mod \( 16 \):

- \( 13^1 \equiv 13 \mod 16 \)
- \( 13^2 \equiv 169 \equiv 9 \mod 16 \)
- \( 13^3 \equiv 13 \cdot 9 \equiv 117 \equiv 5 \mod 16 \)
- \( 13^4 \equiv 13 \cdot 5 \equiv 65 \equiv 1 \mod 16 \)

Như vậy chu kỳ \( 13 \) mod \( 16 \) là \( 4 \). Khi \( k \) là bội số của \( 4 \), ta sẽ có:

\[
29^k \equiv 1 \mod 16 \implies 29^k - 1 \equiv 0 \mod 16
\]

### 2. Chứng minh \( 29^k - 1 \) chia hết cho \( 5^4 \)

Ta cũng sẽ tìm chu kỳ của \( 29 \) modulo \( 625 \) (bởi vì \( 5^4 = 625 \)).

Trước tiên, kiểm tra \( 29 \) mod \( 625 \):

Sử dụng định lý Fermat, vì \( 29 \) và \( 625 \) là coprime (vì \( 625 = 5^4 \) và \( 29 \) không phải là bội số của \( 5 \)), ta có:

\[
\phi(625) = 625 \times (1 - \frac{1}{5}) = 625 \times \frac{4}{5} = 500
\]

Để tìm chu kỳ chính xác, ta cần kiểm tra lũy thừa của \( 29 \):

- \( 29^1 \equiv 29 \mod 625 \)
- \( 29^2 \equiv 841 \equiv 216 \mod 625 \)
- \( 29^4 = (29^2)^2 \equiv 216^2 = 46656 \equiv 431 \mod 625 \)
- \( 29^5 \equiv 29 \cdot 431 \equiv 12599 \equiv 599 \mod 625 \)
- \( 29^{10} \equiv 599^2 = 358801 \equiv 426 \mod 625 \)
- \( 29^{20} = (29^{10})^2 \equiv 426^2 = 181476 \equiv 226 \mod 625 \)
- Cứ tiếp tục cho đến khi \( 29^{100} \equiv 1 \mod 625 \).

Ta sẽ sớm có được chu kỳ là \( 100 \).

### Kết hợp lại

Từ 2 chu kỳ mà chúng ta nhận được:

- \( k \) phải là bội số của \( 4 \) cho \( 2^4 \).
- \( k \) phải là bội số của \( 100 \) cho \( 5^4 \).

Bội số nhỏ nhất chung của \( 4 \) và \( 100 \) chính là \( 100 \). Vậy, ta có thể chọn \( k = 100 \).

### Kết luận

Từ đó, tồn tại số nguyên dương \( k = 100 \) sao cho \( 29^k - 1 \) chia hết cho \( 10^4 \).

Chúng ta đã chứng minh thành công.