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 theorem. Fermat 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.