Prove that there are infinitely many integers which cannot be expressed as $2^a+3^b-5^c$ for non-negative integers $a,b,c$.
Problem
Source: Czech and Slovak Olympiad 2019, National Round, Problem 5
Tags: number theory, national olympiad
07.06.2019 13:48
We have \begin{align*} 2^a \pmod{120} &\in \{ 1, 2, 4, 8, 16, 32, 64 \} \\ 3^b \pmod{120} &\in \{ 1, 3, 9, 27, 81 \} \\ 5^c \pmod{120} &\in \{ 1, 5, 25 \} \end{align*}Residue class of $2^a + 3^b - 5^c \pmod{120}$ have at most $3\times 5 \times 7 = 105$ elements, so non-residue class of $2^a + 3^b - 5^c$ have at least 15 elements. This means there exist $n$ so that $2^a + 3^b - 5^c \equiv n \pmod{120}$ have no solution. So every integer in form of $120k + n$ for all $k$ integer can't be expressed as $2^a + 3^b - 5^c$.
07.06.2019 14:38
First note that for expressing odd numbers we should have $a=0$ so the problem is equelent to showing infinity many even numbers cannot be expressed as $3^b-5^c$ but this expression is never divisible by $3$ so we are done.
09.06.2019 13:59
Taha1381 wrote: $3^b-5^c$ is never divisible by 3 $b=0, c\equiv0\pmod2$ ?
13.06.2019 20:21
byk7 wrote: Taha1381 wrote: $3^b-5^c$ is never divisible by 3 $b=0, c\equiv0\pmod2$ ? Oops.I missed that case but it can be easily fixed since then the number is not divisible by $5$.
19.06.2019 18:58
Actually if b=0 our number must be negative, so we cant write positive numbers in that form and we are done
30.04.2021 13:49
We will show that there is a residue class (modulo $120$) whose elements cannot be written in this form. This implies the result. Note that $ 2^{7}\equiv 8$ (mod 120), $3^{5}\equiv 3$ (mod 120) and $5^{3}\equiv 5$ (mod 120). Thus the powers of $2,3$ and $5$ only have $7, 5$ and $3$ possible remainders modulo 120. Therefore the expression $2^{a}+3^{b}-5^{c}$ can only be an element of at most $7\cdot 5\cdot 3=105$ different residue classes modulo $120$, meaning that there are least $15$ residue classes containing no integers of this form.