Để chứng minh rằng CM: 3^n + 5^n + 7^n + 9^n chia hết cho 12 khi n là số lẻ, ta sẽ sử dụng định lí Euler.

Định lí Euler: Nếu a và m là hai số nguyên tố cùng nhau, thì a^(phi(m)) ≡ 1 (mod m), trong đó phi(m) là hàm phi Euler và cho biết số số nguyên tố cùng nhau với m trong khoảng từ 1 đến m.

Ta biết rằng 3 và 12 là hai số nguyên tố cùng nhau, vì vậy ta có 3^(phi(12)) ≡ 1 (mod 12).

Ta tính phi(12):
- Các số từ 1 đến 12 có dạng 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12.
- Các số nguyên tố cùng nhau với 12 là 1, 5, 7, 11.
- Vậy phi(12) = 4.

Do đó, ta có 3^4 ≡ 1 (mod 12).

Tương tự, ta có 5^4 ≡ 1 (mod 12), 7^4 ≡ 1 (mod 12), 9^4 ≡ 1 (mod 12).

Vì n là số lẻ, nên ta có thể viết n = 2k + 1, với k là số nguyên không âm.

Áp dụng định lí Euler, ta có:
3^n + 5^n + 7^n + 9^n ≡ 3^(2k+1) + 5^(2k+1) + 7^(2k+1) + 9^(2k+1) ≡ 3*3^(2k) + 5*5^(2k) + 7*7^(2k) + 9*9^(2k) ≡ 3*1 + 5*1 + 7*1 + 9*1 ≡ 3 + 5 + 7 + 9 ≡ 0 (mod 12).

Vậy ta kết luận rằng CM: 3^n + 5^n + 7^n + 9^n chia hết cho 12 khi n là số lẻ.