8
$\begingroup$

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...

$\endgroup$
5
  • 2
    $\begingroup$ I can prove that all solutions have either $a=2$ or $b=2$ by showing that for $a,b>1$ the numerator must be congruent to $12\pmod{16}$. Dealing with those cases is a little trickier. $\endgroup$
    – Mastrem
    Dec 13, 2021 at 21:37
  • $\begingroup$ Furthermore, if $a=2$ then $b$ must be an odd multiple of $3$. $\endgroup$
    – Mastrem
    Dec 14, 2021 at 9:58
  • $\begingroup$ As noted $\operatorname{min}(a,b)=2$ and without loss of generality $a\leq b$, so it remains to determine for which $b$ the fraction $$\frac{2^{2^b}+b^4+11}{4+2^b},$$ is an integer. Clearly $b$ must be odd. For $b\leq31$ the only solution is $b=3$. $\endgroup$
    – Servaes
    Dec 14, 2021 at 15:27
  • $\begingroup$ @Servaes I don’t have complete clarity here yet - the idea of divisibility by $16$ does not work. The only idea is to write $2^b$ in the number system with the base $b$. But this is somehow cumbersome, and I don't see any elegant arguments. $\endgroup$
    – QLimbo
    Dec 14, 2021 at 16:24
  • 1
    $\begingroup$ Let me spell out the proof that $\min(a,b)=2$. WLOG, assume $a\ge 2$ even and $b\ge 3$ odd. Write $a=2c$, then $a^{2^b}\equiv 2^{2^b}c^{2^b}\equiv 0\pmod{16}$. Moreover, $b^4\equiv 1\pmod{16}$, whence $b^{2^a}\equiv(b^4)^{4^{c-1}}\equiv 1\pmod{16}$. It follows that $a^{2^b}+b^{2^a}+11\equiv 0+1+11\equiv 12\pmod{16}$. Thus, the denominator may be divisible by $4$, but not by $8$. Note that $2^{\min(a,b)}$ divides the denominator, so we must have $\min(a,b)\le 2$. Since we already know that $\min(a,b)\ge 2$, it follows that $\min(a,b)=2$. $\endgroup$
    – Mastrem
    Dec 14, 2021 at 21:51

2 Answers 2

8
$\begingroup$
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.

$\endgroup$
5
  • 1
    $\begingroup$ Thanks! I went roughly this way, but did not reduce it by $4$, considering everything modulo $2^b+4$, which is worse. I don't know about you, but this task doesn't seem natural to me :) $\endgroup$
    – QLimbo
    Dec 15, 2021 at 18:30
  • 1
    $\begingroup$ @Cornifer It's good to know you went the same (or similar) way : indeed, the simplification to $2^{b-2}+1$ helped me streamline the estimation part of the proof, which was the most important part of it. I think the key insight (which is very much non-natural!) is that modulo $2^{b-2}+1$, another number of the form $2^{l}$ can only leave remainders of a certain kind, and then estimation (and remembering powers of some numbers) is your friend. $\endgroup$ Dec 16, 2021 at 9:11
  • 1
    $\begingroup$ I think, if I had guessed to factor out 4, I could have solved it by playing on the fact that the numerator modulo turns out to be small for b>>1. $\endgroup$
    – QLimbo
    Dec 16, 2021 at 16:14
  • 1
    $\begingroup$ In the beginning, I was trying to understand how you are going to connect this bridge of solution. Elegant! $\endgroup$
    – Darshan P.
    Jan 16, 2022 at 7:20
  • 1
    $\begingroup$ @DarshanP. Thanks. If anything, the insight is in Mastrem's argument, along with the key modulo idea of realizing that the set of remainders is heavily restricted. Looking back, it's probably among my favourite ideas I've had on this site. $\endgroup$ Jan 16, 2022 at 12:50
3
$\begingroup$

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.]

$\endgroup$
3
  • $\begingroup$ Is the twice-placed √-surd ($√$) supposed to represent a ✔✓🗸checkmark (heavy$✔$ ⩛ regular$✓$ ⩛ light$🗸$)? $\endgroup$
    – user946772
    Dec 15, 2021 at 5:11
  • $\begingroup$ I write $\surd$ to mean \qed $\endgroup$
    – Mike
    Dec 15, 2021 at 5:13
  • $\begingroup$ The designated monoglyph tombstone, halmos, end-of-proof, or Q.E.D. symbol for math proofs is $∎$, and sometimes for sub-proofs a cut-out version such as $▯$. I do like your mod-congruence subscript form. $\endgroup$
    – user946772
    Dec 15, 2021 at 5:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .