Pairwise coprime sets?

sutupidmath

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!

Tinyboss

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.

sutupidmath

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?!

Tinyboss

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.

Petek

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.

Petek

sutupidmath

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!

Petek

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.

Petek

sutupidmath

Thanks again, this is very helpful!