Chứng minh tồn tại vô hạn trong số học

Đề bài: Cho m là một số nguyên dương. Chứng minh rằng tồn tại vô số nguyên dương n sao cho $m|3.2^n+n$

Lời giải:

Ta sẽ chứng minh quy nạp theo $m$, rõ ràng $m=1,2,3,4$ là hiển nhiên
Giả sử khẳng định đúng với mọi $m\leq t$ với số nguyên $t>3$
Đặt $d=ord_{t+1}{2}$ và $e=gcd(d,t+1)$, rõ ràng $e\leq d \leq \phi (t+1) \leq t$
Theo nguyên lí quy nạp phải tồn tại vô hạn số nguyên $a$ sao cho $e\mid 3\times 2^a+a$
Đặt $3\times 2^a+a=ef$ ( $f\in \mathbb{Z}^+$ )
Với mọi $g\in \mathbb{Z}^+$ Ta có $3\times 2^{a+dg}+(a+dg) \equiv 3  \times 2^a+a+dg =ef+dg (mod t+1)$
Ta cần chứng minh rằng tồn tại $g\in \mathbb{Z}^+$ sao cho $ef+dg\equiv 0 (mod t+1)$
Tương đương với $gcd(d,t+1) \mid -ef\Leftrightarrow e\mid -ef$ (luôn đúng) 9 (điều kiện cần và đủ của phương trình đồng dư)
vậy ta đã chứng minh tồn tại $n_1=a+dg\in \mathbb{Z}^+$ sao cho $t+1 \mid 3\times 2^{n_1}+{n_1}$
Nhưng vì tồn tại vô số nguyên dương a $a$, ta lấy $a$ lớn hơn $n_1$ ta lại có một số nguyên dương khác thỏa mãn đề bài,
Điều này có nghĩa là tồn tại vô số $n\in \mathbb{Z}^+$ sao cho $t+1\mid 3\times 2^n+n$ Điều phải chứng minh.