Determine all pairs of positive integers $(a,n)$ with $a\ge n\ge 2$ for which $(a+1)^n+a-1$ is a power of $2$.
Problem
Source: ITAMO 2016, Problem 4
Tags: number theory
bobthesmartypants
12.05.2016 03:28
$(a+1)^n+a-1=2^x\implies 2^x\equiv 0\pmod{a}\implies a=2^m$. So $(2^m+1)^n+2^m-1=2^x$. Obviously $x \ge n$.
Then using Binomial Theorem $$(2^m+1)^n+2^m-1= 2^{mn}+\dbinom{n}{1}2^{m(n-1)}+\cdots +\dbinom{n}{n-2}2^{2m}+\dbinom{n}{n-1}2^m+1+2^m-1$$$$=2^{mn}+\dbinom{n}{1}2^{m(n-1)}+\cdots +\dbinom{n}{n-2}2^{2m}+(n+1)2^m$$Since $a=2^m\ge n$, $v_2((n+1)2^m) \le 2m$ with equality if $n=2^m-1$. If $n\ne 2^m-1$, then $v_2((n+1)2^m) < 2m$ so $$x=v_2(2^x)=v_2\left(2^{mn}+\dbinom{n}{1}2^{m(n-1)}+\cdots +\dbinom{n}{n-2}2^{2m}+(n+1)2^m\right) <2m$$$$\implies 2^{mn}+\dbinom{n}{1}2^{m(n-1)}+\cdots +\dbinom{n}{n-2}2^{2m}+(n+1)2^m < 2^{2m}$$$$\implies n=2\implies 2^x=2^{2m}+3\cdot 2^m=2^m(2^m+3)\implies m=0\implies a=1$$contradiction with $a\ge 2$. Else $n=2^m-1$ so $$v_2\left(2^{mn}+\dbinom{n}{1}2^{m(n-1)}+\cdots +\dbinom{n}{n-2}2^{2m}+(n+1)2^m\right) =v_2\left( 2^{mn}+\cdots +\dbinom{n}{n-3}2^{3m}+2^{2m}\left(\dfrac{(2^m-1)(2^m-2)}{2}+1\right)\right)$$$$=v_2\left(2^{mn}+\cdots +\dbinom{n}{n-3}2^{3m}+2^{2m}\left(2^{2m-1}-2^m-2^{m-1}+2\right)\right)\le 2m+1\text{ if }m\ge 3$$so if $m\ge 3$ then $2^{mn}+\dbinom{n}{1}2^{m(n-1)}+\cdots +\dbinom{n}{n-2}2^{2m}+(n+1)2^m \le 2^{2m+1}\implies n=2$ which we already know has no solutions. Otherwise $m\le 2$. If $m=1$ then $a=2$ so $3^n+1$ needs to be a power of $2$. However, since $3^n+1\equiv 2\text{ or }4\pmod{8}$, $3^n+1=2\text{ or }4$ both impossible when $n\ge 2$. If $m=2$ then $n=2^2-1=3$ and $a=4$ so the only solution is $(n,a)=(3,4)$
@Below: thanks, I thought I was missing something obvious. It's still an interesting question to try to solve the diophantine $2^x=3+5^y$; is there an elementary solution?
shinichiman
12.05.2016 10:01
bobthesmartypants wrote: It's still an interesting question to try to solve the diophantine $2^x=3+5^y$; is there an elementary solution? It is interesting indeed. Here is my solution with the help of calculator to find modulo for big number.
We see that $(x,y)=(2,0),(3,1),(7,3)$. Now, we need to show that there is no solution for $y \ge 4$. We rewrite the equation as $$2^7 \left( 2^{x-7}-1 \right)= 5^3 \left( 5^{y-3}-1 \right).$$Then $\nu_2 \left( 5^{y-3}-1 \right) = 2+ \nu_2(y-3)=7$ implies $\nu(y-3)=5$. Hence, $17 \mid 2^{16}-1 \mid 5^{y-3}-1$ so $17 \mid 2^{x-7}-1$ implies $8 \mid x-7$. The equation becomes
$$2^7 \left( 2^{8a}-1 \right)= 5^3 \left( 5^{2^5b}-1 \right), \; 2 \nmid b.$$After observing that $257=2^8+1= \gcd \left( 2^{8}+1, 5^{2^7}+1 \right)$ it suffices to consider modulo $8$ of $b$. We have $b \equiv 1,3,5,7 \pmod{8}$.
$$\begin{tabular}{c|c}
b \text{(mod 8)} & RHS \text{(mod 257)} \\ \hline
1 & 14 \\
3 & 224 \\
5 & 243 \\
7 & 33 \end{tabular}$$On the other hand, we have $2^7 \left( 2^{8a}-1 \right) \equiv 128((-1)^a-1) \in \{ 0,1 \} \pmod{257}$.
Thus, there is no solution for $y \ge 4$. The solutions are $(x,y)=(2,0),(3,1),(7,3)$.
shinichiman
13.05.2016 14:07
Let $(a+1)^n+a-1=2^b$. Since $a \mid (a+1)^n+a-1=2^b$ so $a=2^c$ with $c \le b$. Dividing both side by $a=2^c$ gives us $$(2^c+1)^{n-1}+(2^c+1)^{n-2}+ \cdots + (2^c+1)+2=2^{b-c}.$$Or we can write it as $(2^ck+n-1)+2=2^{b-c}$ or $2^ck+n+1=2^{b-c}$. This follows that $\nu_2(n+1) \ge c$ (otherwise there will exist an odd factor in LHS) or $a \mid n+1$. Note that $a \ge n \ge 2$ so $a=n+1=2^c$.
Now, using Binomial theorem to get $(2^c+1)^i=2^{2c} \cdot K + 2^c i+1$ so
\begin{align*} LHS & =2^{2c}A+2^c \cdot \frac{(n-1)n}{2}+n+1 \\ & = 2^{2c}A+2^{c+1} \left( 2^{2c-2}-2^{c-2}-2^{c-1}+1 \right). \; (A \ge 1) \end{align*}We can't find $b$ for $c=1$. For $c=2$ then $a=4,n=3$.
For $c \ge 3$ then from above implies $2 \nmid 2^{2c-2}-2^{c-2}-2^{c-1}+1$. We combine this with $c+1<2c$ to follow that there exists an odd factor in $LHS$, which is a contradiction.
Thus, the only solution is $a=4,n=3$.