Math Is Fun Forum

Kazy

Member

Registered: 2006-01-24

Posts: 37

GCD Proofs Part 2

I need to prove:

a) Let a, b, c ∈ Z. Suppose that a | c and b | c and that gcd(a,b) = 1. Prove that ab | c.
b) prove that for every integer n, gcd(n, n+1) = 1

Both of these seem trivial and are obviously true, but other than saying "These are obviously true" I don't even know where to begin. It seems I have more trouble with proofs when I know their easy and true, then when i'm not sure if their true. Can anyone help?

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: GCD Proofs Part 2

Both of these seem trivial and are obviously true, but other than saying "These are obviously true"

Yet my professors seem to get away with doing that all the time...

a.

a | c, so c = ak.
b | c, so c = bl.
gcd(a, b) = 1, so 1 = an + bm.

We want to get c = abz.  So you got to play around with what you have.  I'll give you one more hint.  c = anc + bmc.  See if you can get it from there.

Oh, and this isn't really a hint, but more a reminder.  You must use everything you are given in a proof.  Otherwise, you wouldn't be given it.  The only thing I used so far is that 1 = an + bm.

b.

This one is easier than it seems.  Let a | n such that a is not 1.  Since a does not divide 1, but a divides n, a does not divide n + 1.  I proved that fact a few days ago in reply to one of your other questions.  Since this applies for all a's that aren't 1...

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."