# Number Theory Euclidean Algorithm

## 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.

Related Calculus and Beyond Homework Help News on Phys.org
jbunniii
Homework Helper
Gold Member
Do you know a relation between the gcd and linear combinations of u and v?

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
Homework Helper
Gold Member
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?

So then au divides n and vb divides n?

jbunniii