The Chinese Remainder Theorem:

The Chinese Remainder Theorem: is a result of congruences in number theory and some aspects of abstract algebra. It was first published in the 3rd to 5th centuries by Chinese mathematician Sun Tzu. 

The Chinese Remainder Theorem: says if m (one) and m (two) are relatively prime then the system of congruences 

has a unique solution mod m (one) m (two). 

"max" + "may"= 

Example: Find the unique solution to the following congruences: 

so, now we assign all the letters to a specific number,

since (11,9) =1, then there exists x and y so that 

11x+9y=1

using Euclid's formula: we see that 11(5) + 9(-6) = 1

so by this formula we see that x=5 and y= -6. 

Now we will use the "max" + "may" formula: 

=11(2)(5)+ 9(6)(-6)

=  110 - 324

= -214

therefore N=83. 

Example: Find the unique solution to the following congruences: 

so now we assign the letters to a specific number, 

since (5,3) =1 then there exists x and y so that

5x + 3y =1

using Euclid's formula: we see that 5(2) + 3(-3) =1

so by this formula we see that x=2 and y=-3. 

Now we will use the "max"+ " may" formula: 

= 5(2)(2) + 3(3)(-3)

= 20 + -27

= -7

therefore N = 8

Quiz Question: Find the unique solution to the following congruences: 

using the chinese remainder theorem and the "max" + "min" formula. 

.

Credit due to: wikipedia and my class notes

Modular Arithmetic

MODULAR ARITHMETIC: 

Modular Arithmetic is the mathematics of remainders. 

 if m l a-b the number m is called the modulus. 

A common example for Modular Arithmetic is Clock Arithmetic: 

There is an additive law to modular arithmetic that says: 

There is also a commutative law to modular arithmetic that says: 

Example: What is 38 mod 12?

So what you do is divide 12 into 38 and see what the remainder is, 

Example: What is 59 mod 4? 

Examine Question: What is 83 mod 5? 

There are two different tricks to finding mod's the first method is called the casting out nines method: 

the casting out nines method states that for a positive integer x, we define S(x) to be the sum of the digits of x. 

Example: What is S(5409)?

So we need to add all the number in S(x) together and we get 5+4+0+9=18

Now we claim: that 

so using our claim we get 

Examine Question: What is S(1688)?

The second method is just like the casting out of the nines method but using mod 11. So for a positive integer x, we define S(x) to sum of the digits of x. 

Example: What is S(13748)? 

1-3+7-4+8=13

Now we claim that

so using our claim we get 

Examine Question: What is S(34693)?

Work cited to: our lecture notes 

Whats that, its the Euclidean Algorithm

 The Euclidean Algorithm 

• The Euclidean Algorithm is a method for computing the greatest common divisor (gcd) of two integers. It is named after the Greek mathematician Euclid, who described it in books VII and X of his elements. 
• The GCD of two positive integers is the largest integer that divides both of them without leaving a remainder.

In its simplest point, Euclid's algorithm starts with a pair of positive integers, and forms a new pair that consists of the smaller number and the difference between the larger and smaller numbers. The process repeats until the numbers in the pairs are equal. That number than is the greatest common divisor of the original pair of integers. 

                                                  How to set up the Algorithm: 

We will be given two positive integers a and b. We then divide a by b and get a remainder r. If r equals 0, the your b will become your gcd of the two integers a and b. 

Question: When does the remainder stop, will it ever stop? 

Answer: At each round of the algorithm the remainder will go down at least by one, so therefore r will eventually equal zero. 

Exercise: What is the gcd (65, 40)?

65 = 40 (1) + 25

40 = 25 (1) + 20

25 = 20 (1) + 5

20 = 5 (4) + 0

since the remainder is 0 the gcd (65, 40) = 5. 

Exercise: What is the gcd (168, 40)?

168 = 40 ( 4) + 8

40  =  8  ( 5 ) + 0

since the remainder is 0 the gcd (168, 40) = 8.

Potential Examine Question: What is the gcd ( 239, 19)? 

Citations;
1.http://en.wikipedia.org/wiki/Euclidean_algorithm
2.http://www.math.rutgers.edu/~greenfie/gs2004/euclid.html