4
$\begingroup$

If we pick any two positive integers at random, what is the probability that their greatest common factor is 2? I have been wondering about this problem for a while and done some work on it. I started by thinking of a reasonable upper or lower bound. My upper bound was simply $.25$ as that is the probability of picking two even numbers (i.e. having a factor of 2) but if I was to pick (8,12) their gcf is 4. Then I thought about subtracting off the probability that the two numbers chosen had a common factor of 4 and then doing that for 6, 8, 10 and so on which got me to the sum of $1/4 -1/16 - 1/36 - 1/64 -...$ $= 1/2 - \frac{\pi^2}{24}$ I did some experimentation on smaller cases and I do not think my work was right, it should be closer to about $.158$ Also I think my method removed too much like when I subtracted off numbers that had 4 as a factor and numbers that had 6 as a factor I subtracted 12 twice. What should I do to adjust my work or get back on track? I was considering inclusion-exclusion but that seems too complicated for this problem. Thank you for any help

$\endgroup$
  • 1
    $\begingroup$ I think this is a great question, but it may not have a well-defined answer since there is no uniform probability distribution on the integers. In other words, you need some notion of how to pick a random integer to make the question precise. One possibility is to ask the question for the first N integers and then see if a limit exists as $N\to\infty$. $\endgroup$ – Cheerful Parsnip Jul 17 at 3:47
  • $\begingroup$ That would make sense. The question does not explicitly say that each integer has equal probability. I sense that there will be a connection to the problem of "What is the probability that 2 integers are co-prime?" which is actually $\frac{6}{\pi^2}$ $\endgroup$ – Moseph Jul 17 at 3:51
5
$\begingroup$

In this question it is shown that the probability two integers are coprime is $\frac 6{\pi^2}$ in the sense that you choose the integers between $1$ and $N$ uniformly, then take the limit as $N \to \infty$. For the $\gcd$ to be $2$, you need both integers to be even, then the numbers that are half of each of them to be coprime. The chance is then $\frac 14 \cdot \frac 6{\pi^2}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.