Trust Issues

Hi, I am Debayu and this is my second blogpost !! We start off with the following problem. 

Problem: Find the sum of all $b$ such that $$2n+1\mid (\genfrac{}{}{0ex}{}{2n}{b})-1$$ for all $n$ such that $2n\ge b$.

At first glance, this looks somewhat innocent and its probably some problem from some random computational contest, some may this can be what the IOQM 10 markers will look like this year. hmmm so what do we do here? Let's check what happens when $b$ is $2$. So we have that for all $n$, $$2n+1\mid (\genfrac{}{}{0ex}{}{2n}{2})$$ $$⟺2n+1\mid n(2n-1)-1=2n^2-n-1$$ $$⟺2n+1\mid |2n^2-n-1-n(2n+1)|=|-2n-1|$$ which is true so yay $2$ works. Now we might want to check $b=3$, this means $$2n+1\mid (\genfrac{}{}{0ex}{}{2n}{3})$$ $$⟺2n+1\mid \frac{n(2n-1)(2n-2)}{3}$$ $$⟺6n+3\mid 4n^3-6n^2+2n$$ from here, it is easy to see that if $n$ is even, the divisibility wont hold so $3$ doesn't work. Similarly one can check that $4$ doesn't work either and one might guess that the only possible $b$ is $2$ which is actually correct but proving this seems really hard. One idea probably is to try to prove that $b$ should always be even or $b$ is always a prime but it seems pretty counterintuitive to do that since $4$ and $3$ don't work and both the claims seem very weak, but there doesn't seem to be too much to do either. Anyways let's see what we can do, lets begin with expanding the thing we have,

$$(\genfrac{}{}{0ex}{}{2n}{b})-1=\frac{(2n)!}{b!(2n-b)!}-1=\frac{(2n)(2n-1)\cdots (2n-b+1)}{b!}-1$$

Hmm, not too shaggy, lets see what happens when we take this modulo $2n+1$,

$$\frac{(2n)(2n-1)\cdots (2n-b+1)}{b!}-1\equiv \frac{(-1)(-2)\cdots (-b)}{b!}-1\equiv (-1{)}^b-1(\mathrm{mod}2n+1)$$

Woah so indeed $b$ must be even, so we finally have some progress but what do we do now. There seems to be nothing to do since $2$ gives us very less information and expanding binomial coefficients is not the best idea as they can turn ugly really quick. What do you do when nothing else makes sense? Magic? Yes, let's generalize the problem by replacing $a$ with $2$ since $2$ is the most trashy number ever. Here we have our new problem,

Magically Generalized Problem: Find all $b$ such that $$an+1\mid (\genfrac{}{}{0ex}{}{an}{b})-1$$ for all $n$ such that $an\ge b$.

Wait wait, this doesn't trivialize the problem in any way so don't leave your seats, this just gives you more space to work with. Also notice that we don't have the sum thing in the problem now as it might be that there are infinitely many such $b$. Now recall Dirichlet's Theorem,

Dirichlet's Theorem: There are infinitely many primes dividing an AP $(an+b{)}_{n\ge 0}$ with $gcd(a,b)=1$.

Obviously, we have $gcd(a,1)=1$ so we can probably pick big primes dividing $an+1$ to mess all the numbers that don't work. From here the key idea is to notice that if we have primes smaller than $b$ then we can probably mess with the ${\nu }_p$, to avoid that we might want to prove that all primes $p\le b$ divide $a$.

Now suppose the above thing is not true, then pick $p^{huge}|an+1$ which is possible since we are assuming $gcd(a,p)=1$. This means,

$${\nu }_p((\genfrac{}{}{0ex}{}{an}{b}))={\nu }_p((an)(an-1)\cdots (an-b+1))-{\nu }_p(b!)>0$$ but then $an+1$ wont divide $(\genfrac{}{}{0ex}{}{an}{b})-1$ so indeed what we wanted to prove is correct. IIRC these two conditions actually fully characterize all such numbers which is really cool. 

Now returning to the original problem, we had $a=2$, so the only possible $b$ is $2$ since all primes $\le b$ must divide $a$ so we are done!!

You probably know by now how bad you got scammed, this was nothing but 2019 N5, here's the problem statement of it if you are still having trust issues.

ISL 2019 N5: Let  be a positive integer. We say that a positive integer $b$ is -good if  is divisible by  for all positive integers  with . Suppose  is a positive integer such that  is -good, but  is not -good. Prove that  is prime.

Here, notice that for $b+2$ to be bad, you need either $b+1$ or $b+1$ to be prime but $b$ is even so $b+1$ has to be prime.

See dont be mad at me, I know I probably just gave you trust issues for the rest your life but firstly there exist things that will make you have even more of them like,

and secondly, you have more scam ammunition with you now to scam even more people.

Credits: Ameya

"Scams are like rickrolls, the first thing to do after getting scammed is to scam them back" - Me?

Now, I shall introduce you to a very cool theorem!!

Lucas' Theorem: Given natural numbers $m$ and $n$ expressed in base $p$,

$$m=m_k{p}^k+m_{k-1}{p}^{k-1}+\cdots +m_{1}p+m_0,\text{and}$$

$$n=n_k{p}^k+n_{k-1}{p}^{k-1}+\cdots +n_{1}p+n_0,$$

where $p$ is a prime, we have 

$$(\genfrac{}{}{0ex}{}{m}{n})\equiv (\genfrac{}{}{0ex}{}{m_k}{n_k})(\genfrac{}{}{0ex}{}{m_{k-1}}{n_{k-1}})\cdots (\genfrac{}{}{0ex}{}{m_0}{n_0})(\mathrm{mod}p)$$

It makes some sense why we might want to use it, I will just present the proof of our main claim which uses lucas', I first came to know about this after I saw Aryan's proof to it. The key idea is that if one of the binomials in the RHS is $0$ then the whole thing just breaks down and that happens which its like $(\genfrac{}{}{0ex}{}{0}{\text{non-zero}})$.

Proof: Assume contradiction. Consider the base $p$ representation of $b=m_i{p}^i+m_{i-1}{p}^{i-1}+\cdots +m_{1}p+m_0$. Since $p\ge b$, it must have a non-zero $m_j$ other than $m_0$. Now we pick $n$ such that the base $p$ representation of $an$ has the coefficient associated with $p^k$ to be $0$, this is possible since $an+1$ can span all residues $(\mathrm{mod}{p}^{k+1})$ from our assumption. By lucas', $(\genfrac{}{}{0ex}{}{an}{b})\equiv 0(\mathrm{mod}p)$ which is a contradiction. $◼$

If you want to read more about lucas', you can refer to this article. That was all for today!! I hope you have major trust issues now, I mean I hope you enjoyed!! :P