Number Theory Euclidean Algorithm

  • #1
MathSquareRoo
26
0

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.
 

Answers and Replies

  • #2
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,475
257
Do you know a relation between the gcd and linear combinations of u and v?
 
  • #3
MathSquareRoo
26
0
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.
 
  • #4
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,475
257
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?
 
  • #5
MathSquareRoo
26
0
So then au divides n and vb divides n?
 
  • #6
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,475
257
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.
 

Suggested for: Number Theory Euclidean Algorithm

  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
6
Views
647
Replies
7
Views
364
Replies
12
Views
347
Replies
7
Views
382
Replies
2
Views
306
Replies
2
Views
300
Replies
10
Views
2K
Replies
4
Views
148
  • Last Post
Replies
6
Views
824
Top