- #1
honestrosewater
Gold Member
- 2,142
- 6
I saw someone say this in another thread. Why is it so important? My best guess is that it has something to do with prime factorization, but that's a pretty wild guess.
Right.matt grime said:it was me, right?
Okay, that sounds important.Z is a PID The ideal generated by a and b is the ideal generated by their gcd. sort of a fundamental result. hcf(a,b) is the least, strictly positive element of the set of all things of the form as+bt, s,t in Z, we get euclid's algorithm from thinking about gcds, we start thinking about modulo arithmetic units, coprime objects, groups, rings, ideals, inverses, this leads us on to is factorization always unique, what are primes really. it is just the starting block of number theory, along with the observation that there are a distinguished set of objects called primes.
Okay, that makes more sense. Do you know where I can find a proof of "hcf(a,b) is the least, strictly positive element of the set of all things of the form as+bt, s,t in Z" - does it have a common name I could look up? It sounds interesting.matt grime said:it is the set of all things of the form as+bt for s,t in Z.
For all a in Z, there exists some b and c in Z such that bc = a. (b = a and c = 1 gives me this quickly.)
So letting cx = a and cy = b, cxs + cyt = c(xs + yt), so any common factor c of a and b divides as + bt. And I know some c exists because it can just be 1.
And I know hcf(a, b) > 0, because 1 is always a common factor. But that's really all I have. Is it all correct?
When hcf(a, b) = as + bt = c(xs + yt), I know (xs + yt) is in Z, so c and (xs + yt) are both common factors of hcf(a, b) - and neither are 0. But I seriously can't see how to prove that any common factor of a and b is also a factor of hcf(a, b). How can I prove it?
matt grime said:what are a and b? not as i gave them
what is c and what are you doing with it?
What are you trying to prove?
I was using them as brand new variables. I need that result for the next step.For all a in Z, there exists some b and c in Z such that bc = a. (b = a and c = 1 gives me this quickly.)
I want to prove that any common factor of a and b is also a factor of as + bt. So, using the previous step, I let a = cx and b = cy, where c, x, and y are integers. c is a common factor of a and b. By substituting cx for a and cy for b, as + bt = cxs + cyt = c(xt + yt). So any common factor of a and b is also a factor of as + bt. Doesn't that work?So letting cx = a and cy = b, cxs + cyt = c(xs + yt), so any common factor c of a and b divides as + bt.
Okay, but how do you know that d = hcf(a, b)?by euclid's algorithm we know that d=as+bt for some choice of s and t, so all that remians is to show is that d is minimal. well, if c=as+bt for some s and t obviously d divides the RHS and hence c, thus c, if is positive must be greater than d. end of proof.
I'll have to read the rest again. I seriously can't see how to prove that any common factor of a and b is also a factor of hcf(a, b).Muzza said:(you can prove that by showing that if w divides a and b, then w divides d).
I meanmatt grime said:because i decl;ared d to be? or do you mean, how do i know that d can be expressed as an integral combination of a and b? welll, that is what euclid's algorithm proves for us automatically. and you used b for two different things. the first one ought to have been an x (which it becomes halfway through the prrof)
Okay, but is this not true for any other common factor of a and b? That is, if c is any common factor of a and b, does c = as + bt for some s and t?by euclid's algorithm we know that d=as+bt for some choice of s and t,
Oh, right.matt grime said:Euclid's sodding algorithm does it for you!
there are integers s and t such that hcf(a,b)=as+bt
and divisor of a and b divides the RHS (you proved this yourself!) and hence divdes hcf(a,b)
honestrosewater said:I mean
Okay, but is this not true for any other common factor of a and b? That is, if c is any common factor of a and b, does c = as + bt for some s and t?
Okay, yes, sorry, I get it, just took a little while. I'll be more careful about using variables consistently too. Thanks.matt grime said:no, no other factor is expressible in this form. as i proved. the hcf of a and b always divides as+bt.
GCD stands for Greatest Common Divisor and it is the largest positive integer that divides two or more numbers without leaving a remainder. In number theory, gcd is important because it helps us understand the relationship between numbers and identify common factors between them.
Gcd is used in solving various mathematical problems such as finding the lowest common denominator, simplifying fractions, and determining if two numbers are relatively prime. It is also used in cryptography, prime factorization, and modular arithmetic.
Gcd has many practical applications in daily life, such as in measuring time and distance. For example, we use the concept of gcd when converting between units of time (minutes and seconds) or units of distance (feet and inches). It is also used in music theory when determining the time signature of a piece of music.
Gcd is closely related to prime numbers as it can help us identify if two numbers are relatively prime, meaning they have no common factors other than 1. A pair of numbers is relatively prime if their gcd is 1. This property is essential in number theory and has applications in cryptography and number factorization.
Many algorithms in computer science and data structures rely on the concept of gcd for efficient computation. Gcd helps in finding the greatest common divisor of two numbers, which is crucial in data compression, encryption, and sorting algorithms. It is also used in determining the complexity of algorithms and analyzing their runtime.