Chứng minh tồn tại số tự nhiên thỏa mãn yêu cầu bài toán

Bài toán:

Cho trước $k\in \mathbb{Z}^+$ và $m$ lẻ .

Chứng minh rằng tồn tại $n\in \mathbb{Z}^+$ sao cho $2^k| n^n-m$

Lời giải:

Ta sẽ chứng minh quy nạp theo $k$.

Trường hợp $k=1$ là hiển nhiên, chọn $n=1$.

Giả sử rằng tồn tại $n$ sao cho $2^k|n^n-m$,Đặt $n=n_0$ hay $2^k|n_0^{n_0}-m$ hiển nhiên $n_0$ lẻ

Tiếp theo xét 2 trường hợp

$1)$ Nếu $2^{k+1} | n_0^{n_0}-m$

Rõ ràng chỉ cần chọn $n=n_0$.

$2)$ Nếu $2^{k+1}$ Không là ước của $n_0^{n_0}-m$.

Đặt $n_0^{n_0}-m=u\cdot 2^k$ Với $u$ lẻ và theo định lý Euler,Cho mọi số lẻ $a$ ta có $a^{2^{k}}\equiv 1\pmod{2^{k+1}}$,Vì thế

$(2^k+n_0)^{2^k+n_0}-m=(2^k+n_0)^{2^k}\cdot (2^k+n_0)^{n_0}-m\equiv (2^k+n_0)^{n_0}-m\\\equiv n_0^{n_0}+n_0\cdot n_0^{n_0-1}\cdot 2^k-m=(u+n_0^{n_0})2^k\equiv 0\pmod{2^{k+1}}$ Vì cả $u$ và $n_0$ đều lẻ.

Vì thế $n=2^k+n_0$ thỏa mãn, nên ta có đpcm