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.