Linear Algebra Review

[matt grime]

In some order:

 

1 is not a prime; the modern definition (and I know you like your old ones) is that a prime is not allowed to be a unit (invertible multiplicatively).

 

Euclid's algorithm states that there is a constructive way to write the highest common factor of two integers, a and b as an integral combination of them. That is to say

 

if d =hcf(a,b) then there are integers s and t such that as+bt=d.

 

 

A map between two "sets with structure" (eg a binary operation or two) is an isomorphism if it is a bijection on the underlying sets and it preserves the structure.

 

So, for example, two groups, H and G are isomorphic if there is a map f:H-->G such that f(x*y)=f(x)*f(y) and f(x^-1) = f(x)^{-1} and f is a bijection on the underlying sets. I use * to denote the generic composition of elements in G and H.

 

So isos send inverses to inverses and identities to identities.

 

Thus if f is an iso between two fields it must preserve both the + and * of the field, and it must send 0 to 0 and 1 to 1, and so on. In particular, f(2)=f(1+1)=f(1)+f(1) = 2f(1)=2 since f(1)=1

[Johnny5]

 

Euclid's algorithm states that there is a constructive way to write the highest common factor of two integers' date=' a and b as an integral combination of them. That is to say

 

if d =hcf(a,b) then there are integers s and t such that as+bt=d.

[/quote']

 

Euclid didn't have negative integers though. Shouldn't you restrict the discussion to:

 

[math] \mathbb{Z}^+ [/math]

 

?

[Johnny5]

In the following post, I am going to do a few examples of Euclid's algorithm.

 

It appears in Book seven, as proposition 2.

 

Greatest Common Divisor

 

 

Let A' date='B be integers, not both zero.

 

A positive integer d is the [i']greatest common divisor [/i] of A,B provided:

 

d divides A AND d divides B AND (if c divides A and c divides B then c divides d)

 

Definition: If x and y are positive integers, x is a divisor of y, denoted x|y, if xq=y for some integer q.

[matt grime]

Why do you think that Euclid's algorithm must be something that Euclid defined? Just because it has his name attached means nothing: pythagoras didn't invent the pythagorean triples, Galois would have no idea about galois cohomology. If you insist on reading Elements as a modern text book in number theory, or Newton as a learning tool for vector spaces you're not going to get very far.

[Johnny5]

Why do you think that Euclid's algorithm must be something that Euclid defined? Just because it has his name attached means nothing: pythagoras didn't invent the pythagorean triples, Galois would have no idea about galois cohomology. If you insist on reading Elements as a modern text book in number theory, or Newton as a learning tool for vector spaces you're not going to get very far.

 

To be honest, it doesn't matter who invented it, whether or not it was Euclid in particular, is irrelevent to me. Although, what would matter, if knowable, was the year.

 

As for something he defined, no he didnt define it. The person who found it, deduced it. Actually, I am interested in the history of the "Euclidean algorithm" if you happen to know about it.

 

I think investigating the inventor of a mathematical idea is part of the process of understanding that idea, but that's just my opinion.

 

Oh and here is something for you...

 

Algorithm

 

[math] \alpha \lambda \gamma o \sigma = \text{painful}[/math]

 

[math] \alpha \rho \eta \theta \mu o \sigma = \text{calculation or number} [/math]

 

[math] \alpha \lambda \gamma o \rho \eta \theta \mu o \sigma = \text{painful calculation}[/math]

 

 

Regards

 

PS: What about my question on whether or not you should use Z+ as opposed to Z?

 

Now, I don't currently remember the algorithm, but I do remember it was very simple. And i know that it connects to the fundamental axiom of arithmetic, namely that any positive integer can be written as a product of prime numbers. And this all connects to greatest common multiple, and some other things.

 

I remember how to break a natural number down into the product of primes.

 

Take 486 for example.

 

First, factor out the lowest prime number, which is 2, as follows:

486=2*243

Stick with 2, until you cannot factor it out anymore. You cannot factor out 2 from 243, so move on to the next prime number, which is 3. Can you factor out 3 from 243? Here is a quick way to check... 2+4+3=9, and 9 is evenly divisible by 3, so yes. So factor out 3 from 243 as follows:

486=2*243=2*3*81

Stick with 3.

486=2*243=2*3*81=2*3*3*27

Stick with 3.

486=2*243=2*3*81=2*3*3*3*9

Stick with 3.

486=2*243=2*3*81=2*3*3*3*3*3

And the algorithm ends.

 

Now using the transitive property of equality, we have:

 

486=2*3*3*3*3*3

 

This is the one, and only way, to write 486 as a product of prime numbers.

[ydoaPs]

he probably messed up the [math]\LaTeX[/math] in that part of his post.

[matt grime]

Mess up the latex? Who?

 

Anyway, I am perfectly sure that the euclidean algorithm involves negative integers and I really don't understand why it's important: it's just showing that the integers are a PID, after all if x and y are (negative integers) (x,y)=(-x,-y)

 

Right, I tihnk my patience is up on this at the minute (vicious toothache) and don't really see why you'd invoke the "associativity of multiplication" (completely bleeding obvious) .

[Johnny5]

Mess up the latex? Who?

 

Anyway' date=' I am perfectly sure that the euclidean algorithm involves negative integers and I really don't understand why it's important: it's just showing that the integers are a PID, after all if x and y are (negative integers) (x,y)=(-x,-y)

 

Right, I tihnk my patience is up on this at the minute (vicious toothache) and don't really see why you'd invoke the "associativity of multiplication" (completely bleeding obvious) .[/quote']

 

 

Wolfram on PID

 

And also:

 

Wolfram on principle ideal domain

 

Sorry about the tootache Matt.

 

Regards

[matt grime]

http://mathworld.wolfram.com/EuclideanAlgorithm.html

 

uses Z....

[Johnny5]

Euclid's algorithm states that there is a constructive way to write the highest common factor of two integers' date=' a and b as an integral combination of them. That is to say

 

if d =hcf(a,b) then there are integers s and t such that as+bt=d.

 

[/quote']

 

Yes, if d is the highest common factor (greatest common factor) of two natural numbers(though you say integers) then there are integers s,t such that:

 

as+bt=d.

 

I don't understand why you have made the domain of discourse the integers, rather than the natural numbers. I will have to now check to see if Euclid's algorithm holds for the negative integers, as well as zero.

 

Regards

[Johnny5]

http://mathworld.wolfram.com/EuclideanAlgorithm.html

 

uses Z....

 

I see that they use Z, I also see a whole lot more.

[matt grime]

Domain of Discourse? Bugger, you're not a computer scientist are you?

 

If you understood what the highest common factor was (you posted something about it but seemed to miss the key things) then it'd be obvious that it makes sense to talk about the highset common factor of any pair of integers and that Eulcid's algorithm can be used to calculate it, and that the hcf of x and y is the same as the hcf of -x,y and y,-x and -y,-x.

 

 

I have no idea why you want to discuss the Euclidean algorithm at all to be honest.

[Dave]

This thread doesn't seem to have a lot to do with Linear Algebra any more, that's for sure.

[matt grime]

Did it ever?

[Johnny5]

Domain of Discourse? Bugger' date=' you're not a computer scientist are you?

 

If you understood what the highest common factor was (you posted something about it but seemed to miss the key things) then it'd be obvious that it makes sense to talk about the highset common factor of any pair of integers and that Eulcid's algorithm can be used to calculate it, and that the hcf of x and y is the same as the hcf of -x,y and y,-x and -y,-x.

 

 

I have no idea why you want to discuss the Euclidean algorithm at all to be honest.[/quote']

 

Yes I thought about this last night briefly actually, but I then I got busy reading star charts. I have some in my hands right now.

 

I am trying to learn how to read them as a matter of fact.

 

The one I am looking at right now, has polaris at the center. Ursa minor, and Ursa major are right there, near it.

 

But the interesting thing is, that there is a circle traced out, labelled

 

"orbit of precession of the pole... 4600 BC" It says... SC2 constellation chart, northern circumpolar region, epoch 1925.

 

So i got a bit sidetracked last night, as you can see.

 

But back to the greatest common factor...

 

Suppose we are given two natural numbers, at random, 242, 185, and we are asked to find their greatest common factor.

 

First write 242 as a product of primes.

 

242=2*121=2*11*11

 

Next write 185 as a product of primes.

 

185=5*37

 

In this example the GCF is 1.

 

As another example, suppose the numbers 24,288 are chosen at random. Find the GCF.

 

24=2*12=2*2*6=2*2*2*3

 

288=2*144=2*2*72=2*2*2*36=2*2*2*2*18=2*2*2*2*2*9=2*2*2*2*2*3*3

 

When you see an equation like that, I call it a superequation. As an example, it's a shorthand for the following compound statement:

 

(A=B and A=C and A=D and A=E and B=C and B=D and B=E and C=D and C=E and D=E)

 

In other words:

 

If A=B=C=D=E then (A=B and A=C and A=D and A=E and B=C and B=D and B=E and C=D and C=E and D=E), and conversely.

 

It's a way to shorten the amount of writing.

[matt grime]

Euclid's algorithm doesn't require you to know the prime factors of either of the numbers, and that is its beauty. Where are you going with this?

[Johnny5]

Euclid's algorithm doesn't require you to know the prime factors of either of the numbers, and that is its beauty. Where are you going with this?

 

Can you do an example for me Matt?

 

I give you the following two numbers:

 

 

468, 950

 

 

Demonstrate the algorithm please.

[Dave]

950 = 468 * 2 + 14: so gcd(950, 468) = gcd(468, 14)

468 = 14 * 33 + 6: gcd(468, 14) = gcd(14, 6)

14 = 2*6 + 2: gcd(14, 6) = gcd(6,2)

6 = 3*2 => gcd(6,2) = 2 => gcd(950, 468) = 2

[matt grime]

Can you do an example for me Matt?

I give you the following two numbers:

468' date=' 950

Demonstrate the algorithm please.[/quote']

 

 

Have you considered doing some work on your own rather than asking all these (off your own topic) questions and demanding things of others? The Euclidean algorithm is well known and I'm sure you can find many worked examples of it.

[Johnny5]

950 = 468 * 2 + 14: so gcd(950' date=' 468) = gcd(468, 14)

468 = 14 * 33 + 6: gcd(468, 14) = gcd(14, 6)

14 = 2*6 + 2: gcd(14, 6) = gcd(6,2)

6 = 3*2 => gcd(6,2) = 2 => gcd(950, 468) = 2[/quote']

 

Problem: Find the greatest common divisor of 950, 468, using the Euclidean algorithm.

 

In order to answer the question, one must first know the definition of greatest common divisor (also called greatest common factor).

 

Definition: The greatest common divisor of two natural numbers A,B, is the supremum of the set of all natural numbers which evenly divide both A,B.

 

Definition: The supremum, of a set of numbers, is the largest number in the set.

 

For example, the supremum of {498,58, 72, 1024, 5, 1001} is 1024.

 

So what does it mean to be the greatest common divisor of 66, 121?

 

First look at all the natural numbers which go in 66 evenly.

 

Well 1 goes into it 66 times.

2 goes into it 33 times.

3 goes into it 22 times.

4 goes into 66, 16 times, but with remainder 2; therefore 4 does not go into 66 evenly.

5 goes into 66, 13 times, but with remainder 1; therefore 5 does not go into 66 evenly.

6 goes into 66, 11 times, and there is no remainder; therefore 6 goes into 66 evenly.

7 goes into 66, 9 times, 7*9=63, so remainder 3, so 7 doesn't go into 66 evenly.

8 goes into 66, 8 times, 8*8=64, so remainder 2, so 8 doesn't go into 66 evenly.

9 goes into 66, 7 times, 9*7=63, so remainder 3, so 9 doesn't go into 66 evenly, but now we are repeating earlier results, because multiplication of two natural numbers, is commutative.

 

Let us summarize these results as follows:

1*66=66

2*33=66

3*22=66

4*16+2=66

5*13+1=66

6*11=66

7*9+3=66

8*8 +2=66

9*7+3=66

 

From the list above, select all the cases in which multiplication of two natural numbers was equal to 66 without remainder, and put the numbers into a set, you might as well list them in increasing size.

 

{1,2,3,6,11,13,22,33,66}

 

The set of natural numbers above, are all the natural numbers which are less than or equal to 66, which 66 can be evenly divided by. In other words, given any randomly chosen element n of the set above, you can find a natural number m, such that n*m=66.

 

Now, do the same thing that was done for 66, for the number 121.

 

1*121=121

2*60+1=121

3*40+1=121

4*30+1=121

5*24+1=121

6*20+1=121

7*17+2=121

8*15+1 =121

9*13+4 =121

10*12+1=121

11*11 = 121

 

There is no point in going any further, because we have found a perfect square.

 

Now, list all the natural numbers which go into 121 evenly:

 

{1,11,21}

 

and the other set was:

 

{1,2,3,6,11,13,22,33,66}

 

Now write the set of all common factors of 66, and 121:

 

{1,11}

 

Now choose the supremum of this set:

 

{11}

 

The element of the singleton set above is the greatest common factor of 66, and 121.

 

 

 

 

 

Solution: First determine how many times 468 goes into 950, without going over. The answer is twice.

 

468*2=800+120+16=920+16=936

 

The difference between 950, and 468*2 is 14. Therefore:

 

950 = 468*2+14

 

GCD(950,468)=GCD(468,14)

 

468 = 14*33+6

 

So GCD(950,468)=GCD(14,6)

 

14=6*2+2

 

So

 

GCD(950,468)=GCD(6,2)

 

6=2*3+0

 

GCD(950,468) = GCD(2,0)

 

 

All natural numbers divide into zero, zero times.

 

That is 0/n=0 for all [math] n \in \mathbb{N} [/math]

[matt grime]

"In order to answer the question, one must first know the definition of greatest common divisor (also called greatest common factor)."

 

No, one must not. I can get a computer to do Euclid's algorithm, and it does not know what the hcf/gcd is.

 

Knowing what something "is" is definitely good, but is absolutely of no interest in actually applying a simple algorithm.

 

 

What were you hoping to achieve with that post?

[Johnny5]

"In order to answer the question' date=' one must first know the definition of greatest common divisor (also called greatest common factor)."

 

No, one must not. I can get a computer to do Euclid's algorithm, and it does not know what the hcf/gcd is.

 

Knowing what something "is" is definitely good, but is absolutely of no interest in actually applying a simple algorithm.

 

 

What were you hoping to achieve with that post?[/quote']

 

Matt, can you show me exactly what you mean?

 

Run through the computer algorithm for me, and treat me like I am the computer.

[matt grime]

For pity's sake, have you still not found out what the Euclidean Algorithm is?

 

here, from your favourite wolfram:

 

http://mathworld.wolfram.com/EuclideanAlgorithm.html

 

or how about the search results from google for euclidean algorithm?

 

http://www.google.co.uk/search?hl=en&q=euclidean+algorithm&btnG=Google+Search&meta=

 

Do some thinking on your own!

[Johnny5]

For pity's sake' date=' have you still not found out what the Euclidean Algorithm is?

 

here, from your favourite wolfram:

 

http://mathworld.wolfram.com/EuclideanAlgorithm.html

 

or how about the search results from google for euclidean algorithm?

 

http://www.google.co.uk/search?hl=en&q=euclidean+algorithm&btnG=Google+Search&meta=

 

Do some thinking on your own![/quote']

 

 

Yes yes, ok.

 

 

Find GCF of 234, 2039, id est, find GCF(2039,234).

 

2039=234*8+167

 

[math] \therefore GCF(2039,234)=GCF(234,167) [/math]

 

234=167*1+67

 

[math] \therefore GCF(2039,234)=GCF(167,67) [/math]

 

167=67*2+33

 

[math] \therefore GCF(2039,234)=GCF(67,33) [/math]

 

67=33*2+1

 

[math] \therefore GCF(2039,234)=GCF(33,1) [/math]

 

33=1*33+0

 

[math] \therefore GCF(2039,234)=GCF(1,0) [/math]

 

1= 0*x +1

 

[math] \therefore GCF(2039,234)=GCF(0,1) [/math]

 

0 = 1*0 +0

 

[math] \therefore GCF(2039,234)=GCF(1,0) [/math]

 

And we are now in a loop.

 

But, the largest natural number which goes into 1 evenly is 1.

And 0/1=0

 

But, if 0 isn't a natural number then the algorithm should have ended.

 

Let me try another one, only this time I am not going to choose the numbers at random.

 

 

27*20=540

 

27*16=432

 

 

Find the greatest common divisor of 540,432.

 

That is, find GCF(540,432).

 

540=432*1+108

 

[math]

\therefore GCF(540,432)=GCF(432,108)

[/math]

 

432=108*4+0

 

[math]

\therefore GCF(540,432)=GCF(108,0)

[/math]

 

108=0*x+108

 

[math]

\therefore GCF(540,432)=GCF(0,108)

[/math]

 

0=108*0+0

 

[math]

\therefore GCF(540,432)=GCF(108,0)

[/math]

 

And we are now in a loop. GCF(540,432)=108

 

How can we check this?

 

The answer is by brute force. List out all the factors of 540, and all the factors of 432, and then find the largest number which is an element of both sets.

 

 

1*540=540

2*270=540

3*180=540

4*135=540

5*108=540

6*90=540

9*60=540

10*54=540

12*45=540

15*36=540

18*30=540

20*27=540

27*20=540

Going any further is pointless, because we can now list all the factors of 540.

 

{1,2,3,4,5,6,9,10,12,15,18,20,27,30,36,45,54,60,90,108,135,180,270,540}

 

We now list all the natural numbers which are factors of 432:

 

1*432=432

2*216=432

3*144=432

4*108=432

 

Definition: A divisibility test is a quick way to check to see if one number is divisible by another.

 

A quick way to check and see if a number is divisible by 5, is to check and see if the last digit contains a 0, or a 5. In the case of 432, the last digit is a 2, and hence 432 is not divisible by 5.

 

A quick way to check to see if 432 is divisible by 6, is to check and see if 432 is divisible by both the number 2, as well as the number three. If it is, then 432 is divisible by 6.

 

A quick way to check to see if 432 is divisible by 2, is to check and see if the last digit is a multiple of 2, i.e. an element of the set {0,2,4,6,8}. The last digit of 432 is 2, hence 342 is evenly divisible by 2.

 

A quick way to check to see if 432 is divisible by 3, is to add all the numbers, and see if the result is divisible by 3. 4+3+2=9. Nine is divisible by 3, since 3*3=9, 9/3=3. Therefore 432 is divisible by 3.

 

Thus, 432 is divisible by both 2, as well as 3. Therefore, 432 is divisible by 6.

 

Let us continue where we left off:

 

1*432=432

2*216=432

3*144=432

4*108=432

6*72=432

8*54=432

9*48=432

12*36=432

16*27=432

18*24=432

24*18=432

So the set of factors of 432 is given by

{1,2,3,4,6,8,9,12,16,18,24,27,36,48,54,72,108,144,216,432}

 

So now, lets list them out side by side.

 

A={1,2,3,4,5,6,9,10,12,15,18,20,27,30,36,45,54,60,90,108,135,180,270,540}

B={1,2,3,4,6,8,9,12,16,18,24,27,36,48,54,72,108,144,216,432}

 

A is the set of natural numbers which are factors of 540, and B is the set of natural numbers which are factors of 432.

 

The set of common factors is given by the set A intersect B.

 

[math] A \cap B = \mathcal{f} 1,2,3,4,6,9,12,18,27,36,54,108} \mathcal{g}[/math]

 

And the supremum (largest number) of the previous set, is the number 108. So 108 is the greatest common factor of 432,540; symbolically:

 

GCF(540,342) = 108.

 

And this does agree with what we got using Euclid's algorithm.

 

The point of this exercise was to show how much harder it is to find the GCF of two natural numbers using brute force, as opposed to using the Euclidean algorithm.

 

A secondary point, was to utilize the necessary vocabulary to discuss the algorithm intelligently.

[matt grime]

Johnny, try doing this for Numbers in the RSA range, where (probably a speeded u version of) Euclid's algorithm is useful.

 

 

Or you could for once attempt to explain what it is you're hoping to achieve.