Một số bài toán hay về lý thuyết chia hết

Một vài quy tắc cần biết

Ta giả sử các số nói trong bài này đều là số nguyên dương.

1. Nếu $m$ vừa chia hết cho $a$, vừa chia hết cho $b$ và $a$ và $b$ nguyên tố cùng nhau (nghĩa là GCD(a,b)=1) thì $m$ chia hết cho $a.b$.

2. Nếu $a\equiv b$ (mod $m$) và $c\equiv d$ (mod $m$) thì

$a+c \equiv b+d$ (mod $m$)

$a-c \equiv b-d$ (mod $m$)

$ac \equiv bd\qquad \ \ $ (mod $m$)

3. Định lý Fermat: Nếu $p$ là số nguyên tố, $a$ không chia hết cho $p$ thì $a^{p-1} \equiv 1$ (mod $p$).

3. Định lý Euler: Nếu $a$ và $m$ nguyên tố cùng nhau thì $a^{\varphi(m)} \equiv 1$ (mod $m$), trong đó $\varphi(m)$ là số các số nguyên tố cùng nhau với $m$.

BÀI TẬP

1. Chứng minh rằng với mọi số tự nhiên $k$ ta có $\large 2^{2^{6k+2}}+3$ chia hết cho $19$.

GIẢI

Ta có $2^6=64\equiv 1$ (mod $9$), do đó $2^{6k}\equiv 1$ (mod $9$) với mọi $k \in \mathbb{N}$. Suy ra $2^{6k+2} \equiv 4$ (mod $9$), $\Rightarrow 2^{6k+2} -4 \equiv 0$ (mod $9$), nghĩa là $2^{6k+2} -4$ chia hết cho $9$, ngoài ra nó cũng chia hết cho 2 nên nó chia hết cho $18$. Vậy $2^{6k+2}-4=18t$ với $t\in \mathbb{N}$.

Theo định lý Fermat ta có: $2^{18} \equiv 1 $ (mod $19$) nên $2^{18t} \equiv 1 $ (mod $19$).

Vậy $2^{2^{6k+2}}=2^{18t+4}\equiv 2^4 $ (mod $19$) $\Rightarrow 2^{2^{6k+2}}+3\equiv 19$ (mod $19$) $\Rightarrow 2^{2^{6k+2}}+3\equiv 0$ (mod $19$) (đpcm).

2. Chứng minh rằng $2^{70}+3^{70}$ chia hết cho $13$.

Theo định lý Fermat ta có $2^{12}\equiv 1$ (mod $13$). Do đó $2^{60} \equiv 1$ (mod $13$).

Ngoài ra $2^{10} \equiv 10$ (mod $13$)

Vậy $2^{70} \equiv 10$ (mod $13$).

Ta có $3^3\equiv 1$ (mod $13$), suy ra $3^{69} \equiv 1$ (mod $13$). Do đó $3^{70} = 3^{69}.3 \equiv 3 $ (mod $13$).

Tóm lại $2^{70}+3^{70} \equiv 10+3$ (mod $13$), nghĩa là $2^{70}+3^{70} \equiv 0$ (mod $13$). (đpcm).

BÀI TẬP KỲ SAU:

Hướng dẫn: Có thể thực hiện trên máy tính Casio fx-880BTG và cũng có thể chứng minh bằng Phương pháp truyền thống (Đây là bài toán được xuất bản năm 1970 thời kỳ chưa có máy tính như hiện nay).

About TS. Nguyễn Thái Sơn

Nguyên trưởng Khoa Toán-Tin học ĐHSP TP HCM (1999-2009). Nguyên Giám đốc- Tổng biên tập NXB ĐHSP TP HCM (2009-2011). Nguyên Tổng thư ký Hội Toán học TP HCM (2008-2013).