## math_class: Number Theory 101 (Euclidean Algorithm)## Modular Arithmetic (Continued)## More TricksFirst 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, 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 RelationOne important thing about this modular arithmetic. Modular
arithmetic is an - 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 ## What Good Is Modular Arithmetic?Suppose you were looking for Pythagorean Triples (and I know you
were) and you needed to know whether 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
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
I'm sure we'll come upon many other uses of modulo arithmetic later. ## Greatest Common Divisor## DivisibilityYou're probably pretty clear on what it means to say that an
integer Burton lists all of these facts about divisibility (given integers **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
## Greatest Common DivisorFor any two integers 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 Note that because every number divides zero, the Greatest Common Divisor of zero and zero is ill-defined (and thus left undefined). ## The Euclidean AlgorithmOne can find the Greatest Common Divisor of two numbers in
several ways. One could simply try all of the numbers up to
and including First, lets do an example of finding the Greatest Common Divisor
using factoring. If I have two numbers 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
Let's use the Euclidean Algorithm to determine **1776 = 1 * 1492 + 284****1492 = 5 * 284 + 72****284 = 3 * 72 + 68****72 = 1 * 68 + 4****68 = 17 * 4 + 0**
That means that ## 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 WeekWe'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. |