ELEMENTARY NUMBER THEORY - LINKS; CONGRUENCES, EULER'S, FERMAT'S, CHINESE THEOREMS

Please study  Number Systems before Elementary Number Theory.
We introduced Natural Numbers there.
The branch of mathematics which deals with the study of
natural numbers, is called number theory.

Here we deal with a part of it.
Here Natural Numbers are studied without use
of techniques from other mathematical fields.

The various topics include
Divisibility Rules,

Greatest Common Factor by Euclidean Algorithm,

Least Common Multiple,

Prime Factorization,

Fundamental theorem of arithmetic,

Prime Numbers,

List of Prime Numbers,

Investigation of Perfect Numbers.

Other topics include, Modular Arithmetic (Congruences),
which is simply the arithmetic of remainders.

Several important discoveries of Elementary Number Theory are
Fermat's little theorem, Euler's theorem,
the Chinese remainder theorem.

We cover these theorems of Elementary Number Theory
with examples to make
even a high school student can understand them.

For students, who study Elementary Number Theory,
in their under graduate or graduate courses,
this page will serve as a simple introduction.

Modular Arithmetic (Congruences) of Elementary Number Theory

We know, from the knowledge of  Division,
Dividend = Remainder + Quotient x Divisor.

If we denote dividend by a, Remainder by b,
Quotient by k and Divisor by m, we get

a = b + km
⇒ a = b + some multiple of m
⇒ a and b differ by some multiples of m

or if you take away some multiples of m from a, it becomes b.

Taking away some (it does n't matter, how many) multiples
of a number from another number to get a new number
has some practical significance.

Example 1 of Elementary Number Theory : Congruences

For example, look at the question
Today is Sunday. What day will it be 200 days from now ?

How do we solve the above problem ?

We take away multiples of 7 from 200.
We are interested in what remains
after taking away the mutiples of 7.

Let us show the process of dividing 200 by 7,
using our knowledge of   Long Division.

              Dividend
 Divisor   7 )   200   ( 28   Quotient    
                 14
                 ---
                  60
                  56    
                 ---  
                   4   Remainder 
                 ---   

We get 4 when some (28) multiples of 7 are taken away from 200.

∴ The question, "What day will it be 200 days from now ?"
now, becomes, "What day will it be 4 days from now ?"
Because, today is sunday, 4 days from now will be Thursday. Ans.

The point is, when, we are interested in taking away multiples of 7,
200 and 4 are the same for us.

Mathematically, we write this as
200 ≡ 4 (mod 7)
and read as 200 is congruent to 4 modulo 7.

The equation 200 ≡ 4 (mod 7) is called Congruence.

Here 7 is called Modulus and the process is called
Modular Arithmetic.

Let us see one more example.

Example 2 of Elementary Number Theory : Congruences

It is 7 O' clock in the morning.
What time will it be 80 hours from now ?

We have to take away multiples of 24 from 80.
80 ÷ 24 gives a remainder of 8.
or 80 ≡ 8 (mod 24).

∴ The time 80 hours from now is
the same as the time 8 hours from now.

7 O' clock in the morning + 8 hours = 15 O' clock
= 3 O' clock in the evening [ since 15 ≡ 3 (mod 12) ].

Let us see one last example
before we formally define Congruence.

Example 3 of Elementary Number Theory : Congruences

A person is facing East. He rotates 1260 degree anti-clockwise.
In what direction, he is facing ?

We know, rotation of 360 degrees
will bring him to the same position.

So, we have to remove multiples of 360 from 1260.
The remainder, when 1260 is divided by 360, is 180.
i. e. 1260 ≡ 180 (mod 360).

∴ rotating 1260 degrees is same as rotating 180 degrees.

∴ when he rotates 180 degrees anti-clockwise from east,
he will face west direction. Ans.

Definition of Congruence

Let a, b and m be any integers with m not zero,
then we say a is congruent to b modulo m,
if m divides (a - b) exactly without remainder.
We write this as a ≡ b (mod m).

Other ways of defining Congruence include :

(i) a is congruent to b modulo m,
if a leaves a remainder of b when divided by m.

(ii) a is congruent to b modulo m,
if a and b leave the same remainder when divided by m.

(iii) a is congruent to b modulo m,
if a = b + km for some integer k.

In the three examples above, we have

200 ≡ 4 (mod 7); in example 1.

80 ≡ 8 (mod 24); 15 ≡ 3 (mod 12) in example 2.

1260 ≡ 180 (mod 360). in example 3.

We started our discussion with the process of division.
In division, we dealt with whole numbers only and
also, the remainder, is always less than the divisor.

In Modular Arithmetic, we deal with integers
( i.e. whole numbers + negative integers).

Also, when we write a ≡ b (mod m),
b need not necessarily be less than a.

The three most important properties of congruences modulo m are:

The reflexive property :

If a is any integer, a ≡ a (mod m).

The symmetric property :

If a ≡ b (mod m), then b ≡ a (mod m).

The transitive property :

If a ≡ b (mod m) and b ≡ c (mod m),
then a ≡ c (mod m).

Other properties :

If a, b, c and d, m, n are any integers with
a ≡ b (mod m) and c ≡ d (mod m), then

a + c ≡ b + d (mod m)
a - c ≡ b - d (mod m)
ac ≡ bd (mod m)
(a)ⁿ ≡ bⁿ (mod m)

If gcd(c,m) = 1 and ac ≡ bc (mod m),
then a ≡ b (mod m)

Example 4 of Elementary Number Theory : Congruences

Find the last decimal digit of 13¹⁰⁰.

Finding the last decimal digit of 13¹⁰⁰ is same as
finding the remainder when 13¹⁰⁰ is divided by 10.

We know 13 ≡ 3 (mod 10)
∴ 13¹⁰⁰ ≡ 3¹⁰⁰ (mod 10)
.....(i)

We know 3² ≡ -1 (mod 10)
∴ (3²)⁵⁰ ≡ (-1)⁵⁰ (mod 10)
∴ 3¹⁰⁰ ≡ 1 (mod 10)
.....(ii)

From (i) and (ii), we can say
last decimal digit of 13¹⁰⁰ is 1. Ans.

The Theorems of Elementary Number Theory, that follow
are based on modular Arithmetic (congruences).

Fermat's little theorem of Elementary Number Theory

If p is a prime number and
x is any integer that does not have p as a factor,
then x^{(p - 1)} ÷ p gives remainder 1.

In the notation of modular arithmetic,
we can write this statement as
x^{(p - 1)} ≡ 1 (mod p).

Examples :

Example 5 of Elementary Number Theory : Fermat's little theorem

Find the remainder when 7⁹⁶ is divided by 97.

Solution :
Since 97 is a prime number and is not a factor of 7
and the exponent is 96 = 97 - 1, we can apply
Fermat's little theorem.

∴ 7⁹⁶ ≡ 1 (mod 97).
i.e. When 7⁹⁶ is divided by 97, remainder = 1.Ans.

Example 6 of Elementary Number Theory : Fermat's little theorem

Find the remainder when 63³⁰ is divided by 31.

Solution :
Since 31 is a prime number and is not a factor of 63
and the exponent = 31 - 1 = 30, we can apply
Fermat's little theorem.

63³⁰ ≡ 1(mod31)
or 63³⁰ ÷ 31 gives remainder 1.Ans.

Euler's theorem of Elementary Number Theory

If x and y are co-primes, then
x^{totient of y}÷y gives remainder 1,
where totient of y
= number of positive integers that are co-prime to y and less than y.

In the notation of modular arithmetic,
we can write this statement as
x^{totient of y} ≡ 1 (mod y).

Finding totient of y :

If y is expressed as a product of prime factors, say
y = a^p x b^q x c^r x ......
( i.e. a, b, c,.... are distinct prime factors of y and
p, q, r,....... are their multiplicitys (exponents) respectively),
then, totient of y = yx(1- 1⁄a)x(1- 1⁄b)x(1- 1⁄c)x.....

For example, 8 = 2³.
totient of 8 = 8(1- 1⁄2) = 8(1⁄2) = 4.

We can also verify that
the four numbers 1, 3, 5, 7 are co-prime to 8.

Note :
(i) totient of y is denoted by φ(y) and is called
Euler's totient function or Euler's phi function. This is an important function in Elementary Number Theory.

(ii) if y is a prime number, prime factor of y = y
then, totient of y = y((1 - 1⁄y) = y - 1.

Then Euler's theorem becomes
x^{(y - 1)} ÷ y gives remainder 1.
Which is nothing but Fermat's Little Theorem.
Note that, here, x and y are co-primes and y ia a prime number.

Thus, Fermat's Little Theorem is a special case of Euler's theorem.

Example 7 of Elementary Number Theory : Euler's Theorem

Find the remainder when 5³²⁶ is divided by 42.
Prime Factorization  of 42 gives
42 = 2 x 3 x 7.

totient of 42 = 42(1- 1⁄2)(1- 1⁄3)(1- 1⁄7)
= 42 x 1⁄2 x 2⁄3 x 6⁄7 = 12

Since 5 and 42 are co-prime, by Euler's theorem,
5¹² ≡ 1 (mod 42).

Here, we make use of properties of congruences of Elementary Number Theory given above.

⇒ (5¹²)²⁷ ≡ 1²⁷ (mod 42).
⇒ 5³²⁴ ≡ 1 (mod 42)......(i)

We know 5² ≡ 25 (mod 42).....(ii)

(i) x (ii) gives 5³²⁴ x 5² ≡ 1 x 25 (mod 42)

⇒ 5³²⁶ ≡ 25 (mod 42) ⇒ when 5³²⁶ is divided by 42, remainder = 25. Ans.

The Chinese remainder theorem of Elementary Number Theory

The following idea of   Greatest Common Factor (G.C.F.)
is used here.

If G.C.F. of two numbers m₁ and m₂
= G.C.F.(m₁, m₂) = 1, then
we can find two integers i₁, i₂
such that m₁i₁ + m₂i₂ = 1.

For example, G.C.F.(3, 7) = 1.
We can find i₁ = -2 and i₂ = 1
by trial and error
such that 3i₁ + 7i₂ = 3(-2) + 7(1) = -6 + 7 = 1.

Statement of The Chinese remainder theorem

If a number a gives remainder b₁, when divided by m₁
and remainder b₂, when divided by m₂,
then it (a) gives remainder (m₁i₁b₂ + m₂i₂b₁)
when divided by m₁m₂,
where i₁, i₂ are two integers
such that m₁i₁ + m₂i₂ = 1.

In the notation of modular arithmetic,
we can write this statement as

if a ≡ b₁(mod m₁)
and a ≡ b₂(mod m₂),
then a ≡ (m₁i₁b₂ + m₂i₂b₁) (mod m₁m₂)

Corollary of Chinese Remainder Theorem :

In the above theorem, if b₁ = b₂ = b,
then a ≡ b (mod m₁m₂).

Example 8 of Elementary Number Theory : Chinese Remainder Theorem

Let us first take up the original problem solved by
Chinese Remainder Theorem in Elementary Number Theory.

How many soldiers are there in Han Xing's army? -
If you let them parade in rows of 3 soldiers, two soldiers will be left.
If you let them parade in rows of 5, three will be left,
and in rows of 7, two will be left.

Solution :
Let a be the number of soldiers.
Then by data,
a ≡ 2 (mod 3); ...........(i)
a ≡ 3 (mod 5); ...........(ii)
a ≡ 2 (mod 7); ...........(iii)

We have to take two of the above equations, first
and apply the Chinese Remainder Theorem.

If we take (i) and (iii), we can apply the corollary, which is simpler.
we have G.C.F.(3, 7) = 1. Applying the corollary, we get
a ≡ 2 (mod 3 x 7) or a ≡ 2 (mod 21).......(iv)

Now let us apply the theorem to (ii) and (iv).
a ≡ 3 (mod 5); ...........(ii)
a ≡ 2 (mod 21)...........(iv)

We know G.C.F.(5, 21) = 1. So we can apply the theorem.
Let us find i₁ and i₂ such that 5i₁ + 21i₂ = 1.
By trial and error, i₁ = -4 and i₂ = 1

By the theorem, we get,
a ≡ {5(-4)2 + 21(1)(3)} (mod 5 x 21) or a ≡ 23 (mod 105)
⇒ a is such that when it is divided by 105 gives remainder 23.
or a = 23 + k (105) where k is an integer.
If k = 0 is taken, then a = 23 + 0 = 23 is a possible answer.

23 satisfies the three equations, as we can see.
23 ≡ 2 (mod 3); ...........(i)
23 ≡ 3 (mod 5); ...........(ii)
23 ≡ 2 (mod 7); ...........(iii)

Thus 23 is the lowest answer.
The general answer is 23 + k (105) where k is a whole number.

To study more about these theorems and other topics of
Elementary Number Theory, you may refer other sources.