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

Pairwise coprime sets?

  1. Mar 6, 2010 #1
    Hi all,

    I am looking for examples of infinite pairwise coprime sets.

    A set P of integers is pairwise coprime iff, for every p and q in P with p ≠ q, we have gcd(p, q) = 1. Here gcd denotes the greatest common divisor.(Wikipedia)

    Also from wikipedia the following are some examples of infinite such sets:

    The set of all primes, {2, 3, 5, 7, 11, …} is of course pairwise coprime, as is the set of elements in Sylvester's sequence, and the set of all Fermat numbers(Wikipedia).

    However, the set of all primes is trivial and two broad of a set for my purpose, and the last two seem to be too restrective, in the sense that their terms get very big very fast, which is something i would not like to deal with.

    So, i guess what i am looking for is something in beetween. Also, i believe that a finite set of integers that is pairwise coprime would work, as long as it is a relatively large set.

    Also i am wondering, whether there are pairwise coprime sets of any desired lenght? That is, for any given k in Z, is it possible to find a pairwise coprime set P with exactly k elements in it?

    Thanks to all of you!
    Last edited: Mar 6, 2010
  2. jcsd
  3. Mar 6, 2010 #2
    The first k primes. Or any k distinct primes. Or partition n distinct primes into k disjoint nonempty subsets (n>=k) and take the product of each set. I don't know how else you'd do it.
  4. Mar 6, 2010 #3
    I figured this one out.
    What do you mean with 'take the product of each set' here? I am assuming cartesian product, but still, i don't see how that helps, since the resulting set would have pairs of primes(ordered pairs) rather than primes alone.
    Or am I missing something here?! :redface:
    Last edited: Mar 6, 2010
  5. Mar 7, 2010 #4
    I mean, for each set, take the product of all its elements. So if your sets were {2,5,11} and {13, 31} then your numbers would be 110 and 403.
  6. Mar 7, 2010 #5
    I think that Tinyboss has already given you the best advice: If you don't want sets that consist of individual primes, then create sets that consist of products of distinct primes. However, if you're looking for an algorithm to produce sets of pairwise coprime numbers, try this:

    Choose integers a and [itex]S_0[/itex] such that [itex]S_0[/itex] > a [itex]\geq[/itex] 1 and [itex]S_0[/itex] and a are relatively prime. Then define [itex]S_n[/itex] recursively by

    [tex]S_n = a + S_{n-1}(S_{n-1} - a)[/tex]

    Then a and the [itex]S_n[/itex] will be a sequence of pairwise coprime integers. For a = 2 and [itex]S_0[/itex] = 3, you get the Fermat numbers.

  7. Mar 7, 2010 #6
    I believe this is what i was looking for. I tried to construct various recurrence relations that would produce sequences of pairwise coprime integers, but yeah, this is good to know! Do you know whether this recursive relation has a specific name (how's it called), because it looks quite familiar, and i might have seen it before!

    Tanks to both of you!
  8. Mar 7, 2010 #7
    I found the relation on page 7 of Ribenboim's The Little Book of Bigger Primes. He says that it comes from the paper Infinite Coprime Sequences, Edwards, 1964, Math. Gazette 48, 416 - 422. No specific name, though.

  9. Mar 7, 2010 #8
    Thanks again, this is very helpful!:approve:
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook