Sunaina thinks absurd

 Theory  We know what Fermat's little theorem states. If $p$ is a prime number, then for any integer $a$, the number $a^p − a$ is an integer multiple of $p$. In the notation of modular arithmetic, this is expressed as \[a^{p}\equiv a{\pmod {p}}.\] So, essentially, for every $(a,m)=1$, ${a}^{\phi (m)}\equiv 1 \pmod {m}$. But $\phi (m)$ isn't necessarily the smallest exponent. For example, we know $4^{12}\equiv 1\mod 13$ but so is $4^6$. So, we care about the "smallest" exponent $d$ such that $a^d\equiv 1\mod m$ given $(a,m)=1$.  Orders Given a prime $p$, the order of an integer $a$ modulo $p$, $p\nmid a$, is the smallest positive integer $d$, such that $a^d \equiv 1 \pmod p$. This is denoted $\text{ord}_p(a) = d$. If $p$ is a primes and $p\nmid a$, let $d$ be order of $a$ mod $p$. Then $a^n\equiv 1\pmod p\implies d|n$. Let $n=pd+r, r\ll d$. Which implies $a^r\equiv 1\pmod p.$ But $d$ is the smallest natural number. So $r=0$. So $d|n$. Show that $n$ divid...

Yeah, I did some problems and here are a few of them! I hope you guys try them! Putnam, 2018 B3 Find all positive integers $n < 10^{100}$ for which simultaneously $n$ divides $2^n$, $n-1$ divides $2^n - 1$, and $n-2$ divides $2^n - 2$. Proof We have $$n|2^n\implies n=2^a\implies 2^a-1|2^n-1\implies a|n\implies a=2^b$$ $$\implies 2^{2^b}-2|2^{2^a}-2\implies 2^b-1|2^a-1\implies b|a\implies b=2^c.$$ Then simply bounding. USAMO 1987 Determine all solutions in non-zero integers $a$ and $b$ of the equation $$(a^2+b)(a+b^2) = (a-b)^3.$$ Proof We get $$ 2b^2+(a^2-3a)b+(a+3a^2)=0\implies b = \frac{3a-a^2\pm\sqrt{a^4-6a^3-15a^2-8a}}{4}$$ $$\implies a^4-6a^3-15a^2-8a=a(a-8)(a+1)^2\text{ a perfect square}$$ $$\implies a(a-8)=k^2\implies a^2-8a-k^2=0\implies \implies a=\frac{8\pm\sqrt{64+4k^2}}{2}=4\pm\sqrt{16+k^2}. $$ $$ 16+k^2=m^2\implies (m-k)(m+k)=16.$$ Now just bash. USAMO 1988 Suppose that the set $\{1,2,\cdots, 1998\}$ has been partitioned into disjoint pairs $\{a_i,b_i\}$ ($1...

Such a cute problem, although again, swapping the sum is hard.. I should practice more in that area :( Solved with Sidharth and Malay! Problem[2021 China TST 3/2/4] Prove that $$ \sum_{m=1}^n5^{\omega (m)} \le \sum_{k=1}^n\lfloor \frac{n}{k} \rfloor \tau (k)^2  \le \sum_{m=1}^n5^{\Omega (m)} .$$ Proof: Note that the middle term can be manipulated and written as $$\sum_{k=1}^n\lfloor \frac{n}{k} \rfloor \tau (k)^2= \sum_{k=1}^{n}\sum_{dk\le n}1 \tau(k)^2=\sum_{m=1}^n\sum_{k|m}\tau(k)^2$$ Since $\tau (k)$ is multiplicative, we get that $\tau(k)^2$ is multiplicative. Hence $F(m)= \sum_{k|a}\tau(k)^2$ is multiplicative too. ( As it's $1* \tau(k)^2$) Now, we begin our claim which proves the problem. Claim: $5^{\omega(a)}\le \sum_{k|a}\tau(k)^2\le 5^{\Omega(a)}$ Proof: Note that these symbols are multiplicative, we just have to check for primes. For primes $p^b$, $$5^{\omega(p^b)}\le \sum_{k|p^b}\tau(k)^2\le 5^{\Omega(p^b)}$$ Or showing $$5 \le \frac{(b+1)(b+2)(2b+3)}{6} \le 5^b$$ which...

Yeyy finally! I got time! I am so happy that I am finally going to read the analytic theory! However, I have added some CS stuff. Not sure if they are accurate. I have taken up CS in school so hopefully, it's correct!  Big $O$ notation:  We say $f(x)=O(g(x))$ if there exists $c$ such that $|f(x)|< c(g(x)$ for all $x\ge x_0$. Arithmetic of Big $O$ notation: $O(f(x))+O(g(x))= O(f(x)+g(x))$. Moreover, if $f(x)=O(g(x))\implies O(f(x)+g(x))=O(g(x)) $ $O(f(x))\times O(g(x))= O(f(x)\cdot g(x))$ $O(f(x)) - O(g(x))= O(f(x) +g(x))$ ( Yes, it is "+") $O(\int f(x) dx)=\int O(f(x) dx$ I want to dive into the CS part; it looks pretty nice and attractive :p. Introduction In CS, it is important to measure the efficiency of the algorithm before applying it on a big size of data. The "performance" depends on internal and external factors. Internal factors ( which we care more) specify the algorithm's efficiency in terms of: Time required to run and Space required to run....

 OMG Prime number theorem!!! I actually loved it! So today I solved a quite fancy NT problem with other people's help though! Problem : Prove that there exists an interval of the $[n^2,(n+1)^2]$ which contains at least $1000$ primes. Proof 1 : By PNT, if $n$ is large enough $$\pi(n) ~ \frac{n}{\log(n)}$$ So $$f(n)=\pi( {n+1}^2)-\pi( n^2) = \frac{(n+1)^2}{\log({n+1}^2)}- \frac{n^2}{\log(n^2)}$$ $$= \frac{(n+1)^2}{2\log({n+1})}- \frac{n^2}{2\log(n)}$$ Then $$f'(n)= \frac{(2n+2)\log(n+1)-(n+1)}{2[\log(n+1)]^2}-\frac{2n\log(n)-n}{2[\log(n)]^2}$$ $$=\frac{n+1}{\log(n+1)}+\frac{n}{2[\log(n)]^2}- (\frac{n}{\log(n)}+\frac{n+1}{2[\log(n+1)]^2})$$ Take  $$h(x)= \frac{(x)}{\log(x)}, g(x)=\frac{x}{2\log^2(x)}$$ we have basically $$(h(n+1)-h(n))>>>( g(n+1)-g(n)) $$ since $h$ grows faster than $g$ we have  $$h(n+1)-h(n) > (g(n+1)-g(n)$$ for large enough $n$. Infact $f'(n)$ is strictly increasing. Now, by MVT, note that there exist $t_1$ such that $$f(2)-f(1)=f'(t_1), t...

 Well, I am finally free! It's more like I was busy with classes and covering up the NT4 course, dang it is hard! Finally got hand of convolutions etc! ISL 2002 N3 : Let $p_1,p_2,\ldots,p_n$ be distinct primes greater than $3$. Show that $2^{p_1p_2\cdots p_n}+1$ has at least $4^n$ divisors. Proof : Now consider $d\mid p_1p_2\ldots p_n$ and $d'\mid p_1p_2\ldots p_n$. Note that there is a prime $p|2^d+1|2^{p_1p_2\cdots p_n}+1$ and $p\nmid 2^{d'}+1$ by zsig for any $d, d'$. Hence there are any $2^n$ distinct such $p$ ( as there are $2^n$ prime factors of $p_1p_2\cdots p_n$). Since there are atleast $2^n$ distinct primes dividing $p_1p_2\cdots p_n \implies $ there are at least $2^{2^n}$ primes factors which is $>>4^n$. The exceptional case doesn't matter here.  [ISL 2000 N4] :Find all triplets of positive integers $ (a,m,n)$ such that $ a^m + 1 \mid (a + 1)^n$ Proof : Except for the exception of the Zsigmondy theorem, there exists $p$ such that $p|a^m+1$ and $p\nm...

Just did two problems, and both were hard! So I think one can excuse me for not solving more, but it's true. I did give less time. I am trying to reduce the amount of time I "waste". I did spend a good amount of time learning the theory, so yey! Excited for today's link episode!!  [Romania TST 7 2009, Problem 3] Show that there are infinitely many pairs of prime numbers $(p,q)$ such that $p\mid 2^{q-1}-1$ and $q\mid 2^{p-1}-1$. Proof: We begin with the lemma,  Lemma: Let $p\mid 2^{2^n}+1$ then $p\equiv 1\pmod  2^{n+2}$ Proof: Note that ord$_p(2)=2^{n+1}$ $$\implies 2^{n+1}|p\implies p\equiv 1\pmod 2^{n+1}\implies p\equiv 1\pmod 8$$ $$\implies 2^{\frac{p-1}{2}}\equiv 1\pmod p\implies 2^{n+1}\mid \frac{p-1}{2}$$ So consider any prime $p$ dividing $2^{2^{n}}+1$ and $q$ to be prime factor of $2^{2^{n+1}}+1$. Then we get that $p\equiv 1 \pmod 2^{n+2}$ and we get that $q\equiv 1\pmod 2^{n+3}$. Note that $$p\mid 2^{n+1}-1\mid 2^{n+3}-1 \mid 2^{q-1}-1$$ Moreover, $$q\mid 2...

So it's been 1 month since the INMO results were out! So here's my past 1 month's journey into problem-solving.  There hasn't been much in my life, although the Sharygin correspondence round results came out! And I qualified for the final round. I just made the cutoff though. I got 85 marks and the (unofficial) cutoff was 84 marks. I am one of the seven students selected for the final round and the only kid from India in my grade! They, however, are not inviting Indian students in the final round and have asked us to conduct the final round in India if an organization agrees. Monthly reflection: Till May 16, I tried the Awesome Math Application ( which I got accepted into woohoo! And I am taking courses in the second and third season hehe) Then I was completing 108 algebra problems along with MBL problems till June 1 June 1- June 10: Since I was feeling very guilty for not doing enough problems from the Sophie psets, I did a few Sophie psets problems. BTW Thankyou so mu...

Continuing from  here . Book Referred: David Burton, Elementary Number Theory Also, thanks to Pranjal Bhaiya and Ritam bhaiya for taking lectures in NT in EGMO Camp and Sophie! We state and prove LTE first. $$v_p(x^n-y^n)=v_p(x-y)+v_p(n), n|x-y, n\not\mid x.$$ Walkthough: We use induction on $v_p(n).$ [ We show for $v_p(n)=0, v_p(n)=1$ and then use induction. 1. We show it for $v_p(n)=0.$ That is show $v_p(x^n-y^n)=v_p(x-y)$ To show this is true, $$v_p(\frac{x^n-y^n}{x-y})=v_p(x^{n-1}+yx^{n-2}+y^2x^{n-3}+\dots+y^{n-1})=0.$$ As $x\equiv y\pmod p.$ So,  $$x^{n-1}+yx^{n-2}+y^2x^{n-3}+\dots+y^{n-1}\equiv nx^{n-1}\pmod p. $$ And $p\not\mid nx^{n-1}$ 2. We show it for $v_p(n)=1.$ That is show $v_p(x^n-y^n)=v_p(x-y)+1$ To show this is true, $$v_p(\frac{x^n-y^n}{x-y})=v_p(x^{n-1}+yx^{n-2}+y^2x^{n-3}+\dots+y^{n-1})=1.$$ As $x\equiv y\pmod p\implies x=y+pk$ So,  $$x^{n-1}+yx^{n-2}+y^2x^{n-3}+\dots+y^{n-1}\pmod {p^2} $$ $$\equiv (pk+y)^{n-1}+(pk+y)^{n-2}y+(pk+y)^{n-3}y^2+\dots+y^{...