National Math Camp 2020 Exam 2 Problem 3

Discussion on Bangladesh National Math Camp
User avatar
FuadAlAlam
Posts:30
Joined:Wed Sep 16, 2020 11:10 am
Location:Dhaka, Bangladesh
Contact:
National Math Camp 2020 Exam 2 Problem 3

Unread post by FuadAlAlam » Mon Dec 07, 2020 1:35 pm

Let $n$ be a positive integer. Prove that there exist integers $b_1, b_2, ... , b_n$ such that for any integer $m$, the number $$(\ldots (((m^2 + b_1)^2 +b_2)^2 + \ldots)^2 + b_{n-1})^2 + b_n$$ is divisible by $2n-1$.

User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: National Math Camp 2020 Exam 2 Problem 3

Unread post by Anindya Biswas » Sat Dec 26, 2020 10:53 pm

Notice that we can have at most $n$ different quadratic residue modulo $2n-1$. Let $S=\{[a_1],[a_2],\dots,[a_k]\}$ be our complete set of quadratic residue classes modulo $2n-1$. Now we have a algorithm to find the values of $b_i$s.
Now, $m^2\in S$. Let's choose our $b_1$ such that $b_1\equiv-(a_1+a_2)\cdot n\pmod{2n-1}$
Why? See that if we choose $b_1$ in this way, then $(a_1+b)\equiv-(a_2+b)\pmod{2n-1}$ or, $(a_1+b)^2\equiv(a_2+b)^2\pmod{2n-1}$ [Also remark that $n$ is the inverse of $2$ modulo $2n-1$].
By following this method, now the number of possible residue classes the number $(m^2+b_1)^2$ can be in, has decreased by at least one. Now take the set of all possible residue classes of $(m^2+b_1)^2$, let's say $S_1=\{[c_1],[c_2],\dots,[c_l]\}$ and choose $b_2\equiv-(c_1+c_2)\cdot n\pmod{2n-1}$.
By following the same algorithm for $b_3,b_4,\dots,b_{n-1}$, we can always decrease the possible set of residue classes by at least $1$. After choosing $b_1,b_2,\dots,b_{n-1}$, we are left with at most $1$ possible residue class $[r]$ and choosing $b_n\equiv-r\pmod{2n-1}$ will do our job.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

User avatar
FuadAlAlam
Posts:30
Joined:Wed Sep 16, 2020 11:10 am
Location:Dhaka, Bangladesh
Contact:

Re: National Math Camp 2020 Exam 2 Problem 3

Unread post by FuadAlAlam » Mon Mar 01, 2021 12:35 pm

We have the following claim.
Claim : For some subset of the quadratic residue set $a^2$ (mod $2n-1$), we can pick $b_i$ such that the number of all possible values of $(a^2 + b_i)^2$ (mod $2n-1$) has decreased by at least $1$.
Proof : Let $m_1, m_2$ be such that $m_1^2$ and $m_2^2$ are not same modulo $2n - 1$ i.e. $ m_1^2 \not \equiv m_2^2$ (mod $2n - 1$). Pick $$b_i \equiv -2^{-1}(m_1^2 + m_2^2)$$ (mod $2n - 1$).
It is easy to check that $(m_1^2 + b_i)^2 \equiv (m_2^2 + b_i)^2$ (mod $2n - 1$), thus prove our claim.

It is easy to verify that there are at most $n$ quadratic residues modulo $2n - 1$. We can pick appropriate $b_i$'s to reach $$(\ldots(((m^2 + b_1)^2 + b_2)^2 + \ldots)^2 + b_{n-1})^2 + b_n \equiv 0$$ (mod $2n - 1$)
for all $m$ and we are done.

Post Reply