41-я Балканская математическая олимпиада. Варна, Болгария, 2024 год

Пусть $a$ и $b$ — различные положительные целые числа такие, что $3^a + 2$ делится на $3^b + 2$. Докажите, что $a > b^2$. ( Ануарбеков Т. )

Комментарий/решение

Пусть $a = bk + r$ , где $0 \leq r < b$ тогда имеем $3^b + 2 \mid 3^{bk+r} + 2 = (3^b)^k \cdot 3^r + 2 $ и имеем $3^b \equiv -2 \pmod {3^b + 2}$ поэтому $\Rightarrow$ $ (3^b)^k \cdot 3^r + 2 \equiv (-2)^k \cdot 3^r + 2 \pmod {3^b+2}$

Случай 1: $2 \nmid k$

Тогда $3^b+2 \mid 2^k \cdot 3^r - 2$ $\Rightarrow$ $3^b+2 \mid 2^{k-1} \cdot 3^r - 1$. Пусть $2^{k-1} \cdot 3^r = 3^bn+2n+1$, так как $0 \leq r < b$ (Очевидно $r \ne 0$), то имеем $\Rightarrow$ $3^r \mid 2n+1$ $\Rightarrow$ $n \geq \frac{3^r-1}{2} $

Lemma: Если $2^{k-1} \cdot 3^r \geq \frac{3^{b+r} - 3^b}{2} + 3^r$ то $k>b$

Proof: Пусть $b \geq k$ , то $2^{k-1} \cdot 3^r \geq \frac{3^{b+r} - 3^b}{2} + 3^r$ $\Rightarrow$ $2^{k-1} \geq \frac{3^{b} - 3^{b-r}}{2} + 1$ тогда имеем $\Rightarrow$ $2^b \geq 2^{k} \geq 3^{b} - 3^{b-r} + 2 \geq 3^{b-1} + 2$ так имеем $2^b \geq 3^{b-1} + 2$ что неверно при любом натуральном $b.$

Вернемся к задаче. Заметим что $2^{k-1} \cdot 3^r = 3^bn+2n+1 \geq \frac{3^{b+r} - 3^b}{2} + 3^r$. По лемме $k>b$ откуда $a = bk +r > b^2 + r \geq b^2$

Случай 2: $2 \mid k$

Тогда $3^b+2 \mid 2^k \cdot 3^r + 2$ $\Rightarrow$ $3^b+2 \mid 2^{k-1} \cdot 3^r + 1$. Пусть $2^{k-1} \cdot 3^r = 3^bn+2n-1$ , так как $0 \leq r < b$ (Очевидно $r \ne 0$), то имеем $\Rightarrow$ $3^r \mid 2n-1$ $\Rightarrow$ $n \geq \frac{3^r+1}{2} $, Тогда видим что $2^{k-1} \cdot 3^r = 3^bn+2n-1 \geq \frac{3^{b+r} + 3^b}{2} + 3^r \geq \frac{3^{b+r} - 3^b}{2} + 3^r$. По лемме $k>b$ откуда $a = bk +r > b^2 + r \geq b^2$