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!

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

Have something to add?