So, I know that c=aq and c=br for some integers q and r. I also know and can prove that c is greater than or equal to d, thus c=dz + t for some integers z and t by Euclid's algorithm. We know that t is greater than or equal to zero and less than d. If we can show d|t, then we know t=0. From here, we have c=dz, thus d|c and by substitution, [a,b]|c and we're done.
The part I don't get is this. How do you show d|t? If I knew how to do this, I could do the rest of the problem.
Say,
.
Let,
And we can define a positive integer,
.
Let, be a common multiple of .
We need to show,
Note,*)
Where,
because it is a common multiple.
Thus, .
That means,
.
Thus,
Thus,
.
Not only it proves this, it answers your other question.
*)Using the fudamental property of greatest common divisors,
Okay, I follow your proof so far, and it all makes sense, but exactly how does it prove that if a|c and b|c, then lcm(a,b)|c? I'm sure the answer is pretty obvious, but I'm just having trouble seeing it.Not only it proves this, it answers your other question.
, where
Divide both sides by
But
This looks similar to the Chinese remainder theorem.
I just found out that I am not allowed to work with numbers like (a/b). I must only work in integers, and cannot express them as fractions. My teacher will only let me use the multiplication, addition, and subtraction operators. Your proofs are helpful, but I have no clue how to express them without using division. (Oh, divides | is okay. | is acceptable)