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




Comments

Post a Comment

Popular posts from this blog

Constructions in Number Theory

Hi, I am Emon, a ninth grader, an olympiad aspirant, hailing from Kolkata. I love to do olympiad maths and do some competitive programming in my leisure hours, though I take it seriously. I had written INOI this year. Today, I would be giving you a few ideas on how to Construct in Number Theory . Well, so we shall start from the basics and shall try to dig deeper into it with the help of some important and well-known theorems and perhaps, some fancy ones as well. Okay, so without further delay, let's start off... What do we mean by "Constructions"? If noticed, you can see that you often face with some problems in olympiad saying, "... Prove that there exists infinitely many numbers satisfying the given conditions" or "... Prove that there exists a number satisfying the above conditions." These are usually the construction-problems .  For example, let's consider a trivial example : Problem. Prove that there exist infinitely many integers $a$ such th

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

Q&A with experts about bashing

Heyy everyone! From the title, you can see that we are going to talk about  BASH.  Yesss, we are going to discuss whether you really need to learn bash or not?  Let me first introduce myself, I am Pranav Choudhary, a 10th grader from Haryana(India). I like to do geo and combo the most :PP. Oki so let's begin! For those of you who don't know what bashing is, lemme give you a brief introduction first. Bashing is basically a technique used to solve Geometry Problems. In general, when you try a geo problem you might think of angles, similarities, and some other techniques (e.g. Inversion, spiral similarity etc). All of which are called synthetic geometry. But sometimes people use various other techniques called "bash" to solve the same problems.  Now there are different kinds of bashing techniques, e.g. - Coordinate bash, Trig Bash, Complex bash, Barycentric Coordinates. Let me give you a brief introduction to each of them.  Coordinate Bash : You set one point as the orig