PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: High Entry average rating: No information on entry rating
[parent] probability that two positive integers are relatively prime (Result)

The probability that two positive integers chosen randomly are relatively prime is $$ \frac{6}{\pi^{2}} = 0.60792710185\dots. $$

At first glance this ``naked'' result is beautiful, but no suitable definition is there: there isn't a probability space defined. Indeed, the word ``probability'' here is an abuse of language. So, now, let's write the mathematical statement.

For each $n\in\mathbb{Z}^+$ let $S_n$ be the set $\{1,2,\dots,n\}\times\{1,2,\dots,n\}$ and define $\Sigma_n$ to be the powerset of $S_n$ Define $\mu\colon\Sigma_n\to\mathbb{R}$ by $\mu(E)=|E|/|S_n|$ This makes $(S_n,\Sigma_n,\mu)$ into a probability space.

We wish to consider the event of some $(x,y)\in S_n$ also being in the set $A_n=\{(a,b)\in S_n\colon\gcd(a,b)=1\}$ The probability of this event is $$ P((x,y)\in A_n)=\int_{S_n} \chi_{A_n} \,d\mu=\frac{|A_n|}{|S_n|}. $$ Our statement is thus the following. For each $n\in\mathbb{Z}^+$ select random integers $x_n$ and $y_n$ with $1\le x_n, y_n\le n$ Then the limit $\lim_{n\to\infty}P((x_n,y_n)\in A_n)$ exists and $$ \lim_{n\to\infty}P((x_n,y_n)\in A_n)=\frac{6}{\pi^2}. $$ In other words, as $n$ gets large, the fraction of $|S_n|$ consisting of relatively prime pairs of positive integers tends to $6/\pi^2$

Bibliography

1
Challenging Mathematical Problems with Elementary Solutions, A.M. Yaglom and I.M. Yaglom, Vol. 1, Holden-Day, 1964. (See Problems 92 and 93)




Anyone with an account can edit this entry. Please help improve it!

"probability that two positive integers are relatively prime" is owned by mps. [ full author list (2) | owner history (2) ]
(view preamble | get metadata)

View style:

Keywords:  Divisibility, Probability, Pi

This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: fraction, limit, powerset, probability space, relatively prime, integers, positive

This is version 18 of probability that two positive integers are relatively prime, born on 2005-01-06, modified 2005-10-30.
Object id is 6625, canonical name is ProbabilityThatTwoPositiveIntegersAreRelativelyPrime.
Accessed 2584 times total.

Classification:
AMS MSC11A51 (Number theory :: Elementary number theory :: Factorization; primality)
 11A05 (Number theory :: Elementary number theory :: Multiplicative structure; Euclidean algorithm; greatest common divisors)
 11A41 (Number theory :: Elementary number theory :: Primes)

Pending Errata and Addenda
None.
[ View all 11 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)