Skip to main content

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 that $3^a+1$ is divisible by $4$. 

Solution. This is a one-liner. Take $a$ as any odd number greater than or equal to $1$. Then, since $x+y\mid x^n+y^n$ if $n$ is an odd number, we have $4\mid 3^a+1$, as desired.

I hope you have got a basic idea on how to construct. 

The Chinese Remainder Theorem

Many among you might know the Chinese Remainder. Actually, it all started with a problem with specific numbers in a book called Sun-Tzu Suan-ching written by chinese mathematician Sun-Tzu.

Theorem. Let $n_1, n_2, \ldots, n_r $ be a set of pairwise coprime integers. Let $(a_1, a_2,\cdots, a_r)\in \mathbb{N}$. Then, there exists a unique $x\in \{1, 2, \cdots, n_1n_2\cdots n_r\}$ such that $$\begin{aligned} x &\equiv a_1\pmod{n_1} \\ x &\equiv a_2\pmod{n_2} \\ &\ \ \vdots \\ x &\equiv a_r\pmod {n_r}. \end{aligned}$$

$Proof.$ Let $N=\prod_{i=1}^rn_i$. For each $k=1, 2, \ldots, r$, let 

$$\begin{aligned} N_k &= \frac{N}{n_k} \\ &= n_1n_2\cdots n_{k-1}n_{k+1}\cdots n_r. \end{aligned}$$

Now, the $n_i'$s are relatively prime in pairs, so that $\gcd(N_k, n_k)=1$. Hence, by the Theory of Single Linear Congruence, the congruence $N_kx\equiv 1\pmod{n_k}$ is solvable. Let the unique solution be called $x_k$. 

Claim. $y=\sum_{i=1}^ra_iN_ix_i$ is a simultaneous solution to the given system of congruences. 

$Proof.$ We first observe that $N_i\equiv 0\pmod{n_j}\ \forall\ j\ne i$. Then, we have, $$\begin{aligned} y=\sum_{i=1}^ra_iN_ix_i &\equiv 0+0+\ldots+0+a_kN_kx_k+0+\ldots+0 \\ &\equiv a_kN_kx_k\pmod{n_k}. \end{aligned}$$

But, $x_k$ was chosen to satisfy the congruence $N_kx\equiv 1\pmod{n_k}$, implying that $a_kN_kx_k\equiv a_k\pmod{n_k}$, implying that there exists a solution to given system of congruences.

But, it still remains to show that the solution is a unique one. Suppose, for the sake of contradiction, there exists another integer $x_0$ such that $x_0\equiv y\pmod{n_k}$. Hence, $y-x_0\equiv 0\pmod{n_k}$ for each value of $k$. Now, since $\gcd(n_i, n_j)=1$, we have, $n_1\cdots n_r\mid y-x_0$, implying that $y\equiv x_0\pmod{N}$. Since $y\le N$, therefore, $x_0\ge N$ which implies that either $x_0=y$ or $x_0>N$, thus proving it's uniqueness.

Thue's Lemma

Thue’s lemma is a wonderful result in modular arithmetic, and is very useful in constructions, especially related to squares. 

Lemma. Let $n> 1$ be an integer and $a$ be an integer coprime to it. Then there exists integers $k, \ell$ with $0< |k|, |\ell|<\sqrt{n}$ such that  $$ak\equiv \ell\pmod{n}.$$

$Proof.$ Let $m=\lfloor \sqrt{n}\rfloor$. Then $m^2\le n< (m+1)^2$. Now, we consider the numbers of the form $ax-y\ \forall\ 0\le x, y \le m$. There are $(m+1)^2>n$ such numbers. Hence, by PHP, atleast two are the same. So, for some $k_1, \ell_1, k_2, \ell_2$, we have, $$\begin{aligned} ak_1 -\ell_1 &\equiv ak_2-\ell_2 \pmod{n} \\ \iff a(k_1-k_2) &\equiv \ell_1-ell_2\pmod{n}. \end{aligned}$$

Setting $k=k_1-k_2$ and $\ell=\ell_1-\ell_2$, we get,  $$ak\equiv \ell\pmod{n}\text{, as desired}.$$


Fermat's Two-Square Theorem

Albert Girard was the first to make the observation that every prime $p$ of the form $4n+1$ is the sum of two squares is sometimes called Girard's theoremFermat wrote an elaborate version of the statement (in which he also gave the number of possible expressions of the powers of p as a sum of two squares) in a letter to Marin Mersenne dated December $25$, $1640$ : for this reason this version of the theorem is sometimes called Fermat's Christmas theorem.

Theorem. Let $p$ be an odd prime. Then there exist integers $x, y$ such that $p = x^2 + y^2$ if and only if $p \equiv 1 \pmod 4$.

$Proof.$ We first recall what Fermat's Christmas Theorem stated. According to it, there exists $x$ such that $p \mid x^2+1$ if and only if $p \equiv 1 \pmod 4$.

Now, suppose we have a number $q$ coprime to $p$. Then, by Thue's Lemma, we can find $x$ and $y$ such that $0<|x|, |y|<\sqrt{p}$ with $qy\equiv x\pmod p$. Hence, we have, $p\mid x^2-q^2y^2$. Next, we choose $q$ such that $q^2\equiv -1\pmod p$. We can do this due to FCT. Then, we get, $p\mid x^2+y^2$. But, we observe that $0<x^2+y^2<p+p=2p$ and hence $x^2+y^2=p$ as their is no other multiple of $p$ in between $0$ and $2p$.

Interesting Fact. The Fermat's Two-square theorem can be proved using Thue's Lemma, and on the other hand, Thue's Lemma can be proved using Fermat's Two-square theorem.


We now only state two theorems, one of them being a fancy one.

Lagrange Interpolation

Actually, the method of ''Lagrange Interpolation" was first discovered by Edward Waring in the year $1779$, but as can be understood, did not publish it. Later on, in $1795$, it was published by Joseph-Louis Lagrange. It is also an easy consequence of a formula published in $1783$ by Leonhard Euler.

Theorem. If $x_1,x_2,\ldots , x_n$ be $n$ distinct complex numbers and $a_1,a_2,\ldots, a_{n}$ be $n$ complex numbers, then there exists a unique polynomial $P$ of degree less than or equal to $n$ such that $P(x_i)=a_i\ \forall\ i.$ Further, if $P(x_i)=a_i$, then $$P(x)=\displaystyle{\sum_{i=0}^na_i\prod_{0\le i\ne j\le n}\frac{x-x_j}{x_i-x_j}}.$$

Pell's Equation

This equation was first studied extensively in India starting with Brahmagupta who found an integer solution to $92x^2+1=y^2$ in his Brahmasphutasiddhanta circa $628$. The Pell's Equation is also known as the Pell-Fermat Equation.

Theorem. The Pell's Equation $x^2-dy^2=1$ where $d$ is a square-free integer has infinitely many solutions $(x, y)$.

Solved Examples

Example $1$ (All Russian MO $2018$ Grade $10/6$). Let $a$ and $b$ be given positive integers. Prove that there are infinitely many positive integers $n$ such that $n^b + 1$ doesn’t divide $a^n + 1$.

Solution. We first choose a prime $p$ dividing $n^b+1$ that doesn't divide $a^n+1$. So, we want to construct a number $n$ such that $p\mid n^b+1$. Hence, $$n^b\equiv -1\pmod p.$$ So, we want an $n$ such that $\mathrm{ord}_p(n)=2b$. Let $p\nmid q$. Then, \begin{aligned} n^{2b} &\equiv q^{p-1}\pmod p \\ \iff n &\equiv q^{\frac{p-1}{2b}}\pmod p. \end{aligned} So, we want to get that $2b\mid p-1$. Next, we want $p\nmid a^n+1$ or $a^n+1\not\equiv 0\pmod p.$ We do one thing, we take $n$ such that $p-1\mid n$.  Let $n=(p-1)r$ for some $r$. Then, $$a^n+1=a^{(p-1)r}+ 1 \equiv 1+1=2\not \equiv 0\pmod p.$$ Thus, we make the following constructions \begin{aligned} \begin{cases} n &\equiv q^{\frac{p-1}{2b}}\pmod p \\ n &\equiv 0\pmod{p-1}\\ p &\equiv 1\pmod{2b}. \end{cases} \end{aligned} Now, we can choose infinitely many primes $p$ with $p\equiv 1\pmod{2b}$ due to Dirichlet's Theorem on Arithmetic Progression. Hence, we can conclude that there exists infinitely many such $n'$s.


Example $2$ (RMM $2012/4$). Prove that there are infinitely many positive integers $n$ such that $2^{2^n+1}+1$ is divisible by $n$ but $2^n+1$ is not.

Solution.  We first claim that if a number $k$ satisfies the conditions, then so does $\ell=2^k+1>k$.

Claim. If $k$ satisfies the conditions, then so does $2^k+1$.

$Proof.$ Let $2^k+1=\ell>k$. Firstly, since $\ell$ is not divisible by $k$, therefore, $2^{\ell}+1$ is not divisible by $2^k+1$. Hence, $\ell \nmid 2^{\ell}+1$. But, note that $$2^{2^{2^k+1}+1}+1 = (2^k+1)(\text{something}),$$ since $k\mid 2^{2^k+1}+1$. Hence, $2^k+1\mid 2^{2^{2^k+1}+1}+1$, implying that $\ell\mid 2^{2^\ell+1}+1.$ So, $\ell\mid 2^{2^\ell+1}+1$ and $\ell\nmid 2^\ell+1$, as desired. Now, some checking, starting from $5\times 3$, $7\times 3$, $11\times 3,\ldots,$ $19\times 3$, we see that at last $k=19\times 3=57$ works! 

Hence, we can conclude that there exists infinitely many such positive integers $n$ satisfying the given conditions.


Okay, so that's enough, I guess... If you want to look into or try more problems, you can get them here. If you have have questions regarding this post, please feel free to comment. Also, if there is a mistake in this post, please do comment. I shall try to correct it. Hope to see you soon. Until then, bye...

Emon.



Comments

  1. Nice work, i appreciate your effort for making a 25-problem pset, I think this is some unique and hard work by you.

    ReplyDelete

Post a Comment

Popular posts from this blog

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

Kőnig-Egerváry theorem

Graph theory has been my most favourite thing to learn in maths and and in this blog i hope to spread the knowledge about Kőnig's theorem. It is advised that the readers are aware about basic graph theory terminologies including bipartite graphs. Before going on to the theorem i would like to go on about matchings and vertex cover which we are going to use in the theorem  Matchings A matching $M$ of a graph $G$ is a subset of the edges of a graph in which no two edge share a common vertex (non adjacent edges). For example :- The Matching $M$ over here is edge $\{ 3 - 5 , 1-2 , \}$ or $\{ 1 - 2 , 4 - 3 \}$ etc .  Maximum Matching is a matching that contains the largest possible number of edges for instance in the above example the maximum matching is 2 edges as there cannot be a subset of non adjacent edges having greater than 2 edges (Readers are advised to try so they can convince themselves) A Perfect Matching  is a matching that matches all vertices of the graph or in other sen

Algorithms, or Mathematics?!

Hi everyone! In my last blog, I spoke about a couple of very interesting algorithmic techniques and how they can be used to solve a variety of very interesting problems. This blog however, is going to be completely different.   When we’re young we begin by learning the steps to add – we’re given the rules and we must learn to repeat them – no questions asked. Why does carry forward work the way it does? Well, no questions asked. To some extent, it is important to know how exactly to do a certain set of things while first learning maths. We may not be able to get anywhere in a subject if we’re unable to learn a few basic rules and know how to use them. However, after a certain point it is important to bring in the spirit of mathematical thinking within each student too – something missing in almost every form of school math education. Mathematical miseducation is so common, we wouldn’t even see it. We practically expect a math class to look like repetition and memorisation of disjointed