Để tìm số dư trong phép chia 68^345 chia cho 63, ta sẽ sử dụng định lý Fermat nhỏ:

Nếu a và n là hai số nguyên tố cùng nhau, thì a^(φ(n)) ≡ 1 (mod n), trong đó φ(n) là hàm số Euler, cho biết số lượng số nguyên tố nhỏ hơn n và cùng nhau với n.

Trong trường hợp này, 63 = 3^2 * 7, nên φ(63) = (3^2 - 3^1) * (7^1 - 7^0) = 6 * 6 = 36.

Vì 68 và 63 không cùng nhau (vì 68 chia hết cho 4 trong khi 63 không chia hết cho 4), nên chúng ta không thể áp dụng định lý Fermat nhỏ trực tiếp.

Tuy nhiên, chúng ta có thể sử dụng tính chất của số dư trong phép chia để giảm bớt số mũ:

68^345 ≡ (63 + 5)^345 (mod 63)

Với mọi số nguyên dương k, ta có công thức nhị thức Newton:

(63 + 5)^345 ≡ 63^345 + 345 * 63^344 * 5 + ... + 345 * 63 * 5^344 + 5^345 (mod 63)

Vì 63 chia hết cho 63, nên tất cả các số hạng trừ số hạng cuối cùng đều bị chia hết cho 63. Do đó, ta chỉ quan tâm đến số hạng cuối cùng:

(63 + 5)^345 ≡ 5^345 (mod 63)

Bây giờ chúng ta có thể sử dụng định lý Fermat nhỏ, với a = 5 và n = 63:

5^(φ(63)) ≡ 5^36 ≡ 1 (mod 63)

Do đó:

5^345 ≡ (5^36)^9 * 5 ≡ 1^9 * 5 ≡ 5 (mod 63)

Vậy số dư trong phép chia 68^345 chia cho 63 là 5.