Prove that for each positive integer $a$ there exists such an integer $b>a$, for which $1+2^a+3^a$ divides $1+2^b+3^b$.
Problem
Source: Polish MO Finals 2015
Tags: contests, number theory
28.07.2016 06:03
Let $1 + 2^a + 3^a = 2^{e_2}3^{e_3}p_4^{e_4} \cdots p_n^{e_n}$. Lemma: $e_2 \le 2$. Proof: $a \le 2$ can be verified by hand, otherwise, observe that $3^a$ is $1$ or $3$ modulo $8$, so \[ 1 + 2^a + 3^a \equiv 1 + 3^a \equiv 2 \quad \text{or} \quad 4 \pmod{8} \] Then I claim any sufficiently large $b$ satisfying the following system of linear congruences is sufficient. \begin{align*} b &\equiv a \pmod{\phi{(p_4^{e_4})}} \\ b &\equiv a \pmod{\phi{(p_5^{e_5})}} \\ b &\equiv a \pmod{\phi{(p_n^{e_n})}} \\ \cdots \\ b &\equiv 0 \pmod{3^{e_3}} \\ b &\equiv 3 \pmod{4} \end{align*} is enough for the condition. We will check the valuations of each prime and show $1 + 2^b + 3^b$ has at least as high of a valuation as $1 + 2^a + 3^a$, first $p \ge 5$, then $p = 2$, and lastly $p = 3$. First of all, I claim that any such $b$ satisfies $1 + 2^b + 3^b \equiv 0 \pmod{p_k^{e_k}}$ for $k \ge 4$. Indeed, observe that \[ 1 + 2^b + 3^b \equiv 1 + 2^a + 3^a \equiv 0 \pmod{p_k^{e_k}} \]. Next, since $b \equiv 3 \pmod{4}$ (and $b > 3$ from sufficiently large condition) it can be shown that $1 + 2^b + 3^b$ has $2$-adic valuation of two, and moreover this is maximal. Hence, the only valuation left to check is $3$-adic. But in this case, recall that for odd numbers $n$, LTE gives us that \[ v_3(1 + 2^n) = v_3(3) + v_3(n) = 1 + v_3(n) \] \[ 1 + 2^b + 3^b \equiv 1 + 2^b \pmod{3^{e_3}} \]Now, observe that from LTE, \[v_3(1 + 2^b) = 1 + v_3(b) \ge 1 + e_3 \ge e_3 \], so we have checked the valuations of each prime and hence we are done by the Chinese Remainder theorem.
28.07.2016 06:03
24.12.2023 00:25
Lol, this problem is a joke. Let $1+2^a+3^a = X$ Note $v_2(1+2^a+3^a) \leq 2$, then by CRT ensure $b \equiv a \mod \phi({p_i}^{v_{p_i}(X)})$ for $p_i \neq 2,3 | 2^a+3^a+1$ $b \equiv 0 \mod{3^{v_3(X)}} $ $b \equiv 3 \mod{4} $ Clearly this works by LTE for $p=3$, euler's thm for $p_i \neq 2,3$, mod bash for $p=2$