Thread: Proofs USING GCDs

1. 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

2. 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 $\displaystyle \gcd\!\left(m,n\right)=sm+tn$ for some $\displaystyle s,t\in\mathbb{Z}$. So if $\displaystyle c\mid m$ and $\displaystyle c\mid n$, then $\displaystyle c\mid \gcd\!\left(m,n\right)$ since $\displaystyle \gcd\!\left(m,n\right)$ is a linear combination of $\displaystyle m$ and $\displaystyle n$.

Does this make sense so far?

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

Does this make sense?

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

Does this make sense so far?

For B) use the fact that $\displaystyle \gcd\!\left(a,b\right)=sa+tb$ for some $\displaystyle 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

4. Sorry for hijacking.

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

For B), the problem statement suggests proving that both sides divide each other. By C), $\displaystyle c\mid m$ and $\displaystyle c\mid n$ implies $\displaystyle c\mid (n-qm)$. So, using A), we have $\displaystyle d\mid\gcd(m, n-qm)$. Conversely, we need $\displaystyle \gcd(m, n-qm)\mid d$. Obviously, $\displaystyle \gcd(m, n-qm)\mid m$ and $\displaystyle \gcd(m, n-qm)\mid (n-qm)$. By C), this implies that $\displaystyle \gcd(m, n-qm)\mid n$ because $\displaystyle n$ is a linear combination of $\displaystyle m$ and $\displaystyle n-qm$. So, again by A), $\displaystyle \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 $\displaystyle (n, m)$ and $\displaystyle (m, n - qm)$ have the same set of common divisors (at least when $\displaystyle 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 $\displaystyle \gcd(n,m)$ is a linear combination of $\displaystyle n$ and $\displaystyle m$, one uses Euclid's algorithm for computing GCD. The algorithm repeatedly changes a pair $\displaystyle (n, m)$ into $\displaystyle (m, n - qm)$ and applies C) or B). Each step preserves the set of common divisors of the pair. We stop when $\displaystyle (d, 0)$ is reached. Why is $\displaystyle 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 $\displaystyle (d, 0)$, i.e., a divisor of $\displaystyle d$, and vice versa.

Am I missing something in this reasoning?

5. Originally Posted by emakarov
Sorry for hijacking.

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

For B), the problem statement suggests proving that both sides divide each other. By C), $\displaystyle c\mid m$ and $\displaystyle c\mid n$ implies $\displaystyle c\mid (n-qm)$. So, using A), we have $\displaystyle d\mid\gcd(m, n-qm)$. Conversely, we need $\displaystyle \gcd(m, n-qm)\mid d$. Obviously, $\displaystyle \gcd(m, n-qm)\mid m$ and $\displaystyle \gcd(m, n-qm)\mid (n-qm)$. By C), this implies that $\displaystyle \gcd(m, n-qm)\mid n$ because $\displaystyle n$ is a linear combination of $\displaystyle m$ and $\displaystyle n-qm$. So, again by A), $\displaystyle \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 $\displaystyle (n, m)$ and $\displaystyle (m, n - qm)$ have the same set of common divisors (at least when $\displaystyle 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 $\displaystyle \gcd(n,m)$ is a linear combination of $\displaystyle n$ and $\displaystyle m$, one uses Euclid's algorithm for computing GCD. The algorithm repeatedly changes a pair $\displaystyle (n, m)$ into $\displaystyle (m, n - qm)$ and applies C) or B). Each step preserves the set of common divisors of the pair. We stop when $\displaystyle (d, 0)$ is reached. Why is $\displaystyle 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 $\displaystyle (d, 0)$, i.e., a divisor of $\displaystyle d$, and vice versa.

Am I missing something in this reasoning?
no, its good, but how would u put it in to "MATH" language

6. 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.

7. 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 $\displaystyle (m,n)=d$. Prove that $\displaystyle c|m,n\implies c|d$

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

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

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

8. Originally Posted by Drexel28
emarakov is no doubt on the right path. Just to clean it up a bit.

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

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

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

Proof: Since $\displaystyle d|m,n$ it is clear that $\displaystyle d|m\text{ and }d|n-qm$. Therefore $\displaystyle d$ is a divisor of $\displaystyle m\text{ and }n-qm$ thus $\displaystyle d|(m,n-qm)$. Now note that $\displaystyle (m,n-qm)|m$ by definition, and since $\displaystyle (m,n-qm)|qm$ and $\displaystyle n-qm$ is an integer it is clear that $\displaystyle (m,n-qm)|n$. Thus, $\displaystyle (m,n-qm)$ is a divisor of $\displaystyle m\text{ and }n$ so $\displaystyle (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