Skip to main content


Showing posts from January, 2022

Number Theory Revise 3

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^{n-1}\pmod {p^2

Number Theory Revise 2

Continuing from the previous post from  here . Another memory lane of theorem I want to prove/try! Book Reffered: David Burton, Elementary Number Theory Problem 1: $$p_n<2^{2^{n-1}}$$ Proof: Note that $$p_{n+1}\le p_1p_2\dots p_n+1\le 2\cdot \dots 2^{2^{n-1}}=2^{2^{n-1}}$$ Problem 2: If the $n>2$ terms of the arithmetic progression $$p,p+d, p+2d,\dots,p+(n-1)d$$ are all primes then the common difference $d$ is divisible by every prime $q<n.$ Proof: If not then there exists a $q$ such that $(d,q)=1, q<n.$ But then we can get a $r$ such that $p\equiv -rd\mod q.$ Problem 3: Let $p_n$ denote the $n$ th prime. For $n>3$ show that $$p_n<p_1+p_2+\dots p_{n-1}.$$ Proof: Use induction and Bertrand's postulate. We get that $$p_{n+1}<2p_n<p_1+p_2+\dots p_{n-1}+p_n.$$ I should try to prove FLT and Wilson on my own too! But lemme state them in problems format. Anyways.. Problem4: If $n=a^2+b^2=c^2+d^2$ then $$n=\frac{(ac+bd)(ac-bd)}{(a+d)(a-d)}$$ Proof:  Note that

Number Theory Revise part 1

I thought to revise David Burton and try out some problems which I didn't do. It's been almost 2 years since I touched that book so let's see! Also, this set of problems/notes is quite weird since it's actually a memory lane. You will get to know on your own! I started with proving a problem, remembered another problem and then another and so on! It was quite fun cause all these questions were the ones I really wanted to solve! And this is part1 or else the post would be too long. Problem1: Prove that for $n\ge 1$  $$\binom{n}{r}<\binom{n}{r+1}$$ iff $0\le r\le \frac{n-1}{2}$ Proof: We show that $\binom{n}{r}<\binom{n}{r+1}$ for $0\le r\le \frac{n-1}{2}$ and use the fact that $$\binom{n}{n-r}=\binom{n}{r}$$ Note that $\binom{n}{r}= \frac{n!}{r!(n-r)!}, \binom{n}{r+1}=\frac{n!}{(r+1)!(n-r-1)!}$  Comparing, it's enough to show that $$\frac{1}{n-r}<\frac{1}{r+1}\text{ or show } n-r>r+1$$ which is true as $0\le r\le \frac{n-1}{2}$ Problem2: Show that the exp

Birthday Functional Equations problems

Heyoo!!! Birthday FEs!!!!!! $11$ FEs!! Also I would be posting solutions to RG's FE handout, I am done with 10 prs :P!! Problem: Find all functions $f :\Bbb R \rightarrow \Bbb R$ such that $$2f (x) - 5f (y) = 8, \forall x, y \in \Bbb R$$ Solution: $$2f(x)-5f(y)=8$$ $$\implies 2f(x)-5f(x)=8$$ $$\implies f(x)=\frac{-8}{3}, \text{ a constant function }$$ We did this in Rohan Bhaiya's FE class..Oh btw the EGMO camp is sooo niceee! I am loving it!! It's such a big deal to be able to train and attend the camp with EGMO team members! Problem: Find all functions $f :\Bbb R \rightarrow \Bbb R$ such that $$f (x) + xf (1 -x) = x, \forall x\in \Bbb R.$$ Solution: $$f(x)+xf(1-x)=x$$ $$f(1-x)+(1-x)f(x)=1-x$$ This is actually in the linear equations in two variable form! $$x+ay=a$$ $$y+bx=b$$ Anyways,  $$f(x)+xf(1-x)=x$$ $$xf(1-x)+f(x)(1-x)x=(1-x)x$$ $$ \implies f(x)(x-x^2)-f(x)=-x^2\implies f(x)=\frac{-x^2}{x-x^2-1}=\frac{x^2}{x^2-x+1}$$ But verifying, this doesn't work. Problem:

Graph Theory: Independent sets and My blog feactured in feedSpost!!!

Continuing from the previous post ( which is  here  ). This is a bit short post. I think this short post is not at all helpful in olys but then let's do it cause I find them interesting :P. Here are my notes.. Book referred: Daniel A Marcus Graph theory Chapter I: Independence Sets: Independent vertex set:  An independent vertex set in a graph is a set of vertices that does not include any adjacent vertices. Independent edge set:  An independent edge set in a graph is a set of edges that does not include any edges that share an endpoint. Maximal Independent sets: Largest set possible. $\alpha =$ the number of vertices in a maximal independent set $\alpha ' =$ the number of edges in a maximal independent edge set Theorem1: In a graph with $n$ vertices and $e$ edges, a) $\alpha'$ is less than $n/2$ b) if $d_1,d_2,\dots $ be the degress in a maximal independent vertex set, then the sum $d_1+d_2+\dots $ is less than $e.$ Proof: Note that every edge will have distinct vertex e

INMO problems + Summary of 2021

Welcome back! I tried the previous year INMO problems. And yes, I did a lot of them, here are a few! Here are the problems! ( they are kept in random order) [2008 P2]:  Find all triples $ \left(p,x,y\right)$ such that $ p^x=y^4+4$, where $ p$ is a prime and $ x$ and $ y$ are natural numbers. [some INMO]: Find all $m,n\in\mathbb N$ and primes $p\geq 5$ satisfying $$m(4m^2+m+12)=3(p^n-1).$$ [2015 P3]  Find all real functions $f: \mathbb{R} \to \mathbb{R}$ such that $f(x^2+yf(x))=xf(x+y)$. [2005 P6]:  Find all functions $f : \mathbb{R} \longrightarrow \mathbb{R}$ such that\[ f(x^2 + yf(z)) = xf(x) + zf(y) , \]for all $x, y, z \in \mathbb{R}$. [2012 P6] Let $f : \mathbb{Z} \to \mathbb{Z}$ be a function satisfying $f(0) \ne 0$, $f(1) = 0$ and $(i) f(xy) + f(x)f(y) = f(x) + f(y)$ $(ii)\left(f(x-y) - f(0)\right ) f(x)f(y) = 0 $ for all $x,y \in \mathbb{Z}$, simultaneously. $(a)$ Find the set of all possible values of the function $f$. $(b)$ If $f(10) \ne 0$ and $f(2) = 0$, find the set of all

Weird Theorems

Welcome back to this blog.  Oki it's a new day and I decided to prove some weird theorems/lemmas with weird names. So, you can try proving it too!  In my list we have,  Sawayama theorem Butterfly Theorem Iran lemma Simon's Trick Chicken McNugget Theorem Pick's theorem Fermat's Christmas Theorem Sawayama Thebault Theorem: Let $ABC$ be a triangle with circumcircle $\Gamma$ and incenter I. Let $D \in BC.$ Let $\Omega_1$ be the circle tangent to the line segments $DA$ and $DB$ and to the circle $\Gamma$, and let $\Omega_2$ be the circle tangent to the line segments $DA$ and $DC$ and to the circle $\Gamma$. If $O_1$ and $O_2$ are the centres of  $\Omega_1$ and $\Omega_2$, respectively, prove that $O_1 -I -O_2$ are collinear. Walkthrough:  Note $I\in EF,~~I\in GH$ Prove $O_1DO_2=90$ $DO_1|| GH$ and $DO_2 || EF.$ Since we want to prove that $I \in O_1 O_2 $, let $EF \cap O_1 O_2 = I '$ and let $GH \cap O_1 O_2 = I".$  $$\frac {O_1I'}{I'O_2}=\frac{O_1X}{DX}, \