info prev up next book cdrom email home

Relatively Prime

Two integers are relatively prime if they share no common factors (divisors) except 1. Using the notation $(m,n)$ to denote the Greatest Common Divisor, two integers $m$ and $n$ are relatively prime if $(m, n) = 1$. Relatively prime integers are sometimes also called Strangers or Coprime and are denoted $m\perp n$.

The probability that two Integers picked at random are relatively prime is $[\zeta(2)]^{-1}=6/\pi^2$, where $\zeta(z)$ is the Riemann Zeta Function. This result is related to the fact that the Greatest Common Divisor of $m$ and $n$, $(m,n)=k$, can be interpreted as the number of Lattice Points in the Plane which lie on the straight Line connecting the Vectors $(0,0)$ and $(m,n)$ (excluding $(m,n)$ itself). In fact, $6/\pi^2$ is the fractional number of Lattice Points Visible from the Origin (Castellanos 1988, pp. 155-156).

Given three Integers chosen at random, the probability that no common factor will divide them all is

\begin{displaymath}[\zeta(3)]^{-1}\approx 1.20206^{-1} \approx 0.831907,
\end{displaymath} (1)

where $\zeta(3)$ is Apéry's Constant. This generalizes to $k$ random integers (Schoenfeld 1976).

See also Divisor, Greatest Common Divisor, Visibility


Castellanos, D. ``The Ubiquitous Pi.'' Math. Mag. 61, 67-98, 1988.

Guy, R. K. Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 3-4, 1994.

Schoenfeld, L. ``Sharper Bounds for the Chebyshev Functions $\theta(x)$ and $\psi(x)$, II.'' Math. Comput. 30, 337-360, 1976.

© 1996-9 Eric W. Weisstein