#1
Let (gcd of any two integers is always greater than or equal to 1).
By definition, there are some integers such that and .
In other words, dx is a common divisor of and . Since (a,b) = d, then .
However, recall that . So,
i really like o_O's solution to this. but here is how i was thinking of proving it. being very unimaginative, i like to go by definitions a lot and leave the fancy stuff to geniuses like o_O
disclaimer (?): to avoid having to say, "for some integers..." or "where so and so are integers..." all the time (which you should do!) just assume that whenever i introduce a new variable it is an integer.
recall the properties of the gcd:
Definition: means that:
(1) and
(2) If there is such that and , then
also: ....this is pretty much equivalent to condition (1), we will use this a lot.
these are the properties we will use in answering both questions. i hope you are familiar with them. now lets get to it.
Proof:
Assume . then . dividing both sides by (note ) we get , so that 1 satisfies condition (1) above. now, to show it satisfies condition (2), assume there is some such that and . then and . plug these into the equation that satisfies condition (1), we find that . so that 1 satisfies condition (2), and we have
we will use the same plan of attack on this guy. we need to verify the two conditions for 1 in regards to both and .2) If and , prove that
Suppose and
for some u in Z
for some v in Z
Now, how do I say that (a,b) = 1 = (a,c) ?
Thanks for any help.
Proof:
Assume and . then we have:
...................(eq 1)
................(eq 2)
From (eq 1), ..............(eq 3), and .................(eq 4).
plugging in (eq 3) into (eq 2) and simplifying, we get: , so that 1 satisfies condition (1) in regards to (a,c)
plugging in (eq 4) into (eq 2) and simplifying, we get: , so that 1 satisfies condition (1) in regards to (a,b)
now, proving condition (2) for both of these is pretty much identical to the way i did it in the last question. i leave it to you.