Find all positive integers $a$ such that for any positive integer $n\ge 5$ we have $2^n-n^2\mid a^n-n^a$.
Problem
Source: China Lanzhou 18 Aug 2013
Tags: induction, modular arithmetic, number theory proposed, number theory
18.08.2013 13:38
Nice problem!
19.08.2013 13:21
Let $p \in \mathbb{P}$ such that $p|a$. If possible, suppose that $p\ge 3$. Let $n=p-1$. Therefore, $p|2^{p-1}-(p-1)^2|a^{p-1}-(p-1)^a$. But, $p|a \implies p|(p-1)^a$, a clear contradiction. As a result, we infer that either $a=1$ or $a=2^k$. Case I: $a=1 \implies 2^n-n^2|1-n \implies 2^n-n^2|n-1 \forall n \in \mathbb{N}$, but $\forall n \ge 5$, $2^n-n^2 >n-1$, contradiction. Case II: $a=2^k \implies 2^n-n^2|2^{kn}-n^{2^k}$. Since $a-b|a^m-b^m \forall m \in \mathbb{N}$, we have \[2^n-n^2|2^{kn}-n^{2k}\]. \[ 2^n-n^2|n^{2^k}-n^{2k} \] If $k=2$ or $1$, this is obvious. Let $n = 2^{2^k} \implies 2^{2^{2^k}}-2^{2^{k+1}} \le 2^{2^{2k}}-2^{k.2^{k+1}}$, and by induction, this clearly impossible for $k \ge 3$. Therefore, $a=2$ or $a=4$.
20.08.2013 02:45
Very Nice!
20.08.2013 08:44
The 2013 China West Mathematics Invitation Competition was held in the high school affiliated to northwest normal university from 15th Aug. to 19th Aug with 21 representative teams including 105 teenager talents for mathematics taking part in, who come from different regions or countries covering 14 provinces or cities such as Beijing, Chongqing, Shaanxi, Gansu, Guangxi, Guizhou, Hainan, Jiangxi, Ningxia, Qinghai, Sichuan, Xinjiang, Yunnan, etc. and Hong Kong Special Administrative Region as well as some foreign countries like Singapore, Kazakhstan, Indonesia and so on. The Examiners Committee of this competition consists of several professors or experts from different universities or high schools such as Shanghai University, Peking University, University of Macau, Lanzhou University, East China Normal University, and the High School Attached to Renmin University of China, the High School Attached to Hunan Normal University and so forth.
27.08.2013 05:00
There is a better proof that a friend of mine found at the actual competition.
27.08.2013 13:02
DVDthe1st wrote: There is a better proof that a friend of mine found at the actual competition.
Wow!! It is really nice !! Thank you very much.
27.08.2013 13:55
Good to know that Chineses used my problem http://www.artofproblemsolving.com/Forum/viewtopic.php?f=57&t=495826
24.03.2020 09:29
sqing wrote: Find all positive integers $a$ such that for any positive integer $n\ge 5$ we have $2^n-n^2\mid a^n-n^a$. $2^n-n^2\mid a^n-n^a$. $\therefore 2^n-n^2\mid a^{2n}-n^{2a}$. But $2^n-n^2\mid 2^{na}-n^{2a}$. So $2^n-n^2\mid a^{2n}-2^{na}$. Choose prime $p$ s.t. $p$ is greater than $a^2$ and $2^a$. $n=p-1\implies 2^{p-1}-(p-1)^2\mid a^{2(p-1)}-2^{(p-1)a}$. Fermat's little theorem $\implies p\mid 2^a-a^2\implies 2^a-a^2=0$ $\implies a =$ $2$ or $4$. Checking we find that $(2,4)$ indeed satisfy the condition.
01.06.2023 15:42
Let $p>|2^a-a^2|$ be a prime and $n=p(p-1)+2.$ Then $2^n=(2^{p-1})^p\cdot 2^2\equiv 2^2\pmod p,n^2\equiv 2^2\pmod p.$ Therefore $p\mid 2^n-n^2\Rightarrow p\mid a^n-n^a.$ However $a^n=(a^{p-1})^p\cdot a^2\equiv a^2\pmod p,n^a\equiv 2^a\pmod p.$ Then $0\equiv a^n-n^a\equiv 2^a-a^2\pmod p.$ Using $|2^a-a^2|<p,2^a-a^2=0,a=2$ or ${4}{}$ which is both true$.\blacksquare$
06.04.2024 23:24
Taking $n$ even, we get that $a$ is even, so $a=2k$ $2^n-n^2 | (2k)^n-(2^k)^n$. Now if $p | 2^n-n^2$, then $(2^k)^n \equiv (2k)^n (mod p)$, so either $(n,p-1)>1$, or $2^k-2k \vdots p$. Now take any big prime $p$ such that $2$ is a quadratic residue mod $p$. By Chinese Remainder Theorem there exist $n$ such that $n \equiv \sqrt{2}$ (mod $p$) and $n \equiv 1$ (mod $p-1$). So $p | 2^n-n^2$ and $(n,p-1)=1$, so $2^k-2k \vdots p$. Because we can take $p$ arbitrarily large, $2^{k-1}=k$, so $k=1$ or $2$, so $a=2$ or $4$, both work