• Support PF! Buy your school textbooks, materials and every day products Here!

Number Theory Euclidean Algorithm

  • #1

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

Related Threads on Number Theory Euclidean Algorithm

  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
6
Views
321
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
0
Views
1K
Replies
2
Views
592
Replies
10
Views
1K
Replies
5
Views
1K
Replies
0
Views
3K
Top