## 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^**is the same as

^{14}% 5**(-1)^**.

^{14}% 5 = 1For 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:**a ~ a****a ~ b**implies**b ~ a****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:

- ...is a descendent of...
- ...is at least as old as...
- ...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^**. Modulo five, there are only five possibilities for

^{2}== 2 (mod 5)**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^**. The largest amount that they have in common is

^{2}* 3^^{3}**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

ain the formq b + rwithrgreater than or equal to zero and less than|b|using the Division Algorithm.If

ris zeroThen

bis the Greatest Common DivisorOtherwise,

Start again with

aequal to whatbwas this time andbequal tor

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

- Calculate:
**( 3^**^{19}) % 4**( (53 * 26 + 906)^**) % 5^{24}**( 3^**^{19}) % 7

- Use the Euclidean Algorithm to determine:
**gcd(1536,1152)****gcd(1152,1536)****gcd(256,55)**

- Think about how the Euclidean Algorithm would work for:
**gcd(360,72)****gcd(360,-72)****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.