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
Sorry for hijacking.
Linear combination is useful because you can factor things out. If and , then for any integers , you can factor out from . Let's call this fact C).
For B), the problem statement suggests proving that both sides divide each other. By C), and implies . So, using A), we have . Conversely, we need . Obviously, and . By C), this implies that because is a linear combination of and . So, again by A), .
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 and have the same set of common divisors (at least when 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 is a linear combination of and , one uses Euclid's algorithm for computing GCD. The algorithm repeatedly changes a pair into and applies C) or B). Each step preserves the set of common divisors of the pair. We stop when is reached. Why is 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 , i.e., a divisor of , and vice versa.
Am I missing something in this reasoning?
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:
Or:
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.
emarakov is no doubt on the right path. Just to clean it up a bit.
Problem: Let . Prove that
Proof: Since we konw that the linear Diophantine equation has a solution . Therefore, . But if it is clear that thus .
Problem: Define as in the last problem and prove that by proving they divide each other.
Proof: Since it is clear that . Therefore is a divisor of thus . Now note that by definition, and since and is an integer it is clear that . Thus, is a divisor of so . The conclusion follows.