Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Coprime Sequence

  1. Aug 20, 2006 #1
    Let q_1=3, q_{n+1}=q_1...q_{n}-1. How do I show that any two elements of this sequence are coprime?
     
  2. jcsd
  3. Aug 20, 2006 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    I can't actually think of a way of helping you without giving the answer. Let me try it this way: given q_i and q_j with i<j it is rather clear that there is an integer combination of them that is 1, that is there are integeres a and b with aq_i +bq_j =1 (and hence they are coprime). You have acutally written these integers a and b out explicitly in your own post.
     
  4. Aug 20, 2006 #3
    Ah of course! I had forgotten about the converse of that theorem.
     
  5. Aug 20, 2006 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    But it is even easier than that: if i<j and some prime divides q_i it cannot divide q_j, and vice versa. It all follows from just reducing that expression you gave mod any prime: if p a prime divides any q_i it cannot divide any other q_j.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook