Register to reply

Why is gcd important in number theory?

by honestrosewater
Tags: important, number, theory
Share this thread:
honestrosewater
#1
Jun20-05, 06:47 AM
PF Gold
honestrosewater's Avatar
P: 2,330
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.
Phys.Org News Partner Science news on Phys.org
Experts defend operational earthquake forecasting, counter critiques
EU urged to convert TV frequencies to mobile broadband
Sierra Nevada freshwater runoff could drop 26 percent by 2100
matt grime
#2
Jun20-05, 07:55 AM
Sci Advisor
HW Helper
P: 9,396
it was me, right?

Z is a PID The ideal generated by a and b is the ideal generated by thier 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.
neurocomp2003
#3
Jun20-05, 11:33 AM
P: 1,373
yup part of the foundations of numbertheory...coding it is a beauty.

honestrosewater
#4
Jun21-05, 03:12 AM
PF Gold
honestrosewater's Avatar
P: 2,330
Why is gcd important in number theory?

Quote Quote by matt grime
it was me, right?
Right.
Z is a PID The ideal generated by a and b is the ideal generated by thier 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 sounds important.
I just read a little about PIDs. An ideal in Z generated by a is just {a*z : z in Z}? I can't figure out what you mean by: The ideal generated by a and b is the ideal generated by thier gcd. What is the ideal generated by a and b? The union of the ideal generated by each?
matt grime
#5
Jun21-05, 03:51 AM
Sci Advisor
HW Helper
P: 9,396
it is the set of all things of the form as+bt for s,t in Z.
honestrosewater
#6
Jun21-05, 04:11 AM
PF Gold
honestrosewater's Avatar
P: 2,330
Quote Quote by matt grime
it is the set of all things of the form as+bt for s,t in Z.
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
#7
Jun21-05, 05:00 AM
Sci Advisor
HW Helper
P: 9,396
it is easy to prove - try it. if you know eulcid's algorithm then it is straightforward.
honestrosewater
#8
Jun21-05, 05:16 AM
PF Gold
honestrosewater's Avatar
P: 2,330
Okay, I'll look up Eulcid's algorithm and give it a try.
honestrosewater
#9
Jun21-05, 07:44 AM
PF Gold
honestrosewater's Avatar
P: 2,330
I don't see how to use it. I haven't really done anything in number theory- i.e. I have like no basic theorems. I've got:
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?
Am I going in the wrong direction?
matt grime
#10
Jun21-05, 07:57 AM
Sci Advisor
HW Helper
P: 9,396
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.)
what are a and b? not as i gave them

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.
what is c and what are you doing with it?

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?


what are you trying to prove?

the theorem i stated was if d is hcf(a,b) then d is the least positive element of the form as+bt for s and t integers.

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.
Muzza
#11
Jun21-05, 07:58 AM
P: 695
Let [tex]S = \{ax + by; x, y \in \mathbb{Z}\}[/tex]. Obviously S contains some positive (non-zero) elements, so there is a smallest positive element [tex]d \in S[/tex]. Let [tex]d = ax_0 + by_0[/tex].

Define [tex]P = \{kd; k \in \mathbb{Z}\}[/tex].

Obviously [tex]P \subseteq S[/tex].

To show [tex]S \subseteq P[/tex] you need the Euclidean algorithm. Suppose that [tex]ax_1 + by_1 = u \in S[/tex]. Write [tex]u = qd + r[/tex], with [tex]q, r[/tex] integers and [tex]0 \leq r < d[/tex]. Notice that [tex]r = qd - u \in S[/tex]. But we can't have [tex]0 < r[/tex], since then r would be a positive element in S, smaller than the smallest positive element in S! Thus r = 0 and [tex]u = qd \in P[/tex], so that [tex]S \subseteq P[/tex].

Now all you need to establish is that d is a divisor of both a and b (this follows from the equality of P and S), and that every other common divisor of a and b is smaller than d (you can prove that by showing that if w divides a and b, then w divides d).
honestrosewater
#12
Jun21-05, 09:24 AM
PF Gold
honestrosewater's Avatar
P: 2,330
Quote Quote by matt grime
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?
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 was using them as brand new variables. I need that result for the next step.
So letting cx = a and cy = b, cxs + cyt = c(xs + yt), so any common factor c of a and b divides as + bt.
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?
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.
Okay, but how do you know that d = hcf(a, b)?
matt grime
#13
Jun21-05, 09:28 AM
Sci Advisor
HW Helper
P: 9,396
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)
honestrosewater
#14
Jun21-05, 09:28 AM
PF Gold
honestrosewater's Avatar
P: 2,330
Quote Quote by Muzza
(you can prove that by showing that if w divides a and b, then w divides d).
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).
matt grime
#15
Jun21-05, 09:30 AM
Sci Advisor
HW Helper
P: 9,396
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
#16
Jun21-05, 09:33 AM
PF Gold
honestrosewater's Avatar
P: 2,330
Quote Quote by matt grime
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)
I mean
by euclid's algorithm we know that d=as+bt for some choice of s and t,
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?
honestrosewater
#17
Jun21-05, 09:34 AM
PF Gold
honestrosewater's Avatar
P: 2,330
Quote Quote by matt grime
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)
Oh, right.
matt grime
#18
Jun21-05, 09:43 AM
Sci Advisor
HW Helper
P: 9,396
Quote Quote by honestrosewater
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?


no, no other factor is expressible in this form. as i proved. the hcf of a and b always divides as+bt.


Register to reply

Related Discussions
Number Theory: Calculating mod large number Calculus & Beyond Homework 9
Measure theory and number theory? Linear & Abstract Algebra 18
Division theory..and Prime Number theory.. Linear & Abstract Algebra 3