Skip to main content

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 \binom{2n}{b} -1$$ for all $n$ such that $2n \geq 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 \binom{2n}{2}$$ $$\iff 2n+1 \mid n(2n-1)-1=2n^2-n-1$$ $$ \iff 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 \binom{2n}{3}$$ $$\iff  2n +1 \mid \frac{n(2n-1)(2n-2)}{3}$$ $$\iff 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,

$$\binom{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 \pmod{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 \binom{an}{b} -1$$ for all $n$ such that $an \geq 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 \geq 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 \leq 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 (\binom{an}{b}) = \nu_p((an)(an-1)\cdots (an-b+1)) -\nu_p(b!) > 0$$ but then $an+1$ wont divide $\binom{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 $\leq 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 $a$ be a positive integer. We say that a positive integer $b$ is $a$-good if $\tbinom{an}{b}-1$ is divisible by $an+1$ for all positive integers $n$ with $an \geq b$. Suppose $b$ is a positive integer such that $b$ is $a$-good, but $b+2$ is not $a$-good. Prove that $b+1$ 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_kp^k+m_{k-1}p^{k-1}+\cdots+m_1p+m_0, \text{and}$$

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

where $p$ is a prime, we have 

$$\binom{m}{n} \equiv \binom{m_k}{n_k}\binom{m_{k-1}}{n_{k-1}}\cdots \binom{m_0}{n_0} \pmod{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 $\binom{0}{\text{non-zero}}$.

Proof: Assume contradiction. Consider the base $p$ representation of $b = m_ip^i+m_{i-1}p^{i-1}+\cdots+m_1p+m_0$. Since $p \geq 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 $\pmod{p^{k+1}}$ from our assumption. By lucas', $\binom{an}{b} \equiv 0 \pmod{p}$ which is a contradiction. $\blacksquare$

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


Post a Comment

Popular posts from this blog

EGMO solutions, motivations and reviews ft. Atul, Pranjal and Abhay

The  European Girls' Mathematical Olympiad a.k.a EGMO 2022 just ended. Congrats to Jessica Wan from USA, Taisiia Korotchenko, and Galiia Sharafetdinova for the perfect scores! Moreover, the Indian girls brought home 4 bronze medals! By far, this is the best result the EGMO India Team has ever achieved! To celebrate the brilliant result, here's a compilation of EGMO 2022 solutions and motivations written by my and everyone's favorite IMOTCer Atul ! And along with that, we also have reviews of each problem written by everyone's favorite senior, Pranjal !  These solutions were actually found by Atul, Pranjal,  and Abhay  during the 3-hour live solve. In the live solve, they solved all the 6 problems in 3 hours 😍!!! Okie Dokie, I think we should get started with the problems! Enjoy! Problem 1:  Let $ABC$ be an acute-angled triangle in which $BC<AB$ and $BC<CA$. Let point $P$ lie on segment $AB$ and point $Q$ lie on segment $AC$ such that $P \neq B$, $Q \neq C$ and

Kőnig-Egerváry theorem

Graph theory has been my most favourite thing to learn in maths and and in this blog i hope to spread the knowledge about Kőnig's theorem. It is advised that the readers are aware about basic graph theory terminologies including bipartite graphs. Before going on to the theorem i would like to go on about matchings and vertex cover which we are going to use in the theorem  Matchings A matching $M$ of a graph $G$ is a subset of the edges of a graph in which no two edge share a common vertex (non adjacent edges). For example :- The Matching $M$ over here is edge $\{ 3 - 5 , 1-2 , \}$ or $\{ 1 - 2 , 4 - 3 \}$ etc .  Maximum Matching is a matching that contains the largest possible number of edges for instance in the above example the maximum matching is 2 edges as there cannot be a subset of non adjacent edges having greater than 2 edges (Readers are advised to try so they can convince themselves) A Perfect Matching  is a matching that matches all vertices of the graph or in other sen

Algorithms, or Mathematics?!

Hi everyone! In my last blog, I spoke about a couple of very interesting algorithmic techniques and how they can be used to solve a variety of very interesting problems. This blog however, is going to be completely different.   When we’re young we begin by learning the steps to add – we’re given the rules and we must learn to repeat them – no questions asked. Why does carry forward work the way it does? Well, no questions asked. To some extent, it is important to know how exactly to do a certain set of things while first learning maths. We may not be able to get anywhere in a subject if we’re unable to learn a few basic rules and know how to use them. However, after a certain point it is important to bring in the spirit of mathematical thinking within each student too – something missing in almost every form of school math education. Mathematical miseducation is so common, we wouldn’t even see it. We practically expect a math class to look like repetition and memorisation of disjointed