1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number Theory Euclidean Algorithm

  1. Sep 30, 2012 #1
    1. The problem statement, all variables and given/known data

    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.

    2. Relevant 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.
     
  2. jcsd
  3. Sep 30, 2012 #2

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Do you know a relation between the gcd and linear combinations of u and v?
     
  4. Sep 30, 2012 #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.
     
  5. Sep 30, 2012 #4

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

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

    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?
     
  6. Sep 30, 2012 #5
    So then au divides n and vb divides n?
     
  7. Sep 30, 2012 #6

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Number Theory Euclidean Algorithm
  1. Euclidean algorithm (Replies: 4)

  2. Euclidean algorithm (Replies: 3)

Loading...