BdMO National Secondary 2020 P12

Discussion on Bangladesh Mathematical Olympiad (BdMO) National
User avatar
Joined:Thu Aug 22, 2013 9:11 pm
Location:Dhaka, Bangladesh.
BdMO National Secondary 2020 P12

Unread post by Mursalin » Thu Dec 03, 2020 6:35 pm

জয়দীপ একটা ধনাত্মক পূর্ণসংখ্যা $n$-কে চমকপ্রদ বলে যদি মৌলিক সংখ্যার যেকোনো অসীম সেট থেকেই $n$টা মৌলিক সংখ্যা $p_1, p_2, \cdots , p_n$ পাওয়া যায় যেন $p_1 p_2 ... p_n - 1$ সংখ্যাটা $2020$ দ্বারা বিভাজ্য হয়। $2020$-এর চেয়ে ছোট সব চমকপ্রদ সংখ্যার যোগফল বের করো।


Joydip calls a positive integer $n$ amazing if given any infinite set of primes, he can find $n$ primes $p_1, p_2, \cdots, p_n$ from it such that $p_1p_2 \cdots p_n - 1$ is divisible by $2020$. Find the sum of all amazing numbers less than $2020$.
This section is intentionally left blank.

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

Re: BdMO National Secondary 2020 P12

Unread post by Anindya Biswas » Wed Dec 16, 2020 10:21 pm

There are $2020$ residue classes modulo $2020$. So, for an infinite set of prime number $S$, there must exists a residue class $[r]$ such that there are infinitely many prime number $p\in S$ such that $p\equiv r\pmod{2020}$. In that case, $gcd(r,2020)=1$.
Claim-1: If $gcd(x,2020)=1$ then $x^{100}\equiv1\pmod{2020}$.
Notice that $2020=2^2\times5\times101$
Now, $x^{100}\equiv1\pmod4$
and $x^{100}\equiv1\pmod5$
and $x^{100}\equiv1\pmod{101}$ [All of this are implied by Euler's theorem]
So, by Chinese remainder theorem, $x^{100}\equiv1\pmod{2020}$ (Demonstrated)

So, we will choose $p_1, p_2, \dots, p_n$ such that $p_i\equiv r\pmod{2020}$
$\therefore p_1p_2\cdots p_n\equiv r^n\pmod{2020}$
$\rightarrow r^n\equiv1\pmod{2020}$
$\rightarrow 100|n$
So, amazing numbers are number that are divisable by $100$.
So, our answer is, $100+200+300+\cdots+2000=21000$
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

Post Reply