Find all positive integers $(a,b)$ such that $\displaystyle\frac{a^{2^{b}}+b^{2^{a}}+11}{2^{a}+2^{b}}$ is an integer

Find all positive integers $(a,b)$ such that $\displaystyle\frac{a^{2^{b}}+b^{2^{a}}+11}{2^{a}+2^{b}}$ is an integer.

The machine/code says that $a=2$ and $b=3$ are suitable up to symmetry. And I bet that these are the only solutions when $a≤b$. If $a=0$, then $1+2^b≤b+11$ implies $b≤3$ and the only solution is $b=1$. In a similar way $a=1$ implies $b=0$. Since the formula is symmetrical, we can assume $a,b>1$.

$a$ and $b$ cannot have the same parity, because the numerator will be odd and the denominator will be even, which is impossible. Suppose $a≥2$ is even and $b≥3$ is odd. The pair $(a,b)=(2,3)$ is a solution giving $\displaystyle\frac{a^{2^{b}}+b^{2^{a}}+11}{2^{a}+2^{b}}=29$. For $a=2$, there is no other solution for $b≤25$. For $a=4$ and $a=6$, there is no solution for $b≤25$.

But I don't think this reasoning will be enough for a complete proof...

Solution 1:

Proof plan

• Prove that $\min(a,b) = 2$.

• Prove that , assuming $a=2$, the numerator can actually leave only so many remainders modulo the denominator.

• Prove that for large values of $b$, the remainder cannot be zero.

• Check small values of $b$ using number-specific modular tricks.

Beginning

I begin with Mastrem's excellent argument. Indeed, note that the expression for the candidate dividend is symmetric in $a,b$. Note that if $a,b$ have the same parity then the numerator will be odd while the denominator will be even. Therefore, they have dissimilar parities, and we assume that $a$ is the even number and $b$ the odd one so that $a \geq 2 , b \geq 3$ (note : any of them being equal to $1$ can be checked separately).

Then, writing $a=2c$, we go modulo $16$ on the numerator. Note that $2^b \geq 8$ so $2^8|a^8 | a^{2^b}$, hence $16 | a^{2^b}$. On the other hand, $b^4 \equiv 1 \pmod{16}$ for any $b$ odd, therefore $4 | 2^a$ implies that $b^{2^a} \equiv 1 \pmod{16}$. All in all, $a^{2^b}+b^{2^a}+11 \equiv 12 \pmod{16}$. In particular, the largest power of $2$ dividing the numerator is $4$.

Thus, the largest power of $2$ dividing the denominator should also be at most $4$, for the ratio to be an integer. However, note that $2^{\min(a,b)}$ divides the denominator. Therefore, we are forced to have $\min(a,b) \leq 2$, which by the conditions imposed forces $a = 2$ and $b \geq 3$ is odd. We assume this from now on.

Remainder restriction

Once we know that $b$ is an odd number and $a =2 \leq b$ , then we ask ourselves when $$ \frac{2^{2^b} + b^4+11}{4+2^{b}} $$

is an integer i.e. when $1+2^{b-2}$ divides $2^{2^b} + b^4+11$ (since $4$ already does if $b$ is odd and at least $3$, and $lcm(1+2^{b-2},4) = 4+2^b$). We note that $2^{2^b}$ can only leave certain kinds of remainders modulo $1+2^{b-2}$. Indeed, note that if $2^{b-2} \equiv -1 \pmod{2^{b-2}+1}$. Therefore, if $2^b = k(b-2)+l$ for $0 < l \leq b-3$ (note that $l \neq 0$ as $b-2$ is odd), we get that $$ 2^{2^b} \equiv 2^{k(b-2)}2^l \equiv (-1)^k2^l \pmod{2^{b-2}+1} $$ Therefore, $$ 2^{2^b} + b^4+11 \equiv \pm 2^{l} + b^4+11 \pmod{2^{b-2}+1} $$ for some $l \in \{0,1,...,b-3\}$. The question is, is it possible for the RHS quantity to be equivalent to $0$ modulo $2^{b-2}+1$? For this, some easy estimates are in line.

Note that for large enough $b$, it is true that $2^{b-2}+1 > 2^{b-3}+b^4+11$, therefore for $b-3>l>0$, it is true that $0< 2^l+b^4+11 < 2^{b-2}+1$. On the other hand, note that it is obvious that $-2^{b-3}+b^4+11>-2^{b-2}-1$. Hence, for large enough $b$, it follows that if the expression is equivalent to zero, it literally equals zero i.e. there exists $l \in \{0,1,...,b-3\}$ with $b^4+11 = 2^l$.

So when is $b^4+11 = 2^l$? The answer lies in noting that $b^2 \equiv 1 \pmod{8}$ and therefore $b^4 \equiv 1 \pmod{8}$ for all odd $b$, hence $b^4+11$ cannot be a multiple of $8$ for any odd $b$. Eliminating the small cases, it follows that the equation has no solutions over the integers.

Estimation

Therefore, we are only left to ask, when is $2^{b-2}+1 > 2^{b-3}+b^4+11$? This reduces to $2^{b-3} > b^4+10$, and if one knows their powers of $2$ well (I know I had a dull childhood if I had to memorize powers of $2$), then one sees that $2^{18} = 262144$ and $21^4 < 210000$ so $b=21$ works. One can prove that if the inequality holds for $b$, it does so for $b+1$ as well (by induction). Therefore, there are no solutions for $b \geq 21$ using the logic above.

Finishing the solution

Thus, we are left with $a=2$ and $b$ odd, $b \leq 20$. We can actually do better, though : we have to check if $1+2^{b-2}$ divides $2^{2^b} + b^4+11$, recall. Note that if $b$ is odd, then $1+2^{b-2}$ is actually a multiple of $3$. Therefore, the same should be true of $2^{2^b}+b^4+11$. However, $2^{2^b}+11$ is a multiple of $3$, so it follows that $b^4$ is a multiple of $3$ i.e. $b$ is a multiple of $3$. This leaves only $3,9,15$!

$b=3$ works.

For $b=9$, $1+2^{b-2}$ is a multiple of $43$ by computation, while on the RHS, $9^2 \equiv -5 \pmod{43}$ so $9^4 \equiv 25 \pmod{43}$, and $2^{2^9} \equiv 2^{512} \equiv 2^{8} \equiv 41 \pmod{43}$ (using Euler's theorem with $\phi(43) = 42$), so the RHS modulo $43$ is $41+25+11 \neq 0 \pmod{43}$.

For $b=15$, the LHS $1+2^{b-2} = 8193$ is a multiple of $2731$ (yes, I'm stretching far here, bear with me!) while on the RHS, $2^{2^{15}} = 2^{32768}\equiv 2^8 = 256 \pmod{2731}$, and $15^4 \equiv 1467 \pmod{2731}$,so the RHS modulo $2731$ is $1467 + 256+11 \neq 0$.

It follows that $a=2,b=3$ is the only solution.

Solution 2:

As noted by the comments one of $a,b$, say $b$ must be $2$ and the parity of $a$ and $b$ must differ. So let us assume that $a$ is odd.

We first make the following claim:

Claim 1: Let $c$ and $a'$ be nonnegative integers. Then for some nonegative integer $d\le a'$ the equation holds: $$2^c \equiv_{2^{a'}+1} \pm 2^d.$$

Proof: Induction on $c$. Clearly true for $c \le a'$. Now $2^{a'+1} \equiv_{2^{a'}+1} -1$ so $$2^{c} \quad = \quad 2^{c-a'}2^d \quad \equiv_{2^{a'}+1} \quad -1 \times 2^{c-a'} \pmod{(2^{a'}+1)}.$$ However, by the induction hypothesis, there is an integer $d' \le a'$ such that the equation $$2^{c-a'} \equiv_{2^{a'}+1} \pm 2^{d'}$$ holds, so from this Claim 1 follows. $\surd$

Claim 2: For an integer $a>31$ the strict inequality $$a^4+11<2^{a-3}$$ holds.

Proof: Induction on $a$. Check directly for $a=31$, and then note that $(a+1)^4+11 < 2×(a^4+11)$, whereas $2^{(a+1)-3} = 2×2^{a-3}$. So informally, the RHS of the inequality, already larger than LHS, at least doubles when $a$ increases by $1$, whereas the LHS does not increase by such a large factor. $\surd$

We now use this to show there is no solution $(a,b)$ with $a$ odd and $a>31$, and with $b=2$. To this end, with $b=2$ and $a$ odd, the denominator becomes $4 \times 2^{a-2}+1$, and the numerator becomes $a^4+2^{2^a}+11$. Thus, it suffices to show that $2^{a-2}+1$ cannot divide $11+a^4+2^{2^{a}}$ for $a > 31$. Now, by the Claim 1, $$2^{2^{a}} \equiv_{2^{a-2}+1} \pm 2^d$$ for some nonegative integer $d \le a-2$. We consider 2 cases:

Case 1: $ \ 2^{2^{a}} \equiv_{2^{a-2}+1} -2^d$ for some nonnegative integer $d$. Then for $2^{a-2}+1$ to divide $11+a^4+2^{2^{a}}$, the equation $a^4+11-2^d \equiv_{2^{a-2}+1} 0$ must hold. So from this the following holds:

For there to be an integer $a>31$ such that $2^{a-2}+1$ divides $11+a^4+2^{2^{a}}$ for some nonnegative integer $d$, there has to be such an $a,d$ for which either the equation (a) $a^4+11-2^d=0$ or the equation (b) $a^4+11-2^d =n \times (2^{a-2}+1)$ holds.

However, there is no such $a,d$ that satisfies either of these equations (a), (b). [Indeed, the equation $a^4+11-2^d=0$ does not hold for any nonnegative integers $a,d$. [Indeed, checking mod 16, this cannot hold $d \ge 4$. And by exhaustive search this cannot hold for $d \le 4$ either.] And as the strict inequality $a^4+11< 2^{a-2}$ holds for $a>31$ by Claim 2, the equation $a^4+11-2^d =n \times (2^{a-2}+1)$ cannot hold for any nonnegative integer $d$ and any integer $a \ge 31$ either.]

Case 2: $ \ 2^{2^{a}} \equiv_{2^{a-2}+1} + 2^d$ for some nonnegative integer $d$. Then we can assume that $d<a-2$ otherwise revert to Case 1. But then $|2^{a-2}-2^d| \ge 2^{a-3}$, so the only way that $a^4+11+2^d$ is a multiple of $2^{a-2}+1$ is if $a^4+11$ is at least $|2^{a-2}-2^d|$ $\ge$ $2^{a-3}$, and this is impossible for $a \ge 31$ by Claim 2.

So we have indeed shown that there are no solutions $(a,b)$ with $a >31$ and $b=2$. So we can then reasonably finish the original problem simply by checking directly each of the $16$ solutions $(2k+1,2)$; $k=0,1,2,\ldots, 15$ [or we can trust Servaes' calculations in the Comments.]