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