Let $n{}$ be a positive integer and let $a{}$ and $b{}$ be positive integers congruent to 1 modulo 4. Prove that there exists a positive integer $k{}$ such that at least one of the numbers $a^k-b$ and $b^k-a$ is divisible by $2^n.$ Cătălin Liviu Gherghe
Problem
Source: Romania TST 2024 Day 1 P3
Tags: number theory, Divisibility
31.07.2024 16:54
Maybe similar to Bulgaria IMO TST 2020 (not completely sure)? EDIT: Below solution with structure of units mod $2^n$ confirms this.
31.07.2024 22:57
The condition of mod 4 motivate to use lte and that is the hint
01.08.2024 02:08
Here's a solution using some group theory notation to show what is actually the true nature of the problem, although one doesn't actually need any deep results: It is well known that \begin{align} \mathbb Z/2^{n-2} \mathbb Z \times \mathbb Z/2 \mathbb Z &\cong \left(\mathbb Z/2^n \mathbb Z \right)^* \\ (k,p) &\mapsto (-1)^p \cdot 5^k \end{align}Suppose $a$ corresponds to $(k,p)$, and $b$ corresponds to $(l,q)$. The condition that they are conguent to $1 \bmod 4$ implies that $p =q = 0$. Thus, it suffices to show that given any two elements $k,l \in \mathbb Z/2^{n-2} \mathbb Z$, one is a multiple of the other, but this is clear by looking at highest power of $2$ dividing $k,l$. $\blacksquare$
01.08.2024 18:29
Also similar to St. Petersburg 2018 9.6.
01.08.2024 23:26
We prove by induction that $2^{n}$ divides $a^{k} - b$ or $b^{k} - a$ for every $n \ge \nu_2(a-1) \ge \nu_2(b-1)$. For the base case, take $k = 2^{\nu_2(a-1)-1}$. We get that $2^{\nu_2(a-1)} \mid (b^{\nu_2(a-1) - 1} - 1) - (a - 1)$. Now suppose there exists $k$ such that $2^{n} \mid b^{k} - a$ for a sufficiently large $n$. Case 1. $2^{n+1} \mid b^{k} - 1$ just take the same $k$. Case 2. $b^{k} - a\equiv2^{n}\pmod{2^{n+1}}$ we have that $\nu_2(b^{k}-a) = n$ take $k' = k + \alpha$ and rewrite $b^{k+\alpha} - a=b^{k}(b^{\alpha} - 1) - (a-b^{k})$. From LTE we get that $\nu_2(b^{k}(b^{\alpha}-1)) = \nu_2(b^{\alpha}-1) = \nu_2(b-1) + \nu_2(\alpha) < n + \nu_2(\alpha)$ so we can choose $\alpha$ such that $\nu_2(b^{\alpha}-1) = n$ and since $\nu_2(a-b^{k}) = n$ we get that $\nu_2(b^{k'} - a) > n$ and we are done because this implies that $2^{n+1} \mid b^{k'} - a$.
03.09.2024 10:36
This problem is almost the same as a problem from Saint-Petersburg olympiad 2018 https://artofproblemsolving.com/community/c35h1776999_divisibly_and_existance_from_saint_petersburg_olympiad