Number Theory Euclidean Algorithm

[MathSquareRoo]

Homework Statement

Suppose that u, v ∈ Z and (u,v) = 1. If u | n and v | n, show that uv | n. Show that this is false if (u,v) ≠ 1.

Homework Equations

a | b if b=ac

3. The Attempt at a Solution

I understand this putting in numbers for u,v, and n but I don't know how to formally write it.

 

[jbunniii]

Do you know a relation between the gcd and linear combinations of u and v?

 

[MathSquareRoo]

Linear combination of u and v are equal to the gcd correct? And the gcd divides u and v I believe. I need help organizing all these ideas.

 

[jbunniii]

Linear combination of u and v are equal to the gcd correct?

Not necessarily true for an arbitrary linear combination, but there exists at least one linear combination equal to the gcd.

And the gcd divides u and v I believe.

Certainly, gcd means greatest common divisor, so it's certainly a divisor.

OK, if we let d = the gcd, then you know there is a linear combination such that d = au + bv. Now you know that u divides n and v divides n, so how can you use that fact here?

 

[MathSquareRoo]

So then au divides n and vb divides n?

 

[jbunniii]

So then au divides n and vb divides n?

No, that isn't necessarily true. However, if u divides n, then n = ur for some integer r. And v divides n, so n = vs for some integer s. Now try using these facts.