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.

We are not interested in how many multiples are taken away. i. e. We are not interested in the quotient. We only want the 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 in Elementary Number Theory.

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)^{n} ≡ b^{n} (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^{100}.

Finding the last decimal digit of 13^{100} is same as finding the remainder when 13^{100} is divided by 10.

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^{3}. 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^{326} 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^{12} ≡ 1 (mod 42).

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

(i) x (ii) gives 5^{324} x 5^{2} ≡ 1 x 25 (mod 42)

⇒ 5^{326} ≡ 25 (mod 42)⇒ when 5^{326} is divided by 42, remainder = 25. Ans.

Get The Best Grades With the Least Amount of Effort

Here is a collection of proven tips, tools and techniques to turn you into a super-achiever - even if you've never thought of yourself as a "gifted" student.

The secrets will help you absorb, digest and remember large chunks of information quickly and easily so you get the best grades with the least amount of effort.

If you apply what you read from the above collection, you can achieve best grades without giving up your fun, such as TV, surfing the net, playing video games or going out with friends!

If G.C.F. of two numbers m_{1} and m_{2} = G.C.F.(m_{1}, m_{2}) = 1, then we can find two integers i_{1}, i_{2} such that m_{1}i_{1} + m_{2}i_{2} = 1.

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

Statement of The Chinese remainder theorem

If a number a gives remainder b_{1}, when divided by m_{1} and remainder b_{2}, when divided by m_{2}, then it (a) gives remainder (m_{1}i_{1}b_{2} + m_{2}i_{2}b_{1}) when divided by m_{1}m_{2}, where i_{1}, i_{2} are two integers such that m_{1}i_{1} + m_{2}i_{2} = 1.

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

if a ≡ b_{1}(mod m_{1}) and a ≡ b_{2}(mod m_{2}), then a ≡ (m_{1}i_{1}b_{2} + m_{2}i_{2}b_{1}) (mod m_{1}m_{2})

Corollary of Chinese Remainder Theorem :

In the above theorem, if b_{1} = b_{2} = b, then a ≡ b (mod m_{1}m_{2}).

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_{1} and i_{2} such that5i_{1} + 21i_{2} = 1. By trial and error, i_{1} = -4 and i_{2} = 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.

Progressive Learning of Math : Elementary Number Theory

Recently, I have found a series of math curricula (Both Hard Copy and Digital Copy) developed by a Lady Teacher who taught everyone from Pre-K students to doctoral students and who is a Ph.D. in Mathematics Education.

This series is very different and advantageous over many of the traditional books available. These give students tools that other books do not. Other books just give practice. These teach students “tricks” and new ways to think.

These build a student’s new knowledge of concepts from their existing knowledge. These provide many pages of practice that gradually increases in difficulty and provide constant review.

These also provide teachers and parents with lessons on how to work with the child on the concepts.

The series is low to reasonably priced and include