# Practical probability that the GCD of a set of large, random integers is 1?

In a recent post on Crypto.SE, I argued that the probability that at least one pair of really large, uniformly random integers ($>2^{100,000,000}$) from a set of size $k$ is coprime is

$$1-(1-6/\pi^2)^{\frac{k(k-1)}{2}}$$

In the comments the point was made that taking the GCD over all integers in the set should yield a strictly better probability than the pair-wise approach I used. As the probability in this case would be $1/\zeta(k)$ as per Wikipedia, my result is clearly wrong, especially considering that "my" probability approaches $1$ strictly faster for $k>2$.

Where's the flaw in my thought process and how can I correct it?

Here's my argumentation, so you don't have to follow the link to Crypto.SE.

The first thing to observe or assume is that the values of $r_i$ are random non-zero integers. Due to their large size (beyond $2^{100,000,000}$), I will model them as randomly distributed numbers. Next, we observe that we found the modulus, if for any pair of $r_i,r_j$, $\gcd(r_i,r_j)=1$ holds, i.e. if any pair is co-prime. As we modeled the integers randomly, this can be said with probability $6/\pi^2$ and obviously a pair is not co-prime with probability $1-6/\pi^2$. Now the question becomes, "what is the probability, that all pairs are not co-prime?" which is $(1-6/\pi^2)^{\frac{k(k-1)}{2}}$. From this we can obviously draw the conclusion that there's at least one co-prime pair among the $r_i$s with the following probability, which is also the probability that our guess $N'$ for $N$ is correct:

$$\Pr[N'=N]=1-(1-6/\pi^2)^{\frac{k(k-1)}{2}}$$

My intuition tells me that I can't take the number of pairs as exponent, because there are some cases I consider "unique" here that actually aren't.

You're treating this as ${k \choose 2} = k(k-1)/2$ independent events. But, they're not independent. Therefore, you can't just multiply the probabilities like that.
For instance, if we're told that $\gcd(r_1,r_2)=2$ and $\gcd(r_2,r_3)=2$, then the (conditional) probability of $\gcd(r_1,r_3)=1$ is not $6/\pi^2$; it is $0$.