0
$\begingroup$

I'm wondering if anyone knows of results counting or bounding the number of relatively prime pairs in two subsets of positive integers. In particular:

Given $A = \{a \in \mathbb{Z} | m_1 \leq a \leq m_2 \}$ and $B = \{b \in \mathbb{Z} | n_1 \leq b \leq n_2 \}$, is there a formula for or a bound on the size of the set $P = \{(a,b)|a \in A, b \in B,$ and $a$ and $b$ are relatively prime$\}$.

Thanks!

$\endgroup$
  • 1
    $\begingroup$ Are you familiar with the result that for fixed $m_1,n_1$, as $m_2,n_2$ tend to infinity the fraction of relatively prime pairs $(a,b)$ tends to $\frac{6}{\pi^2}$? $\endgroup$ – hardmath Aug 18 '14 at 18:23
  • $\begingroup$ Yes, hardmath, I've got that result. Thank you though. $\endgroup$ – user166293 Aug 18 '14 at 18:26
  • $\begingroup$ If there is some information about the intervals $[m_1,m_2]$ and $[n_1,n_2]$ that you suspect will inform the counts/estimates, you should provide that. Otherwise the count can be anything from no pairs to all pairs. $\endgroup$ – hardmath Aug 18 '14 at 18:32
  • $\begingroup$ You can't mean "all pairs" in quite the way you have stated - as soon as you have two numbers in each interval you have a pair of even numbers. Constructing "no pair" examples of any size will also be tricky. $\endgroup$ – Mark Bennet Aug 18 '14 at 18:46
  • 1
    $\begingroup$ Note that taking primes, we can look at $(2p,3qr,2s)(2q,3ps,2r)$ which have no coprime pairs, and then use modular arithmetic/ Chinese Remainder Theorem to create a set of triples having at least those prime factors. So with $p=11, q=5, r=13, s=7$ we get the triples $(5654, 5655, 5656)(14090, 14091, 14092)$. The method can be generalised to obtain rectangles as large as one wishes containing no coprime pairs. $\endgroup$ – Mark Bennet Aug 18 '14 at 21:23

Your Answer

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

Browse other questions tagged or ask your own question.