Elementary Number Theory

Introduction

We have previously covered a short course on divisibility. In this chapter, we will generally focus on congruences. Loosely, congruence is a short notation that is extremely useful in solving various problems in number theory. Precisely, it is much more than just a notation.\\

Without further ado, let's get straight to the punchline.

Congruence Notation

If $a, b, m \in \mathbb{Z}$ such that $m \mid a - b$, then we write this as $a \equiv b \pmod{m}$.

This is really all there is to it! But with this notation, we will prove several interesting results in an easy way.

This notation or relation $\equiv$ has many similarities with the "$=$" sign. Some of the similar properties are enumerated below:

•   If $a \equiv b \pmod{m}$ and $b \equiv c \pmod{m}$, then $a \equiv c \pmod{m}$.
•   If $a \equiv b \pmod{m}$, then this is equivalent to $b \equiv a \pmod{m}$ and $a - b \equiv 0 \pmod{m}$.
•    If $a \equiv b \pmod{m}$ and $c \equiv d \pmod{m}$, then $a + c \equiv b + d \pmod{m}$ and $ac \equiv bd \pmod{m}$.
•    If $a \equiv b \pmod{m}$ and $c \in \mathbb{Z}$ and $c \neq 0$, then $ac \equiv bc \pmod{m}$.

The proofs of these $4$ basic properties are trivial.

Next, we have if $a \equiv b \pmod{m}$ holds true and $f(x)$ is a polynomial in $x$, then $f(a) \equiv f(b) \pmod{m}$. The proof of this also follows from the preceding four properties.

Basic  Theorems

Next, we state something important.

If $ac \equiv bc \pmod{m}$, then $a \equiv b \pmod{\frac{m}{(c, m)}}$.

Proof: Given $ac \equiv bc \pmod{m}$. This means $ac - bc = mz$, for some $z \in \mathbb{Z}$. Now, dividing both sides by $(c, m)$, we have

$\frac{c}{(c, m)}(a - b) = \frac{mz}{(c, m)}.$

This simply means that $\frac{m}{(c, m)} \mid \frac{c}{(c, m)}(a - b)$. But, $\left(\frac{m}{(c, m)}, \frac{c}{(c, m)}\right) = 1$, which means that $\frac{m}{(c, m)} \mid (a - b)$.

Corollary: 

A useful corollary to the preceding result is when $(c, m) = 1$, for then $ac \equiv bc \pmod{m}$ implies $a \equiv b \pmod{m}$.

We give the following useful result:

$$\begin{align*}\text{If } a &\equiv b \pmod {m_i} \text{ for } i = 1, 2, 3, \ldots, k, \\\text{then } a &\equiv b \pmod{[m_1, m_2, m_3, \ldots, m_k]}.\end{align*}$$

Proof: The proof of this result is straightforward. If $m_i \mid b - a$, then $b - a$ is just a multiple of all $m_i$ or the common multiple of $m_i$'s. So, $[m_1, m_2, \cdots, m_k] \mid a - b$. This proves our result.

Now, we introduce certain terminologies.

We consider $m \in \mathbb{Z}^+$. We call a set of $m$ integers $\{r_1, r_2, ..., r_m\}$ a complete residue system congruent modulo $m$ if each and every integer $y$ is congruent to one and only one of these numbers modulo $m$.

A set of $m$ integers is said to form a complete residue modulo $m$ iff no two of those numbers are congruent to each other modulo $m$.

This can be proved simply. If $r_i$'s form a complete residue system, then every integer is congruent to one and only one $r_i$ modulo $m$. If $r_k \equiv r_j \pmod m$, then if $b \in \mathbb{Z}$ is such that $b \equiv r_k \pmod m$, then $b \equiv r_k \pmod m$, and this contradicts the fact that one and only one $r_i$ is congruent to $b$ modulo $m$. So, we have established the claim in one direction.

For the other part, it's just the definition.

Next, if $x \equiv y \pmod m$, then $y$ is called a residue of $x$ modulo $m$.

Now, it is obvious that there are infinitely many complete residue systems of $m$. Two of them are $0, 1, 2, ..., m-1$ and $1, 2, \cdots, m$.

Now, in a complete residue system modulo $m$, we exclude those numbers which are not relatively prime to $m$, and consequently, we obtain a subset of the complete residue system of $m$, and this subset is called a reduced residue system congruent modulo $m$.

Also, there are infinitely many reduced residue systems of $m$.

This becomes clear with the following theorem.

If $r_1, ..., r_m$ is a complete or reduced residue system of $m$, and $(a, m) = 1$, then $ar_1, ar_2, ..., ar_m$ is also a complete or reduced residue system of $m$, respectively.

This can be proved easily.

But for that fact, we need to state the definition of a reduced residue system modulo $m$ in an alternative way.

A reduced residue system of $m$ is a set of numbers relatively prime to $m$, such that every other integer $y$ satisfying $(m, y) = 1$ is congruent to one of the numbers in this set, and no two numbers in this set are congruent to each other modulo $m$.

Now, we try to prove the preceding theorem.

If $r_1, r_2, ..., r_n$ is a set of complete or reduced residue system modulo $m$, and $(a, m) = 1$, then if $r_i \equiv 1 \pmod m$, we have $ar_i \equiv 1 \pmod m$.

The set $r_1, r_2, ..., r_n$ has the same cardinality as $ar_1, ar_2, ..., ar_n$.

Again, if $ar_i \equiv ar_j \pmod m$, then $r_i \equiv r_j \pmod m$, which further implies $i = j$.

This completes our proof.

Now, it's time for some interesting results.

We hereby state Euler's Theorem.

If $(a, m) = 1$, then $a^{\phi(m)} \equiv 1 \pmod m$.

Now, $\phi(m)$ is generally called the Euler's phi-function or sometimes the totient. It denotes the number of positive integers less than $m$ that are relatively prime to $m$.

Let $r_1, r_2, ..., r_{\phi(m)}$ be a reduced residue system of $m$. Then, $ar_1, ar_2, ..., ar_{\phi(m)}$ is also a reduced residue system modulo $m$. Hence, corresponding to each $r_i$, we have $ar_j \equiv r_i \pmod m$. Also, we have for  each $ar_j$ consequently we have one unique $r_i$ so that $ar_j \equiv r_i \pmod m.$ Hence, multiplying all such relations for each and every $r_i,$ we have $a^{\phi(m)}\prod_{i=1}^{\phi(m)}r_i\equiv \prod_{i=1}^{\phi(m)}r_i\pmod m.$ Now, this is again equivalent to $a^{\phi(m)}\equiv 1\pmod m.$ 

If $m=p,$ then $\phi(p)=p-1,$ so that, $a^{p-1}\equiv 1\pmod p\implies a^p\equiv a\pmod p.$

This is what we call the Fermat's Last Theorem, which states that, "If $p$ is a prime, and $a$ is an integer then $a^p\equiv 1\pmod p,$ and furthermore if, $(a,p)=1$ we have $a^{p-1}\equiv 1\pmod p.$"

We state another simple result, i.e

If $p$ is a prime then $x^2\equiv 1 \pmod p,$ iff $x\equiv \pm 1\pmod p.$

If $x^2\equiv 1\pmod p,$ then, $p|(x+1)(x-1).$ So, $p|(x-1)$ or $p|(x+1)$ and consequently, $x\equiv \pm 1\pmod p.$

Another groundbreaking theorem, we have is of Wilson's Theorem, which states that if $p$ is a prime number then, $(p-1)!\equiv -1\pmod p.$

If $p=2,3$ then the result is obvious. We assume $p\geq 5.$ Suppose that $1\leq a\leq p-1, $ then, $\exists \overline a,$ such that $1\leq \overline{a}\leq p-1,$ such that $a\overline{a}\equiv \pmod p.$ Furthermore, this $\overline a$  is unique. For if, say, there exists $1\leq a\leq p-1,$ then, since $(p,a)=1,$ we have, $a,2a,...,(p-1)a,pa$ a complete residue system of $p.$ Now, this complete residue system has at  a reduced residue system, and   an element that belongs to the reduced residue system, is coprime to $p,$ which means $\exists\overline{a},$ such that $1\leq\overline{a}\leq p$ satisfying, $a\overline{a}\equiv 1\pmod p.$ But $(pa,p)\neq 1,$ so we can exclude $p$ from the set of values that $\overline{a}$ takes on. So, precisely such an $\overline{a}$ exists. Now, we prove the uniqueness. This is easily seen by the fact that if say, $1\leq\overline{a_1},\overline{a_2}\leq p-1$ satisfying $a\overline{a_1}\equiv 1\pmod p$ and $a\overline{a_2}\equiv 1\pmod p$ then, $a\overline{a_1}\equiv a\overline{a_2}\pmod p\implies \overline{a_1}\equiv\overline{a_2}\pmod p,$ which can't be true as $\overline{a_1},\overline{a_2}$ are in the complete residue system of $p$ and so, no two elements are congruent to each other modulo $p.$ Similarly, for all $1\leq\overline{a}\leq p-1,$ we have an $a$ such that $1\leq a\leq p-1,$ satisfying $\overline{a}a\equiv 1\pmod p,$ and in addition, this $a$ is unique. Thus, $a,\overline{a}$  forms a pair such that $a\overline{a}\equiv 1\pmod p.$ But here a little more care is demanded, for if $a=\overline{a},$ then $a^2\equiv 1\pmod p,$ and then, we have, $a\equiv 1\pmod p,a\equiv -1\pmod p,$ which is true if $a=1,a=p-1$ respectively. For $2\leq a\leq p-2,$ we have no problem. Hence, we have $\prod_{i=1}^{p-2}a\equiv 1\pmod p\implies (p-1)!\equiv -1\pmod p.$ This completes the proof.

Throughout this section, we will further denote $p$ to be a prime.

The  $x^2\equiv -1\pmod p,$ has solutions iff $p=2$ or $p\equiv 1\pmod 4.$

If $p=2,$ then $x=1$ is a solution.

If $p=4k+1,$ (where $k\in \mathbb Z$ ) is an odd prime, then we consider $(p-1)!=[1.2.3...(\frac{p-1}{2})][(\frac{p+1}{2})....p].$ We have divided $(p-1)!$ into two parts such that each part contains an equal number of factors. We note that we have divided the two parts in such a way as if, $j$ is in the first part, $p-j$ is in the second part. We observer, that $(p-j)j\equiv -j^2\pmod p.$ Hence, we have $(p-1)!=\prod_{i=1}{\frac{p-1}{2}}j(p-j)\equiv (-1)^{\frac{p-1}{2}}\prod_{i=1}{\frac{p-1}{2}}j^2=((\frac{p-1}{2})!)^2\equiv -1\pmod p.$ So, $(\frac{p-1}{2})!$ is a solution when $p\equiv 1\pmod 4$. This serves as the proof of the first part.

Now, for the other part, we assume that if $x^2\equiv -1\pmod p,$ has solutions. We note that $p$ does not divide such an $x.$ Thus, $(p,x)=1.$ By FLT, $-x^{p-1}\equiv -1\pmod p.$ So, $x^{p-1}\equiv (-1)^{\frac{p-1}{2}}\pmod p\implies 1\equiv (-1)^{\frac{p-1}{2}}\pmod p.$ If $(-1)^{\frac{p-1}{2}}=-1,$ then it is noted that, $p|2,$ so $p=2.$ If this is not the case, it means $(-1)^{\frac{p-1}{2}}=1$ which implies that ${\frac{p-1}{2}}$ is even so, $p\equiv 1\pmod 4.$ This establishes our result.

Next, comes another important result by Albert Girard which was later proved by Fermat.

If $p$ is a prime number such that $p\equiv 1\pmod 4,$ then there exists positive integers $a,b$ such that $a^2+b^2=p.$

Let $p$ be a prime number such that $p\equiv 1\pmod 4.$ By the preceding theorem, we can guarantee the existence of an $x$ such that $x^2\equiv -1\pmod p.$ We define a function $f(u,v)=u+vx$ and $K=[\sqrt{p}].$ Since $\sqrt{p}$ is not an integer, so, $K< \sqrt{p}< K+1.$ We consider the pairs of integers $(u,v)$ where $u,v\in [0,K].$ So, the number of pairs of $(u,v)$ is $(K+1)^2.$ Now, $K+1> \sqrt{p}$ implies the number of pairs is greater than $p.$ Thus, if we consider $f(u,v)\pmod p,$ then we have more number of values under consideration than the possible remainders. So, there exist two pairs $(u_1,v_1)$ and $(u_2,v_2)$ that are distinct from one another, such that $f(u_1,v_1)\equiv f(u_2,v_2)\pmod p\Rightarrow u_1-u_2\equiv -x(v_1-v_2)\pmod  p.$ Let $u_1-u_2=a$ and $v_1-v_2=b.$ We can say that either $a\neq 0$ or $b\neq 0.$ Using this, we can write $a\equiv -bx\pmod p\Rightarrow a^2\equiv b^2x^2\equiv -b^2\pmod p.$ So, $p|a^2+b^2.$ Also, $u_1\leq K$ and $u_2\geq 0,$ implies $-K\leq u_1-u_2\leq K.$ Similarly, we have $|b|\leq K.$ But, $ K< \sqrt p,$ and hence, $|a|^2+|b|^2=a^2+b^2< 2p.$ The only multiple of $p$ in this range is $p,$ so $a^2+b^2=p.$

Next, we prove the last two results of this section.

Let $q$ be a prime factor of $a^2+b^2,$ such that $q\equiv 3\pmod 4$ then $q|a$ and $q|b.$

The strategy here is to prove the contrapositive, i.e., if $q\nmid a$ and $q\nmid b,$ then $q\not\equiv 3\pmod 4.$ We have $(a,q)=1.$ Let $\overline{a}$ be chosen so that $a\overline{a}\equiv 1\pmod q.$ Multiplying both sides of the congruence $a^2\equiv -b^2\pmod q$ by $-\overline{a}^2,$ we get $\overline{a}^2b^2\equiv -1\pmod q.$ Let $x=\overline{a}b.$ Thus, $x$ is a solution of $x^2\equiv -1\pmod q,$ which implies from the preceding theorem that $q\equiv 1\pmod 4$ or $q=2.$ This completes the proof.

Problem 11

Find the least positive integer $x$ such that $13|(x^2 + 1).$

Solution

The least positive integer is, $x=5.$ 

Problem 14

Show that $7|(3^{2n+1}+ 2^{n+2})$ for all $n.$

Solution

We have that, $3^{2n}.3\equiv 2^n.3\pmod 7$ and $2^{2}.2^n\equiv -2^n.3\pmod 7$ and adding these two congruence relations we have $3^{2n+1}+ 2^{n+2}\equiv 0\pmod 7\implies 7|(3^{2n+1}+ 2^{n+2}).$

Problem 17

Show that $61!+ 1\equiv 63!+ 1 \equiv 0\pmod{71}.$

Solution

We note that, $71|(62.63-1)=71|(63!+ 1)-(61!+ 1).$ This means $61!+ 1\equiv 63!+ 1 \pmod{71}.$

Also, by Wilson's Theorem, we have $70!=61!62.63\cdots 70\equiv -1\pmod {71}.$

This means $61!62.63\cdots 70\equiv -61!9!\equiv -(-61!)\equiv 61!\equiv -1\pmod {71}.$

So, we have $63! \equiv -1\pmod {71}.$

Problem 30

What are the last two digits in the ordinary decimal representation of

$3^{400}$ ?

Solution

We note that $3^5\equiv 43\pmod {10^2}.$

So, $3^{5\cdot 80}\equiv 43^{80}\pmod {10^2}.$

Again, $43^2\equiv 49\equiv 1\pmod {10^2}\implies  43^{80}\equiv 49^{40}\equiv 1\pmod {10^2}.$

So, finally, $3^{400}\equiv 1\pmod{10^2}.$

Hence, we conclude that the last two digits of $3^{400}$ is $01.$

Problem 35

 If $n$ is composite, prove that $(n - 1)!+ 1$ is not a power of $n.$

 Solution

By a corollary of Wilson's Theorem, if $n>4$ is composite, then $n \mid (n-1)!$.

If $n|(n-1)!+1,$ we have $n|1,$ if $n> 4,$ which is absurd.

So, $n$ is less than or equal to $4.$ The only value of $n$ such that $(n - 1)!+ 1$ is  a power of $n$ are $1,2,3.$ But neither of them are composite.

Problem 36

If $p$ is a prime, prove that $(p - 1)!+ 1$ is a power of $p$ if and only if

$p =2,3$ or $5.$

Solution

If $p> 5,$ let us assume $(p - 1)!+ 1=p^n.$ But $p-1$ is composite.

We have, $(p - 1)!=p^n-1.$ Cancelling the factor of  $p-1$ we have,$(p-2)!=p^{n-1}+p^{n-2}+...+1.$

Checking the modulo $p-1,$ on both the sides the above equation, we have, $(p-2)!\equiv 0\pmod{p-1}.$

Again, as $a-b|a^k-b^k,$ we have $p^{n-1}+p^{n-2}+...+1\equiv n\pmod{p-1}.$

So, $n=0.$ But then, $(p - 1)!=0,$ which is absurd.

Problem 44

Show that if $p$ is prime then $\binom{p-1}{k}\equiv(-1)^k\pmod p,$ for $0\leq k\leq p-1.$

Solution

We know that $\binom  {p-1}{k}$ is always an integer. 

We note that, $$(p-k)(p-k+1)\cdots(p-1)\equiv (-k)(-k+1)\cdots (-1)\pmod p.$$

[This can be proven easily from the fact that $(p-k)\equiv -k\pmod p, (p-k+1)\equiv -k+1\pmod p$ and so on.]

Now, $(-k)(-k+1)\cdots (-1) = (-1)^kk!$. Using this, we have

$$(p-k)(p-k+1)\cdots(p-1) \equiv (-k)(-k+1)\cdots (-1) = (-1)^kk! \pmod p \implies (p-k)(p-k+1)\cdots(p-1) \equiv (-1)^kk!$$ $$\pmod p.$$

Now, this is again equivalent to writing as

$\frac{(p-k)(p-k+1)\cdots(p-1)}{k!} \equiv (-1)^k \pmod p$ as

$\frac{(p-k)(p-k+1)\cdots(p-1)}{k!} = \binom{p-1}{k} \in \mathbb{Z},$ and $(k!,p)=1$ since

$k \leq p-1 < p.$ So, we have $\binom{p-1}{k} \equiv (-1)^k \pmod p,$ as required.

Problem 50

Given a positive integer $n,$ prove that there is a positive integer $m$

that to base ten contains only the digits $0$ and $1$ such that $n|m.$ Prove that the same holds for digits $0$ and $2,$ or $0$ and $3,$ $\cdots,$ or $0$ and $9,$ but for no other pair of digits.

Solution

We consider $n$ numbers $1, 11, 111, \ldots, \underbrace{111\cdots 1}_{\text{n 1's}}$. We assume that neither of these numbers leaves a remainder of $0$ when divided by $n$. If there were such a number in the above list, we would be done. So, the possible remainders on division by $n$ are $1, 2, \ldots, n-1$. Hence, we have $n$ numbers and $n-1$ remainders. By the Pigeonhole Principle (PHP), there exist two numbers that leave the same remainder on dividing by $n$. We call these two numbers $p=\frac{10^p-1}{9}$ and $q=\frac{10^q-1}{9}$. Without loss of generality (WLOG), let $p>q$. We then have $m=\frac{10^p-10^q}{9} \equiv 0 \pmod{n}$, and $m$ is, in fact, the required type of number.

Similarly, for a digit $2\leq i\leq 9$ we can proceed similarly by consider the list : $$i,ii,iii,\cdots, \underbrace {iii\cdots i}_{\text{n times}},$$ and then proceeding similarly as above.

Finally, for the last part if say, $n=10,$ and me suppose that $m$ is a number made of digits $2,3,$ then $n$ will never divide $m.$So, this property does not essentially hold for any other pair of digits.

Problem 52

Show that if p is prime then $p|((p - 2)! - 1),$ but that if $p> 5$ then

$(p-2)!- 1$ is not a power of $p.$

Solution

We note that $p-1\equiv -1\pmod p.$ Multiplying both sides of the relation by $-(p-2)!,$ we have $-(p-1)!\equiv (p-2)!\equiv 1\pmod p.$ This serves as a proof for the first part.

We note that $p-1\mid (p-2)!$. This means if $(p-2)!-1=p^k$, then we have $p-1\mid p^k+1$. Consequently, $p-1\mid p^k+1-p^k+1=2$. However, this is a contradiction as $p>5$.

Problem 56

Let $p$ be a prime number, and suppose that $x$ is an integer such that

$x^2 \equiv-2\pmod p.$ By considering the numbers $u + vx$ for various pairs $(u,v),$ show that at least one of the equations $a^2 + 2b^2 =p, a^2 + 2b^2=2p$ has a solution.

Solution

We call those numbers as $f(u,v).$ Next, we define $K=\sqrt p.$  Now, $\sqrt{p}\notin \mathbb{Z}$. So, we have the strict inequality, i.e., $K < \sqrt{p} < K+1$. We just assume that $0\leq u,v\leq K$ without any justification but just hope that this assumption will be a key to prove things. Also, this assumption does not affect any interest(s) of the given problem, so we are free to make such an assumption. Also because, taking this assumption preserves the generality of our  approach or solution. So, there is no harm, in making such an assumption, all in all. Now, we can note that the total number of $f(u,v)$'s that we have in our hand has a one-to-one correspondence with the total number of pairs of $(u,v)$ possible under the prior assumption( i.e $0\leq u,v\leq K$ ). So, the total number of $f(u,v)$'s possible is $(K+1)^2$ as the total number of pairs of $(u,v)$ possible under the prior assumption that $0\leq u,v\leq K$ is $(K+1)^2.$ We now consider the remainders on dividing these $K+1$ numbers (or $f(u,v)$'s) by $p$. The total number of remainders is $p$. Also, as $\sqrt{p} < K+1 \implies p < (K+1)^2$, we can conclude by the Pigeonhole Principle that two numbers (or $f(u,v)$'s) leave the same remainder on division by $p$. Let them be $f(u_1,v_1)=u_1+v_1x$ and $f(u_2,v_2)=u_2+v_2x$. So,

$ u_1+v_1x \equiv u_2+v_2x  \pmod{p} \implies u_1-u_2 \equiv -x(v_1-v_2) \pmod{p}. $

Let $a=u_1-u_2$ and $b=v_1-v_2$. Then, $a \equiv -bx \pmod{p} \implies a^2 \equiv b^2x^2 \equiv -2b^2 \pmod{p}$ as $x^2 \equiv -2 \pmod{p}$.

Again, $u_1 < K, u_2 > 0 \implies a < K$. Now, as $u_1 > 0$ and $u_2 < K$, we have $a = u_1 - u_2 > -K$. Using these, we can say $|a| < K$. Similarly, we can show that $|b| < K$. Squaring and adding these two inequalities gives us $a^2+2b^2 = |a|^2 + 2|b|^2 < 3K^2 < 3p$.

So, we have found out that $p \mid a^2 + 2b^2$ and $a^2 + 2b^2 < 3p$. The only possible multiples of $p$ in the interval $[p,3p)$ are $p$ and $2p$. So, either $a^2 + 2b^2 = p$ or $a^2 + 2b^2 = 2p$. Indeed, we have found that $a=u_1-u_2,b=v_1-v_2$ satisfies either one of the given equations in the original problem.