• Mood:

# NumberTheory101 (#2): Euclidean Algorithm

## Modular Arithmetic (Continued)

### More Tricks

First off, I want to add to the modular arithmetic thing from last week. I want to show you a couple more tricks for making the calculations easy.

One key in some of the problems from last week was that some ornery looking numbers were really congruent to one or zero modulo the base. For example, 241 % 5 = 1. This simplified much of the calcuation because ones are easy to multiply and exponentiate. But, what if the problem had been looking for 249^14 % 5? Well, 249 == 4  (mod 5). You wouldn't want to have to take four to the fourteenth power unless you had no other option. In this case, you have a great option because 4 == -1  (mod 5). Thus, 4^14 % 5 is the same as (-1)^14 % 5 = 1.

For calculation purposes, you can let the number get below zero or above the modulus (in the examples that I showed you, the modulus was five) for as long as you like. The final answer should be greater than or equal to zero and less than the modulus, but you can use whatever numbers are most convenient for you in the intermediate steps.

### Equivalence Relation

One important thing about this modular arithmetic. Modular arithmetic is an equivalence relation. Now, what does that mean? First, the symbol ~ is used to represent a relationship. For example, to express that a and b are related, one would write a ~ b.

Equivalence Relation
If a, b, and c are three elements that could possibly be related, the relation ~ is an equivalence relation if and only if all of the following hold:
1. a ~ a
2. a ~ b implies b ~ a
3. a ~ b and b ~ c implies a ~ c

That's a little bit abstract. Let's look an easy example. The relationship "...has the same hair color as..." is an equivalence relation. For any three people---Alice, Bob, and Carol---, all three conditions hold. Alice has the same hair color as Alice. If Alice has the same hair color as Bob, then Bob has the same hair color as Alice. If Alice has the same hair color as Bob and Bob has the same hair color as Carol, then Alice has the same hair color as Carol. This holds no matter who Alice, Bob, and Carol are.

For the record, the three properties of an equivalence relationship are named (in the order enumerated above) the Reflexive Property, the Symmetric Property, and the Transitive Property.

Now, let's look at some examples that are not equivalence relationships. It will be instructive if you take the time to figure out which of the three conditions do not hold for each of these examples:

1. ...is a descendent of...
2. ...is at least as old as...
3. ...lives within five miles of...

Imagine trying to sort something based on the equivalence relation. Start by putting one thing in a (very small) pile. Then, take one of the unsorted things. Check it against some item from each pile. If it is related to an element from some pile, then put the item in that pile. If it doesn't match an item from any pile, start a new pile.

The conditions for an equivalence relation guarantee you some nice things about this sorting process. First off, if there are forty items in one pile, it doesn't matter which one you compare the item against. The third condition for the equivalence relation guarantees that if it is related to any item in the pile, it is related to every item in the pile. Secondly, that same condition also ensures that your item will only ever match one pile.

This is called a partition of the elements. Each element is in one and only one pile.

For the relationship "...is equivalent modulo n to...", this partitioning idea comes in handy. For a given n, every integer falls into one and only pile. In each pile, all of the numbers in that pile can be used equivalently for modular arithmetic. Because of this, when one is dealing with modular arithmetic, one can often exhaust the possibilities quickly. There are infinitely many integers, but there are only n equivalence classes (piles) modulo n. More on this in the next segment.

### What Good Is Modular Arithmetic?

Suppose you were looking for Pythagorean Triples (and I know you were) and you needed to know whether 22,222 was a perfect square. You could try calculating the square root or guessing. Or, you could observe the following: 22,222 == 2  (mod 5). That means that if a^2 = 22,222, then a^2 == 2  (mod 5). Modulo five, there are only five possibilities for a. We can easily check:

• 0^2 == 0  (mod 5)
• 1^2 == 1  (mod 5)
• 2^2 == 4  (mod 5)
• 3^2 == 4  (mod 5)
• 4^2 == 1  (mod 5)

It is impossible for a perfect square to be congruent to two (or three) modulo five. (This is one small result in a larger subject Quadratic Residues which we'll get to in a later lesson). Note, this does not mean that every number which is congruent to four modulo five is a perfect square. But, it does mean that any number which is not congruent to zero, one, or four modulo five is not a perfect square.

Burton has some good examples of why one would want to use modular arithmetic in his exercises for section 2.1 on pages 19 and 20. He uses a technique similar to the one above to show that there are no perfect squares that are congruent to two modulo three. I don't know about you though, but I can't just tell by looking at a number what its remainder will be modulo three.

Another exercise there has one verify that the expression n * (n + 1) * (2 * n + 1) / 6 is always an integer. We know that n is congruent to either 0, 1, 2, 3, 4, or 5 when considered modulo 6. Thus, we can simply check that the expression n * (n + 1) * (2 * n + 1) is congruent to zero modulo six when n takes on any of those six values.

I'm sure will come upon many other uses of modulo arithmetic later.

## Greatest Common Divisor

### Divisibility

You're probably pretty clear on what it means to say that an integer b is divisble by an integer a. Precisely, it means that there exists some other integer c so that b = a * c. When b is divisble by a, we write that a | b (which is read "a divides b").

Burton lists all of these facts about divisibility (given integers a, b, c, and d:

• a | 0
• 1 | a
• a | a
• a | 1 if and only if a is plus or minus one.
• If a | b and c | d, then a*c | b*d.
• a | b and b | a if and only if a is plus or minus b.
• If a | b and b is not equal to zero, then |a| <= |b|.
• If a | b and a | c, then a | (b*x + c*y) for arbitrary integers x and y.

It is straightforward enough to exhibit proofs of the most of these. The first, for example, is obvious because 0 = a * 0.

### Greatest Common Divisor

For any two integers a and b (with at least one of them not zero), there are some positive integers d such that d | a and d | b. There is definitely at least the possibility d = 1 because 1 | a for all a. From the last two properties of divisibility stated above, we can see that d must be less than or equal to |a| + |b|. Thus, one can use the Well-Ordering principle on the set of positive numbers |a| + |b| + 1 - d to obtain the smallest member of that set which will be from the largest possible d. That d is called the Greatest Common Divisor of a and b. This is written gcd(a,b). Some just write (a,b), but I find that notation confusing.

I sorta threw two things together there that you may prefer to have separated. First, if you can show that a non-empty set of integers is bounded from above, then you can use the Well-Ordering Principle to find the largest member of the set. Second, the largest number that divides both a and b is their Greatest Common Divisor. (What an appropriate name, eh?)

Note that because every number divides zero, the Greatest Common Divisor of zero and zero is ill-defined (and thus left undefined).

## The Euclidean Algorithm

One can find the Greatest Common Divisor of two numbers in several ways. One could simply try all of the numbers up to and including |a| + |b|. That works okay for small numbers. One could also completely factor each number, see which primes (and to what power those primes are) that they share, and determine the Greatest Common Divisor. This works okay for numbers which are easily factored. Or, one can use the Euclidean Algorithm.

First, lets do an example of finding the Greatest Common Divisor using factoring. If I have two numbers a = 90 and b = 108, then I would factor each of them. a = 2 * 3^2 * 5 and b = 2^2 * 3^3. The largest amount that they have in common is d = 2 * 3^2 = 18.

As you may have guessed, the Euclidean Algorithm is a fair bit easier to use than the others. The only thing you need to use is the Division Algorithm.

Here's how the Euclidean Algorithm works to determine the Greatest Common Divisor of a and b.

Express a in the form q b + r with r greater than or equal to zero and less than |b| using the Division Algorithm.

If r is zero

Then b is the Greatest Common Divisor

Otherwise,

Start again with a equal to what b was this time and b equal to r

Let's use the Euclidean Algorithm to determine gcd(1776,1492).

• 1776 = 1 * 1492 + 284
• 1492 = 5 * 284 + 72
• 284 = 3 * 72 + 68
• 72 = 1 * 68 + 4
• 68 = 17 * 4 + 0

That means that gcd(1776,1492) = 4.

## Problems

1. Calculate:
1. ( 3^19) % 4
2. ( (53 * 26 + 906)^24 ) % 5
3. ( 3^19) % 7
2. Use the Euclidean Algorithm to determine:
1. gcd(1536,1152)
2. gcd(1152,1536)
3. gcd(256,55)
3. Think about how the Euclidean Algorithm would work for:
1. gcd(360,72)
2. gcd(360,-72)
3. gcd(-360,-72)

## Next Week

We're going to do a few more things with the Greatest Common Divisor next week. Then, we're going to move on to a small discussion about doing modular arithmetic with prime numbers as the modulus. We'll probably take a short dipinto Group Theory for a moment, there. Then, we'll talk a little bit about factoring numbers.

• Post a new comment

#### Error

default userpic