Prove that for any natural numbers $a , b , c$ that $b>a>1$ and $gcd(c,ab)=1$ , there exist a natural number $n$ such that : $$c | \binom{b^n}{a^n}$$ Proposed by Navid Safaei
Problem
Source: Iran Team selection test 2024 - P9
Tags: number theory
28.05.2024 13:29
bump pls
28.05.2024 18:38
see below solution.
31.05.2024 13:25
Unfortunately the above solution is wrong, because to choose a large $k'$ so that $(b^{xy})_p=(\dots 0001)_p$ (or even $k$), then by LTE $x$ must be divisible by $p$, but your claim is that $x$ is only divisible by primes less than $p$.
31.05.2024 14:28
Any ideas how to fix it?
31.05.2024 15:44
WLOG, $a \equiv b \equiv 1 \pmod{c}$ because we can replace $(a,b)$ with $(a^{\phi(c)},b^{\phi(c)})$. It suffices to prove for the case $c=p^k.$ Why? If $c$ has $t$ primes factor $p_1,p_2,\dots,p_t$, choose a large $k$ and let $n_i$ be the integer such that $p_i^k$ divides $\binom{b^{n_i}}{a^{n_i}}$, then choose $n \equiv n_i \pmod {p_i^T}$ for some LARGE $T \gg b^{n_1n_2\dots n_i}$, then we see that $a^n \equiv a^{n_i} \pmod{p_i^T}$ and $b^n \equiv b^{n_i} \pmod{p_i^T}$ by LTE (recall $a \equiv b \equiv 1 \pmod{c}$, so it happens), thus the number of carries of $b^n-a^n$ in the $p_i$-th ary representation is no less than the number of carries of $b^{n_i}-a^{n_i}$ in the $p_i$-th ary representation. Hence we can easily see that if $p_i^k~|~\binom{b^{n_i}}{a^{n_i}}$ it holds that $p_i^k~|~\binom{b^{n}}{a^{n}}$ for all $i$ as well, hence $c~|~(p_1p_2\dots p_t)^k~|~\binom{b^{n}}{a^{n}}$ , and we are done. We consider $3$ cases when $c=p^k$. For notation, for an integer $b=\sum_{i=0}^q b_i p^i$ where $0 \leq b_i \leq p-1$, we denote its $p$-ary representation as $(b)_p=(b_qb_{q-1} \dots b_1b_0)_p$. Case 1) $v_p(b-1) >v_p(a-1)$. In this case, if $(a)_p=(\dots a_m \underbrace{00 \dots 0}_{(m-1)\times0}1)_p$ where $a_m \neq 0$ and $m=v_p(a-1)$, it holds that $(b)_p=( \dots \underbrace{ 00 \dots 0}_{m\times0}1)_p$ where $a_m \neq 0$ . Consider a LARGE $k'$. We can choose $n$ such that $(a^n)_p=(\dots \underbrace{(p-1)(p-1)\dots (p-1)}_{k'\times(p-1)} a_m 00 \dots 01)_p$ (and this means that $a^n \equiv a \pmod{p^{m+1}}$). In this, case, we can prove that $b^{n} \equiv b \pmod{p^{m+1}}$ as well, since $v_p(b-1)>v_p(a-1)$, thus $(b^n)_p=( b_{k'}b_{k'-1} \dots b_{m+1} \underbrace{00 \dots 0}_{m\times0}1)_p$. We easily see that since $b_i \leq p-1$ for all $m+1 \leq i \leq k'$ and $a_m>0, b_m=0$, $a_i=p-1$ for all $m+1 \leq i \leq k'$ then there are at least $k$ carries in $b^n-a^n$ when $k'$ is large, and we are done. Case 2) $v_p(b-1) <v_p(a-1)$. Let $(b)_p=(\dots b_m \underbrace{00 \dots 0}_{(m-1)\times0}1)_p$ where $b_m \neq 0$ and $m=v_p(b-1)$ choose a LARGE $k'$ such that $(b^n)_p= (\underbrace{\dots 00\dots 0}_{(k'-m) \times 0} \dots b_m \underbrace{00 \dots 0}_{(m-1)\times0}1)_p$ (meaning that $v_p(b^n-1)=v_p(b-1)$) where $b_m \neq 0$, then it also holds that $(a^n)_p=\dots \underbrace{00 \dots 0}_{m\times0}1$ as well, since $v_p(b-1) <v_p(a-1)$. Now, from position $m+1$ to $k'-k$, if there is any digit of $a^n$ greater than $0$, then there are at least $k$ carries in $b^n-a^n$, done. Otherwise, all the digits of $a^n$ from position $m+1$ to $k'-k$ must be all zero. Hence $(a^n)_p=(\dots \underbrace{00 \dots 0}_{(k'-k) \times 0}1)_p$, or $a^n \equiv 1 \pmod{p^{k'-k+1}}$, hence $n \equiv 0 \pmod {k'-k+1-v_p(a-1)}$, a contradiction, since $v_p(b^n-1)=v_p(b-1)$, thus $v_p(n)=0$. Case 3) Finally, we are left with the case $v_p(a-1)=v_p(b-1)$. Thus we can write $(a)_p=(\dots a_m \underbrace{00 \dots 0}_{(m-1)\times0}1)_p$, $(b)_p=(\dots b_m \underbrace{00 \dots 0}_{(m-1)\times0}1)_p$ with $a_m,b_m \neq 0$. WLOG, we assume $b_m \leq a_m$, otherwise we can just REPLACE $a,b$ with $a^x,b^x$ for some $x$ not divisible by $p$ so that $b_m \leq a_m$. In this case, choose $n$ such that $(a^n)_p=(\dots \underbrace{(p-1)(p-1)\dots (p-1)}_{k'\times(p-1)} a_m 00 \dots 01)_p$ for some LARGE $k'$. Now if $b_m<a_m$, then similar to case 1) we are done. Otherwise, consider $b_m=a_m$. Note that, in $b^n$, if there is any digit less than $p-1$ from $m+1$ to $k'-k$, then there are at least $k$ carries in $b^n-a^n$, done. Hence, we must have $(b^n)_p=(\dots \underbrace{(p-1)(p-1)\dots (p-1)}_{(k'-k)\times(p-1)} a_m 00 \dots 01)_p$, thus $b^n \equiv a^n \pmod {p^{k'-k+1}}$, or $n \equiv 0 \pmod {k'-k+1-v_p(a-b)}$, however, which is a contradiction since $v_p(a^n-1)=v_p(a-1)$, thus $v_p(n)=0$. Thus, in any case, there is some $n$ such that $p^k$ divides $\binom{b^n}{a^n}$, as desired.