For which positive integer couples $(k,n)$, the equality $\Bigg|\Bigg\{{a \in \mathbb{Z}^+: 1\leq a\leq(nk)!, gcd \left(\binom{a}{k},n\right)=1}\Bigg\}\Bigg|=\frac{(nk)!}{6}$ holds?
Problem
Source: Turkey 2021 IMO TST Problem 9
Tags: Turkey, number theory, GCD
27.05.2021 01:57
Let $p|n$ be a prime divisor of $n$. Then let us write $k$ in the base of $p$. Let $k=(a_{m-1}a_{m-2}...a_1a_0)_p$ where $m\leq k$. Then we want $p \nmid {a\choose k}$. Let $(nk)!=p^m A$ clearly this is true since $p^m|p^k|(nk)!$ Then let $a=p^m B +(c_{m-1}c_{m-2}...c_1c_0)_p$ therefore we have $0\leq B<A$ and for all $j=0,1,..,m$ we have $c_j \geq a_j$ from Lucas Theorem. Which means that in $(mod \; p^m)$ the number $a$ can take exactly $(p-a_{m-1})(p-a_{m-2})...(p-a_1)(p-a_0)$ values. So the ratio of the numbers $a$ with $p \nmid {a\choose k}$ is equal to $\frac{(p-a_{m-1})...(p-a_1)(p-a_0)}{p^m}$ so from Chinese Remainder Theorem we can deduce that the ratio of $a$ that satisfies $\gcd(n,{a\choose k})=1$ to the all possible values of $a$ (there is $(nk)!$ of them) is equal to the following: $$\prod_{p|n} \frac{(p-a_{m-1})...(p-a_1)(p-a_0)}{p^m}$$So we need to find such $k$ that makes this ratio $\frac{1}{6}$. So clearly if $p_t$ is the greatest prime divisor of $n$ then $p_t$ must divide the denominator of the ratio that we found so we can clearly see that $p_t\leq 3$ and if $p_t=2$ then there is no $3$ divisor in the denominator therefore $p_t=3$. Then we have $n=2^a3^b$ and for the ratio we multiply some $\frac{1}{2}$ some $\frac{1}{3}$ and some $\frac{2}{3}$ and we got $\frac{1}{6}$. So clearly we either have $\frac{1}{2}\frac{1}{3}=\frac{1}{6}$ or $\frac{1}{2}\frac{1}{2}\frac{2}{3}=\frac{1}{6}$. So in first case $k=2^u = 2\cdot 3^v$ therefore $k=2$ and otherwise $k=2^u+2^v=3^w$ therefore $k=3$ or $k=9$ this part is easy just analyze cases. So we are basically done here we have $k=2$ or $k=3$ or $k=9$ and $n=2^a3^b$ for positive integers $a,b$.
27.05.2021 09:41
What about $k=3$ ?
27.05.2021 15:32
Ah yeah and that too I missed it in the last part
24.06.2021 03:37
I don't think k=2 is an answer.Maybe you can check it.
05.07.2021 13:24
omeravci372742 wrote: Let $p|n$ be a prime divisor of $n$. Then let us write $k$ in the base of $p$. Let $k=(a_{m-1}a_{m-2}...a_1a_0)_p$ where $m\leq k$. Then we want $p \nmid {a\choose k}$. Let $(nk)!=p^m A$ clearly this is true since $p^m|p^k|(nk)!$ Then let $a=p^m B +(c_{m-1}c_{m-2}...c_1c_0)_p$ therefore we have $0\leq B<A$ and for all $j=0,1,..,m$ we have $c_j \geq a_j$ from Lucas Theorem. Which means that in $(mod \; p^m)$ the number $a$ can take exactly $(p-a_{m-1})(p-a_{m-2})...(p-a_1)(p-a_0)$ values. So the ratio of the numbers $a$ with $p \nmid {a\choose k}$ is equal to $\frac{(p-a_{m-1})...(p-a_1)(p-a_0)}{p^m}$ so from Chinese Remainder Theorem we can deduce that the ratio of $a$ that satisfies $\gcd(n,{a\choose k})=1$ to the all possible values of $a$ (there is $(nk)!$ of them) is equal to the following: $$\prod_{p|n} \frac{(p-a_{m-1})...(p-a_1)(p-a_0)}{p^m}$$So we need to find such $k$ that makes this ratio $\frac{1}{6}$. So clearly if $p_t$ is the greatest prime divisor of $n$ then $p_t$ must divide the denominator of the ratio that we found so we can clearly see that $p_t\leq 3$ and if $p_t=2$ then there is no $3$ divisor in the denominator therefore $p_t=3$. Then we have $n=2^a3^b$ and for the ratio we multiply some $\frac{1}{2}$ some $\frac{1}{3}$ and some $\frac{2}{3}$ and we got $\frac{1}{6}$. So clearly we either have $\frac{1}{2}\frac{1}{3}=\frac{1}{6}$ or $\frac{1}{2}\frac{1}{2}\frac{2}{3}=\frac{1}{6}$. So in first case $k=2^u = 2\cdot 3^v$ therefore $k=2$ and otherwise $k=2^u+2^v=3^w$ therefore $k=3$ or $k=9$ this part is easy just analyze cases. So we are basically done here we have $k=2$ or $k=3$ or $k=9$ and $n=2^a3^b$ for positive integers $a,b$. The first, we let $m$ such that $p^m\parallel (nk)!$, then $k=\overline{a_{m-1}\dots a_0}_p$ (accept $a_i=0$). Since we can use CRT.