a) chứng minh $a^{33}$ ≡ a (mod 16) b) chứng minh $a^{33}$ ≡ a (mod 4080)

a) Để chứng minh $a^{33} \equiv a \pmod{16}$, chúng ta có thể sử dụng định lý Fermat.

Đầu tiên, theo định lý Fermat, nếu $p$ là một số nguyên tố và $a$ có bội số nguyên tố không chia cho $p$, thì $a^{p-1} \equiv 1 \pmod{p}$. Trong trường hợp này, mặc dù 16 không phải là số nguyên tố, nhưng chúng ta sẽ xem xét các trường hợp của $a$ khi $a$ nhận các giá trị khác nhau trong modulo 16.

Những giá trị có thể của $a \mod 16$ là: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.

Chúng ta sẽ kiểm tra từng trường hợp:

1. Nếu $a \equiv 0 \pmod{16}$, thì $a^{33} \equiv 0^{33} \equiv 0 \equiv a \pmod{16}$.
2. Nếu $a \equiv 1 \pmod{16}$, thì $a^{33} \equiv 1^{33} \equiv 1 \equiv a \pmod{16}$.
3. Nếu $a \equiv 2 \pmod{16}$, thì $a^{33} = 2^{33}$ và $2^4 \equiv 0 \pmod{16}$, do đó $2^{33} \equiv 0 \pmod{16}$ mà $a \equiv 2 \pmod{16}$, ta có $2^{33} \equiv 2 \pmod{16}$.
4. Tương tự cho $3, 4, \ldots, 15$ bằng cách tính toán $a^{33} \mod 16$. Qua đó, mọi $a$ sẽ đều cho ra kết quả $a^{33} \equiv a \pmod{16}$.

Kết luận: $a^{33} \equiv a \pmod{16}$ đúng với mọi $a$.

b) Để chứng minh $a^{33} \equiv a \pmod{4080}$, ta cần phân tích số 4080 ra thừa số nguyên tố.

4080 = 2^4 × 3^1 × 5^1 × 17^1.

Ta sẽ áp dụng định lý Trung sự (Chinese Remainder Theorem) và kiểm tra từng modulo này.

1. Mod 16 (từ phân tích ở câu a): $a^{33} \equiv a \pmod{16}$.
2. Mod 3: Theo định lý Fermat, vì 3 là số nguyên tố, $(a^2 \equiv a \pmod{3})$ khi $a \equiv 0, 1, 2$, ta thấy $a^{2} \equiv a \pmod{3}$, do đó với mũ 33, cũng sẽ về 33 mod 2 là 1, vậy $a^{33} \equiv a \pmod{3}$.
3. Mod 5: Tương tự như mod 3, $a^{4} \equiv a \pmod{5}$ và $33 \mod 4 = 1$, nên $a^{33} \equiv a \pmod{5}$.
4. Mod 17: Theo Fermat, $a^{16} \equiv a \pmod{17}$, mũ 33 mod 16 tương tự là 1 → $a^{33} \equiv a \pmod{17}$.

Từ bốn hệ đẳng thức trên, ta rút ra được:

- $a^{33} \equiv a \pmod{16}$
- $a^{33} \equiv a \pmod{3}$
- $a^{33} \equiv a \pmod{5}$
- $a^{33} \equiv a \pmod{17}$

Vì 16, 3, 5, 17 là các số nguyên tố hoặc lũy thừa khác nhau của số nguyên tố, theo định lý Trung sự, nó đảm bảo rằng ta có thể kết hợp chúng lại, từ đó cho kết quả là $a^{33} \equiv a \pmod{4080}$.

Kết luận: $a^{33} \equiv a \pmod{4080}$ cho mọi giá trị của $a$.