# Proofs USING GCDs

• Nov 15th 2009, 10:44 AM
AwesomeDesiKid
Proofs USING GCDs
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
• Nov 15th 2009, 10:52 AM
Chris L T521
Quote:

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?
• Nov 15th 2009, 11:02 AM
AwesomeDesiKid
Quote:

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
• Nov 15th 2009, 04:09 PM
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?
• Nov 17th 2009, 08:25 AM
AwesomeDesiKid
Quote:

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
• Nov 17th 2009, 08:47 AM
emakarov
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:
Quote:

You write:
Quote:
I don't understand why this the case.
Or:
Quote:

You write:I cannot figure out how to use C) to derive http://www.mathhelpforum.com/math-he...a08101c7-1.gif 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.
• Nov 17th 2009, 03:14 PM
Drexel28
Quote:

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.
• Nov 17th 2009, 08:35 PM
AwesomeDesiKid
Quote:

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