Why is gcd important in number theory?

In summary, the conversation discusses the importance of prime factorization and how it relates to concepts such as PID, gcd, Euclid's algorithm, modulo arithmetic, and number theory. The conversation also touches on the 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" and the use of Euclid's algorithm to prove it. It is also mentioned that d is the smallest positive element of the set S = {ax + by; x, y \in \mathbb{Z}} and that it is a divisor of both a and b. Finally, the conversation discusses the importance and beauty of coding in number theory.
  • #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.
 
Physics news on Phys.org
  • #2
it was me, right?

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.
 
  • #3
yup part of the foundations of numbertheory...coding it is a beauty.
 
  • #4
matt grime said:
it was me, right?
:smile: Right.
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 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 their gcd. What is the ideal generated by a and b? The union of the ideal generated by each?
 
  • #5
it is the set of all things of the form as+bt for s,t in Z.
 
  • #6
matt grime said:
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.
 
Last edited:
  • #7
it is easy to prove - try it. if you know eulcid's algorithm then it is straightforward.
 
  • #8
Okay, I'll look up Eulcid's algorithm and give it a try.
 
  • #9
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?
 
Last edited:
  • #10
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.
 
  • #11
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).
 
  • #12
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?
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)?
 
  • #13
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)
 
  • #14
Muzza said:
(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).
 
  • #15
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)
 
  • #16
matt 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)
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?
 
  • #17
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)
Oh, right. :redface:
 
  • #18
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?



no, no other factor is expressible in this form. as i proved. the hcf of a and b always divides as+bt.
 
  • #19
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.
Okay, yes, sorry, I get it, just took a little while. I'll be more careful about using variables consistently too. Thanks.
 
  • #20
I think you can look at this proof in 4 stages.

The first stage is trivial if you know the Euclidean Algorithm, it is just that hcf(a,b) = sa + tb for some integers s, t.

Next, you notice that S = {sa + tb: s, t in Z} is generated entirely by its least positive element. Suppose d is the least positive element, and c is in S and is positive, but d does not divide c. Then the division algorithm tells us that there is x such that 0 < x < d and some postive integer f such that c = df + x. But then x = c - df, which must be in S (you can easily check this), and x < d, contradicting our choice of d, so d really does divide all c in S.

Next is to notice that such d divides a and b. This follows directly from the previous "stage" since a and b are the combinations of the form 1a + 0b and 0a + 1b, so they're in S, and so d divides them. So d is a common factor of a and b.

It remains to show that d is the greatest common factor of a and b. The greatest common factor of two numbers has the property that it is divisible by all common factors of a and b. So we show that if x is a common factor of a and b, then it divides d. If x divides a and x divides b, then xc = a, xf = b. But then d = sa + tb = s(xc) + t(xf) = x(sc + tf), so x divides d, as required.
 
  • #21
Okay, I understand that one too. Thanks.
 
  • #22
I think you can prove the Euclidean Algorithm easily too. It can be proven as other recursive algorithms are proven: show that it works for a "base case", show that the general case leads to the base case, and that if it works at one stage of the process, then it works at the previous stage. If we want to find gcd(a,b), then the base case is when either a|b or b|a. In this case, we choose either a or b, and either choice is a "linear" combination of a and b. If neither a divides b nor b divides a, then without loss of generality, say a < b. Define c as b (mod a). So 0 < c < a, and b = ka + c for some natural k. Is gcd(c,a) equal to gcd(a,b)? Define x = gcd(c,a) and y = gcd(a,b). x divides every positive "linear" combination of c and a (that is, any number of the form sc + ta > 0 for integers s, t) since if xc' = c and xa' = a, then:

sc + ta = s(xc') + t(xa') = x(sc' + ta')

But a is obviously a linear combination of a and c, and since b = ka + c, b is also a linear combination of the two. So x divides a and b, hence x|y. y divides a and b, and since c = b - ka is a positive linear combination of b and a, y|c, so y divides both a and c, hence y|x. x|y and y|x give us x = y.

It remains to prove that the Euclidean Algorithm will eventually take us to a base case. Well we can see that if at one stage we are taking a and b as arguments with a < b, then at the next stage we're taking a and c = b (mod a) < a, so now we have two numbers less than or equal to a. You can see that this process keeps replacing the larger number of the pair with a new number that is smaller than the smaller of the original pair. This process can't go on forever; in the "worst" case, we will come down to something like a and 1, and of course this satisfies the base case conditions because 1|a, since 1 divides everything.

Unless I made a mistake in the above, you can prove this entire theorem from scratch.
 

1. What is gcd and why is it important in number theory?

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.

2. How is gcd used in solving mathematical problems?

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.

3. What are the applications of gcd in real life?

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.

4. How does gcd relate to prime numbers?

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.

5. Why is gcd important in algorithms and computer science?

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.

Similar threads

  • Linear and Abstract Algebra
Replies
8
Views
858
  • Linear and Abstract Algebra
Replies
2
Views
2K
  • Calculus and Beyond Homework Help
Replies
13
Views
682
  • Linear and Abstract Algebra
2
Replies
42
Views
3K
Replies
5
Views
1K
  • General Math
Replies
2
Views
2K
Replies
5
Views
314
  • Linear and Abstract Algebra
Replies
6
Views
3K
  • Linear and Abstract Algebra
Replies
11
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
27
Views
3K
Back
Top