Proofs USING GCDs

**AwesomeDesiKid** · November 15th 2009, 10:44 AM

Let m and n be integers with n >= m > 0. Set d = Gcd(m, n).

A)Prove that if c|m and c|n, then c|d.

B)For any integer q, prove d = Gcd(m, n − qm) by proving each side divides the other.

its kinda obvious that they are true and work
but don't know how to proove them

**Chris L T521** · November 15th 2009, 10:52 AM

Originally Posted by AwesomeDesiKid

Let m and n be integers with n >= m > 0. Set d = Gcd(m, n).

A)Prove that if c|m and c|n, then c|d.

B)For any integer q, prove d = Gcd(m, n − qm) by proving each side divides the other.

its kinda obvious that they are true and work
but don't know how to proove them

For A), note that $\gcd\!\left(m,n\right)=sm+tn$ for some $s,t\in\mathbb{Z}$ . So if $c\mid m$ and $c\mid n$ , then $c\mid \gcd\!\left(m,n\right)$ since $\gcd\!\left(m,n\right)$ is a linear combination of $m$ and $n$ .

Does this make sense so far?

For B) use the fact that $\gcd\!\left(a,b\right)=sa+tb$ for some $s,t\in\mathbb{Z}$ to show the desired result (I leave it for you to figure this part out).

Does this make sense?

**AwesomeDesiKid** · November 15th 2009, 11:02 AM

Originally Posted by Chris L T521

For A), note that $\gcd\!\left(m,n\right)=sm+tn$ for some $s,t\in\mathbb{Z}$ . So if $c\mid m$ and $c\mid n$ , then $c\mid \gcd\!\left(m,n\right)$ since $\gcd\!\left(m,n\right)$ is a linear combination of $m$ and $n$ .

Does this make sense so far?

For B) use the fact that $\gcd\!\left(a,b\right)=sa+tb$ for some $s,t\in\mathbb{Z}$ to show the desired result (I leave it for you to figure this part out).

Does this make sense?

Can you break/explain it little bit in details
like why do u do that, so if i see that kinda problem in future i would know how to pick it up
THANKS

**emakarov** · November 15th 2009, 04:09 PM

Sorry for hijacking.

Linear combination is useful because you can factor things out. If $c\mid m$ and $c\mid n$ , then for any integers $s, t$ , you can factor out $c$ from $sm + tn$ . Let's call this fact C).

For B), the problem statement suggests proving that both sides divide each other. By C), $c\mid m$ and $c\mid n$ implies $c\mid (n-qm)$ . So, using A), we have $d\mid\gcd(m, n-qm)$ . Conversely, we need $\gcd(m, n-qm)\mid d$ . Obviously, $\gcd(m, n-qm)\mid m$ and $\gcd(m, n-qm)\mid (n-qm)$ . By C), this implies that $\gcd(m, n-qm)\mid n$ because $n$ is a linear combination of $m$ and $n-qm$ . So, again by A), $\gcd(m, n-qm)\mid d$ .

Feel free to ignore the rest; I am writing sort of to recall these things for myself.

I prefer proving B) first and then A). B) is easy: by C), the pairs $(n, m)$ and $(m, n - qm)$ have the same set of common divisors (at least when $n - qm \ge 0$ to avoid possible problems with the definition of divisors of negative numbers). Therefore, the greatest of those divisors is the same.

To show A), as well as the fact that $\gcd(n,m)$ is a linear combination of $n$ and $m$ , one uses Euclid's algorithm for computing GCD. The algorithm repeatedly changes a pair $(n, m)$ into $(m, n - qm)$ and applies C) or B). Each step preserves the set of common divisors of the pair. We stop when $(d, 0)$ is reached. Why is $d$ the GCD of the original numbers? Because by the described preservation, every common divisor of the original numbers, including the GCD, is a common divisor of $(d, 0)$ , i.e., a divisor of $d$ , and vice versa.

Am I missing something in this reasoning?

**AwesomeDesiKid** · November 17th 2009, 08:25 AM

Originally Posted by emakarov

Sorry for hijacking.

Linear combination is useful because you can factor things out. If $c\mid m$ and $c\mid n$ , then for any integers $s, t$ , you can factor out $c$ from $sm + tn$ . Let's call this fact C).

For B), the problem statement suggests proving that both sides divide each other. By C), $c\mid m$ and $c\mid n$ implies $c\mid (n-qm)$ . So, using A), we have $d\mid\gcd(m, n-qm)$ . Conversely, we need $\gcd(m, n-qm)\mid d$ . Obviously, $\gcd(m, n-qm)\mid m$ and $\gcd(m, n-qm)\mid (n-qm)$ . By C), this implies that $\gcd(m, n-qm)\mid n$ because $n$ is a linear combination of $m$ and $n-qm$ . So, again by A), $\gcd(m, n-qm)\mid d$ .

Feel free to ignore the rest; I am writing sort of to recall these things for myself.

I prefer proving B) first and then A). B) is easy: by C), the pairs $(n, m)$ and $(m, n - qm)$ have the same set of common divisors (at least when $n - qm \ge 0$ to avoid possible problems with the definition of divisors of negative numbers). Therefore, the greatest of those divisors is the same.

To show A), as well as the fact that $\gcd(n,m)$ is a linear combination of $n$ and $m$ , one uses Euclid's algorithm for computing GCD. The algorithm repeatedly changes a pair $(n, m)$ into $(m, n - qm)$ and applies C) or B). Each step preserves the set of common divisors of the pair. We stop when $(d, 0)$ is reached. Why is $d$ the GCD of the original numbers? Because by the described preservation, every common divisor of the original numbers, including the GCD, is a common divisor of $(d, 0)$ , i.e., a divisor of $d$ , and vice versa.

Am I missing something in this reasoning?

no, its good, but how would u put it in to "MATH" language

**emakarov** · November 17th 2009, 08:47 AM

It is already in the math language if by this you mean the style that combines text and formulas and is used, say, in math textbooks. It is possible to write this using symbols only, without words, but it won't be easier to understand.

If you need more details and smaller steps from one statement to the next, could you post the exact place which you understand? For example:

You write:

Obviously,

I don't understand why this the case.

Or:

You write:

By C), this implies that

I cannot figure out how to use C) to derive

from the previous statement.

If, on the other hand, the whole text does not make sense, then you probably need to go back to definitions, examples and simple exercises to build some intuition about these things.

**Drexel28** · November 17th 2009, 03:14 PM

Originally Posted by AwesomeDesiKid

Let m and n be integers with n >= m > 0. Set d = Gcd(m, n).

A)Prove that if c|m and c|n, then c|d.

B)For any integer q, prove d = Gcd(m, n − qm) by proving each side divides the other.

its kinda obvious that they are true and work
but don't know how to proove them

emarakov is no doubt on the right path. Just to clean it up a bit.

Problem: Let $(m,n)=d$ . Prove that $c|m,n\implies c|d$

Proof: Since $(m,n)=d$ we konw that the linear Diophantine equation $mx+ny=d$ has a solution $(x_0,y_0)\in\mathbb{Z}^2$ . Therefore, $mx_0+ny_0=d$ . But if $c|m,n$ it is clear that $c|mx_0,ny_0$ thus $c|mx_0+ny_0=d$ .

Problem: Define $m,n,d$ as in the last problem and prove that $d=(m,n-qm)$ by proving they divide each other.

Proof: Since $d|m,n$ it is clear that $d|m\text{ and }d|n-qm$ . Therefore $d$ is a divisor of $m\text{ and }n-qm$ thus $d|(m,n-qm)$ . Now note that $(m,n-qm)|m$ by definition, and since $(m,n-qm)|qm$ and $n-qm$ is an integer it is clear that $(m,n-qm)|n$ . Thus, $(m,n-qm)$ is a divisor of $m\text{ and }n$ so $(m,n-qm)|d$ . The conclusion follows.

**AwesomeDesiKid** · November 17th 2009, 08:35 PM

Originally Posted by Drexel28

emarakov is no doubt on the right path. Just to clean it up a bit.

Problem: Let $(m,n)=d$ . Prove that $c|m,n\implies c|d$

Proof: Since $(m,n)=d$ we konw that the linear Diophantine equation $mx+ny=d$ has a solution $(x_0,y_0)\in\mathbb{Z}^2$ . Therefore, $mx_0+ny_0=d$ . But if $c|m,n$ it is clear that $c|mx_0,ny_0$ thus $c|mx_0+ny_0=d$ .

Problem: Define $m,n,d$ as in the last problem and prove that $d=(m,n-qm)$ by proving they divide each other.

Proof: Since $d|m,n$ it is clear that $d|m\text{ and }d|n-qm$ . Therefore $d$ is a divisor of $m\text{ and }n-qm$ thus $d|(m,n-qm)$ . Now note that $(m,n-qm)|m$ by definition, and since $(m,n-qm)|qm$ and $n-qm$ is an integer it is clear that $(m,n-qm)|n$ . Thus, $(m,n-qm)$ is a divisor of $m\text{ and }n$ so $(m,n-qm)|d$ . The conclusion follows.

thank you so much, this is sooooo much more clear
not that emarakov wan't big help, but this one i can see soo clearly
thanks again

Thread: Proofs USING GCDs

LinkBack

Thread Tools

Display

Proofs USING GCDs

Similar Math Help Forum Discussions

GCDs and LCMs

On GCDs and power's of 2

GCDs of polynomials

gcds

Sequence Convergence Proofs vs. Continuity Function Proofs

Search Tags