Let $k$ be a positive integer and $m$ be an odd integer. Prove that there exists a positive integer $n$ such that $n^n-m$ is divisible by $2^k$.
Problem
Source: Mexico
Tags: number theory, induction
laikhanhhoang_3011
02.02.2022 17:58
For $k=1,2$:
+) If $m \equiv 1 (\textrm{mod 4})$ then choose $n\equiv 1(\textrm{mod 4})$
+) If $m \equiv 3 (\textrm{mod 4})$ then choose $n\equiv 3(\textrm{mod 4})$
We define $n(k,m):n(k,m)^{n(k,m)}-m\vdots 2^k$
From above we solve for $k=1,2$
Now we will induction, for any $m$, assume exist $n(k,m)$. We will prove exist $n(k+1,m)$
+) If $n(k,m)^{n(k,m)}-m \vdots 2^{k+1}$ then choose $n(k+1,m)=n(k,m)$
+) If $n(k,m)^{n(k,m)}-m \equiv 2^k (\textrm{mod } 2^{k+1})$. We will choose $n(k+1,m)$ in the form $a:n(k+1,m)=a.2^k+n(k,m)$
We need $(a.2^k+n(k,m))^{a.2^k+n(k,m)}-m\vdots 2^{k+1}$, but $(a.2^k+n(k,m))^{a.2^k}-1 \vdots 2^{k+1}$ (LTE)
So we need $(a.2^k+n(k,m))^{n(k,m)}-m\vdots 2^{k+1}$
Apply Newton"s binomial, we neew to choose $a: n(k,m).n(k,m)^{n(k,m)-1}.a2^k+n(k,m)^{n(k,m)}-m \vdots 2^{k+1}$
Which mean $2^k.(n(k,m).n(k,m)^{n(k,m)-1}.a+1) \vdots 2^{k+1}$. Just choose $a$ odd now
Q.E.D