Question

Suppose that GCD(a,b) = 1 and that a divides bc. Show that a must divide c without using the Fundamental Theorem of Arithmetic.

Answer 1

I have questions about all of the proofs that I've found. For example, this one:

Suppose a|c and b|c. Then c = am and c = bn.

Suppose that gcd(a,b) = 1. We may write it as a linear combination:

1 = ax + by

Observe that

1 = ax + by
c = acx + bcy
c = a(bn)x + b(am)y
c = ab(nx) + ab(my)
c = ab(nx + my).

Hence, ab|c.

Why does c = am and c = bn?

Answer 2

Never mind, stupid question.

Answer 3

its not a stupid question

Answer 4

I think I get it.

Answer 5

a|c and b|c

a|c means `c = am` for some m
b|c mean `c = bn` for some n

Answer 6

example :

3|12 means `12 = 3*4`, here m = 4
2|12 means `12 = 2*6`, here n = 6

Answer 7

That means that there is some integers for a and b which, when multiplied by a and b, will cause them to meet at a point c on the number line. That seems to be a given, but I'm trying to understand why.

Answer 8

thats possible only when gcd(a, b) = 1

Answer 9

for example :

a = 4, b = 6, c = 12

clearly 4|12 and 6|12
but 4*6 does not divide 12

Answer 10

Euclid's Lemma says that if a prime divides the product of two numbers, then it must divide at least one of those numbers. Going back to my original problem, nowhere do we know that either of the numbers are prime. We know that they're coprime, but one (or both?) of them could still be composite. Unless I'm missing something, Euclid's Lemma doesn't apply.

Answer 11

Your original problem as-it-is itself is called Euclid's Lemma

See http://prntscr.com/4j5i6u

Answer 12

On the last line of that proof, how can a | (acx + bcy) be recast as a|c?

Answer 13

Wait, never mind. That really was a stupid question, lol.

Answer 14

Thanks, I understand!