Fix integers $a$ and $b$ greater than $1$. For any positive integer $n$, let $r_n$ be the (non-negative) remainder that $b^n$ leaves upon division by $a^n$. Assume there exists a positive integer $N$ such that $r_n < \frac{2^n}{n}$ for all integers $n\geq N$. Prove that $a$ divides $b$. Pouria Mahmoudkhan Shirazi, Iran
Problem
Source: RMM 2024 Problem 4
Tags: RMM, number theory, remainder, size
29.02.2024 23:36
Let $n$ be large. If $b^n=ka^n+r_n$, then $b^{n+1}=kba^n+br_n$. Then, $r_{n+1}\equiv br_n\pmod{a^n}$. Since $br_n,\frac{2^{n+1}}{n+1}<a^n$, we must actually have $r_{n+1}=br_n$ for all large $n$, which eventually contradicts $r_n<\frac{2^n}n$ unless $r_n=0$, implying $a\mid b$.
29.02.2024 23:47
Knock knock Zhautykov 2021/1
29.02.2024 23:55
$r_n\equiv b^n(mod \ a^n)$ and $\frac{2^n}{n}>r_n$ for all $n\geq N$. Let $b^n=a^n.k_n+r_n$ Take $d=gcd(a,b)$ and $a=dx,b=dy$. \[d^ny^n=d^nx^n.k_n+r_n\]\[d^n(y^n-x^n.k_n)=r_n\]Let $r_n=d^n.s_n$. \[y^n-x^nk_n=s_n<\frac{2^n}{n.d^n}=(\frac{2}{d})^n.\frac{1}{n}\]We have $s_n\geq 0$. Case $1$:$d=1$ \[y^n-x^nk_n=s_n<\frac{2^n}{n}\]If $s_n=0$, then $x^n|y^n\implies x=1\implies a|b$. We have $x\geq 2$. Let $s_n\geq 1$. $y^n=x^nk_n+s_n$ $x^nyk_n+ys_n=y^{n+1}=x^{n+1}k_{n+1}+s_{n+1}\implies x^n(yk_n-xk_{n+1})=s_{n+1}-ys_n$ If $s_{n+1}-ys_n=0,$ then $s_{n+1}=ys_n\implies \frac{s_{n+1}}{s_n}=y$ For $n\geq N$, we have $\frac{2^{n+k}}{n+k}>s_{n+k}=s_n.y^k$ \[\frac{2^{n+k}}{n+k}>y^k\iff 2^{n+k}>(n+k)y^k\geq (n+k)2^k\implies 2^n>n+k\]We can take $k$ sufficiently large which results in a contradiction. If $s_{n+1}-ys_n>0,$ then $x^n|s_{n+1}-ys_n\implies 2^{n}\leq x^n<s^{n+1}<\frac{2^{n+1}}{n+1}\implies n<1$ which gives a contradiction. Case $2: d\geq 2$. So we have \[0\leq y^n-x^nk_n=s_n<\frac{1}{n}<1\]Hence $y^n=x^nk_n\iff k_n=\frac{y^n}{x^n}$ and $(x_n,y_n)=1\implies x=1$ and $k_n=y^n$. Thus $a=d^n|d^ny^n=b$
01.03.2024 00:00
China TST 2007 anyone?
01.03.2024 11:21
R8kt wrote: China TST 2007 anyone? Which problem? I did not find a similar one, can you please give a link?
01.03.2024 12:12
Assassino9931 wrote: R8kt wrote: China TST 2007 anyone? Which problem? I did not find a similar one, can you please give a link? Well to me, this problem seemed similar in nature: https://artofproblemsolving.com/community/c6h247841p1359751 You also have to construct a recursive sequence and prove by inequalities that it must increase.
01.03.2024 17:35
Indeed, the ideas from the IZhO problem are sufficient to solve this one as well.
02.03.2024 03:11
Suppose $a \nmid b$ and note that $$b^n \equiv r_n \pmod{a^n}$$ Case 1: If $\gcd(a, b) = d \in [2, a-1]$, then $d^n \mid r_n$ and this gives us $$2^n \leq d^n \leq r_n < \frac{2^n}{n} < 2^n$$which is a contradiction. Case 2: If $\gcd(a, b) = 1$, then $s a + t b = 1$ for some integer $s, t$ such that $|s| < b$ and $|t| < a$. Since $$b^{n+1} \equiv r_{n+1} \pmod{a^{n+1}} \Longrightarrow b^{n+1} \equiv r_{n+1} \pmod{a^n} \Longrightarrow br_n \equiv r_{n+1} \pmod{a^n}$$We get $$tr_{n+1} \equiv tbr_n = (1 - sa) r_n\pmod{a^n}$$On the other hand $$|tr_{n+1} - (1 -sa)r_{n}| \leq \frac{2^{n+1}|t|}{n+1} + \frac{2^n|1-sa|}{n} < 2^n \leq a^n$$for all sufficiently large $n$. This means $$tr_{n+1} = (1 - sa)r_{n} \Longrightarrow r_{n+1} = br_n$$for all $n \geq N$ for some $N$. Then $$r_{n} = b^{n-N}r_N \geq 2^{n-N}r_N > \frac{2^n}{n}$$for all sufficiently large $n$ and this is a constradiction.
02.03.2024 04:38
03.03.2024 03:53
Here is my solution(I think it is very intuitive and easy to come up with) Case 1: There exists a natural number $n$ such that $r_{n}=0$ Then we have $a^n|b^n$ which gives us that $a|b$ (It follows by writing $a=d.x$, $b=d.y$, where $d=\gcd (a, b)$) Case 2: Suppose that none of the residues is $0$. Suppose that there exists a positive integer $N$ such that $r_n < \frac{2^n}{n}$ for all integers $n\geq N$. Let $m$ be the smallest natural number such that $m\geq N$ and $m.(\frac{a}{2})^m>b$. We know that such number exists, because $m.(\frac{a}{2})^m$ is strictly increasing and $b$ is fixed. Choose $n \geq m$. We have the following: $b^n\equiv r_n \pmod {a^n}$ $\iff a^n|b^n-r_n$ $(1)$ $b^{n+1}\equiv r_{n+1} \pmod {a^{n+1}}$ $\iff a^{n+1}|b^{n+1}-r_{n+1}$ $\implies a^{n}|b^{n+1}-r_{n+1}$ $(2)$ To get rid of the "nasty" $b^n$, we can multiply $(1)$ by $b$ and we have $a^n|b^{n+1}-r_{n}b$ $(3)$ Now from $(2)$ and $(3)$ we have $a^n|b^{n+1}-r_{n+1}-(b^{n+1}-r_{n}b)\iff a^n|r_{n}b-r_{n+1}$. Note that this is true for all integers $n\geq N$. Now we can use the property that if $x|y$, then $y=0$ or $|x|\leq|y|$ Suppose that there exists an integer $n \geq m$ such that $a^n \leq | r_{n}b-r_{n+1}|$. We have 2 cases: Case 2.1 $r_{n}b>r_{n+1}$. Then we must have $a^n \leq r_{n}b-r_{n+1}<r_{n}b<b.\frac{2^n}{n}$. But from $n\geq m$ we have $b<n.(\frac{a}{2})^n$ Hence we have $a^n<b.\frac{2^n}{n}<n.(\frac{a}{2})^n.\frac{2^n}{n}=a^n$, contradiction! Case 2.2 $r_{n}b<r_{n+1}$. Then we must have $a^n\leq r_{n+1}-r_{n}.b<r_{n+1}<\frac{2^{n+1}}{n+1}=\frac{2}{n+1}.2^n \leq a^n$, contradiction! Hence we have $r_{n}b-r_{n+1}=0 \iff r_{n}b=r_{n+1}$ for all $n\geq m$. Inductively, we have $r_{m+k}=r_{m}.b^k$ for all positive integers $k$. Now let's pick the smallest positive integer $k$ such that $k\geq \frac{2^m}{r_{m}}-m$. Consider the number $r_{m+k}$ $r_{m+k}=r_{m}.b^k\geq r_{m}.2^k=2^k.\frac{2^n}{\frac{2^n}{r_{m}}-m+m}\geq 2^k.\frac{2^m}{m+k}=\frac{2^{m+k}}{m+k}$, but this is a contradiction! Hence we have a contradiction in the case where none of the residues is $0$. Hence, $a|b$. $\blacksquare$
03.03.2024 21:25
To be clear, the sharp bound really is $\frac{a^n}{b}$ instead of $\frac{2^n}{n}$ (assuming $a<b$ as the other case is trivial). Indeed, if $r_n$ is the remainder, then $r_{n+1}-br_n$ is a multiple of $a^n$. But since $r_{n+1} \ne br_n$ infinitely often (unless it's always zero in which case $a \mid b$), this means that either $r_{n+1}>a^n>\frac{a^{n+1}}{b}$ or $br_n>a^n$, in both cases implying our conclusion.
03.03.2024 23:59
Knock knock, who's there? It's the worst solution on earth. Assume wlog that $\gcd(a,b)=1$. As usual, we will let $\{x\}$ denote the fractional part of $x$. Let $m$ and $M$ be positive integers we add restrictions to throughout the problem. Let $t=b/a$ We first note that for large $n$ we have \[ \frac{2^n}{n} > r_n = a^n \cdot \left \{ \frac{b^n}{a^n} \right \} \implies \left \{ t^n \right \} < \frac{1}{n} \left ( \frac{2}{a} \right )^n = \frac{q^n}{n} \] where $q \leq 1$. Thus, we have \[ \left \{ \left ( t \right )^M \right \} < \frac{q^M}{M} \text{ and } \left \{ t^{M+m} \right \} < \frac{q^{M+m}}{M+m}\]Moreover, \[ \left \{ t^{M+m} \right \} = \left \{ t^{m} \cdot t^{M} \right \} = \left \{ t^{m} \cdot (K+r) \right \} \] Where $K$ in the integer part and $r$ is the fractional part. We may rewrite the above expression as... \[ \left \{ t^{m} \cdot K+ t^{m} \cdot r \right \} \] First, note that $\left \{ t^{m} \cdot K \right \} \leq \frac{a^m-1}{a^m}$ since it is rational with denominator $a^m$. Moreover, note that $\left \{ t^{m} \cdot r \right \} < \frac{q^n}{n} \cdot t^m$ Which gets arbitrarily small by making $M$ very large compared to $m$. But, \[\left \{ t^{m} \cdot K \right \} + \left \{ t^{m} \cdot r \right \} < \frac{a^m-1}{a^m} + \frac{q^n}{n} \cdot t^m < 1 \] Forl large enough $M$. Recall that if $\{x\} + \{y\} < 1$ then $\{x\} + \{y\} = \{x+y\}$. Thus, \[ \left \{ t^{m} \cdot K+ t^{m} \cdot r \right \} = \left \{ t^{m} \cdot K \right \} + \left \{ t^{m} \cdot r \right \} \geq \left \{ t^{m} \cdot K \right \} \] Recall that $K = \left \lfloor t^M \right \rfloor$. Now, we claim that one can choose $M$ so that $\left \{ t^{m} \cdot K \right \} > 0$. Indeed, recall that $t=\frac{b}{a}$. So, we want \[ \left \{ \frac{Kb^m}{a^m} \right \} > 0 \implies a^m \nmid Kb^m \implies a^m \nmid K\] Claim: Given any $m$ where $a^{m-1}> \frac{b}{a}$, one may find infitely many positive integers $e$ for which $a^m \nmid \left \lfloor \left ( \frac{b}{a} \right )^e \right \rfloor$. Assume the contrary, we have $t^e \in [\ell_0 a^m, \ell_0 a^m+1) \implies t^{e+1} \in [\ell_0 b a^{m-1}, \ell_0 b a^{m-1} + b/a )$ Note that if $a \nmid \ell_0$ then the interval does not contain a multiple of $a^m$. (Recall that $b/a<a^{m-1}$). Thus, $a \mid \ell_0$. So, if we let $\ell_1 = \frac{b\ell_0}{a}$ we then get $t^{e+1} \in [\ell_1 a^m, \ell_1 a^m+1)$. Recursing gives $\ell_k = \frac{b^k}{a^k} \ell_0$ which cannot be an integer for large enough $k$. $\square$ Thus, by setting $m$ to be large enough, we may find a suitable $K$ where \[ \left \{ \frac{Kb^m}{a^m} \right \} > 0 \implies \left \{ \frac{Kb^m}{a^m} \right \} \geq \frac{1}{a^m} \] Thus, what we have been building up to, the following amazing chain of inequalities. \[ \frac{1}{a^m} \leq \left \{ \frac{Kb^m}{a^m} \right \} \leq \left \{ t^{m} \cdot K+ t^{m} \cdot r \right \} = \{t^{M+m} \} < \frac{q^{m+M}}{M+m} \]Trivially, the RHS gets arbitrarily close to zero as $M$ gets large, and thus cannot exceed the LHS for all suitable $M$. This yields our desired contradiction. $\blacksquare$
07.03.2024 12:32
Note that for big $n$, $b^n \equiv r_n \pmod{a^n}$ and $b^{n+1} \equiv r_{n+1} \pmod{a^n}$, so \[ r_{n+1} \equiv br_n \pmod{a^n}. \]Now for arbitrarily large $n$, $r_{n+1} < a^n$, and $br_n < a^n$. Thus for sufficiently large $n$, $r_{n+1}=br_n$, which implies $b<2$ or $r_n=0$. The latter clearly holds.
07.03.2024 12:47
Does this work? Suppose the contrary. It is clear that $br_n \leq \frac{2^n}{n} \cdot b < a^n$ for all sufficiently large values of $n$. This implies that the remainder $b^{n+1}$ leaves upon division by $a^n$ is equal to $br_n$. Since $a^n \mid a^{n+1}$ the remainder $b^{n+1}$ leaves dividing by $a^{n+1}$ has to be greater than the remainder it leaves dividing by $a^n$. This implies that $r_{n+1} \geq br_n$ for all sufficiently large $n$, which is obviously absurd. $\blacksquare$
15.03.2024 11:38
Assume that $\frac{b}{a}=\frac{p}{q}$ where $(p,q)=1$ and $q>1$. It's even not possible that $r_n<\varepsilon_n a^n$, where $\lim_{n\to \infty}\varepsilon_n =0$, that is, it's not possible that $r_n=o(a^n)$. Assume on the contrary it holds. Thus, $$b^n=ka^n+\varepsilon_n a^n.$$Multiplying both sides by $b$ it yields $$b^{n+1}=k\frac{b}{a}a^{n+1}+\varepsilon_n \frac{b}{a}a^{n+1}.$$It means that $$\varepsilon_{n+1}=k\frac{p}{q}+\varepsilon_n \frac{p}{q} \mod 1.$$Now, for sufficiently large $n$ we have $\varepsilon_n \frac{p}{q}<\frac{1}{q}$, since $\varepsilon_n\to 0$. Note that $k\frac{p}{q}$ is either integer or its distance to the nearest integer is at least $1/q$. It gives us $\varepsilon_{n+1}>\varepsilon_n$. This leads us to contradiction if we take a special $\varepsilon_n$ such that $\varepsilon_i<\varepsilon_n, \forall i>n$. It is possible since $\varepsilon_n\to 0$. Remark. The portion of NT in this problem is very small. The same idea as in Izho 2021 p1.
07.06.2024 20:18
We uploaded our solution https://calimath.org/pdf/RMM2024-4.pdf on youtube https://youtu.be/2afMLcv6ZUA.
21.06.2024 20:28
The case $b< a$ is obvious so assume $a\leq b$. Notice that for all $n\geq N$ we have that $ r_n\cdot b\equiv r_{n+1}\pmod{a^n}$. Assume that $n$ is also larger than $b$. Then by the assumtion of the question $r_n<\frac{2^n}{n}<\frac{a^n}{b}$. Also have $r_{n+1}<\frac{2^{n+1}}{n+1}<a^n$. Thus the equivalence is actually an equality and $r_n\cdot b=r_{n+1}$. In order for the inequality to remain true we must have $r_n=0$ for some $n$. Thus $a^n|b^n$ or $a|b$.
17.11.2024 17:32
Suppose the condition was satisfied for some $a,b$ with $a\nmid b$. Note that for each $n$, $r_n$ is positive integer. If $a > b$, then $r_n = b^n$ exceeds $\frac{2^n}{n}$ for large enough $n$, a contradiction. Thus, $a < b$. Claim: $r_{n+1} = b \cdot r_n$ for all $n > N$. Proof: Suppose otherwise. Note that $b^n \equiv r_n \pmod{a^n}$, so if we let $b^n = k a^n + r_n$ for some positive integer $k$, multiplying both sides by $b$ gives that $b^{n+1} = kb a^n + b r_n$. This means that $r_{n+1}$ is $br_n$ modulo $a^n$. Let $r_{n+1} = x\cdot a^n + b r_n$ for some positive integer $x$. We then have $r_{n+1} > x a^n \ge a^n$. Since $n + 1 > N$, $a^n < \frac{2^{n+1}}{n+1}$ must hold. However, since $n > 1$, $\frac{2^{n+1}}{n+1} < \frac{2^{n+1}}{2} = 2^n \le a^n$, a contradiction. Therefore, $r_{n+1} = b \cdot r_n$. $\square$ Now fix some $m > N$. We can inductively get $r_{m+k} = b^k r_m$. This implies that \[ b^k r_m < \frac{2^{m + k}}{m + k} \implies \left( \frac b2 \right)^k < \frac{2^m }{(m + k) \cdot r_m} < \frac{2^m}{m \cdot r_m}\](which is true as $r_m > 0$). Since $1 < a < b$, $b > 2$, so choosing $k$ large enough gives a contradiction. Thus, we must have $a\mid b$.