Number Theory

Question What is the probability that two random positive integers are relatively prime?

Our first problem is to make sense out of this question. We want every integer to be chosen with equal probability, but then this probability would have to be zero, which is not very helpful.

We need to restrict the domain to a finite segment of the integers and then let the segment grow to infinity.

Example 0.1   $\Pr({\rm a~random~integer~is~divisible~by~}4) = \lim_{n\to\infty} \Pr(4{\,\mid\,}x \colon 1\leq x\leq n)=1/4$

Theorem 0.2 (Prime Number Theorem)   Let $\pi(x)$ be the number of primes $\leq x$. Then, $\pi(x)\sim x/\ln x$. (``$\sim$'' stands for asymptotic equality, see Handout.)

Example 0.3   $\Pr({\rm a~random~integer~is~a~prime}) = \lim_{n\to\infty} \pi(n)/n\sim \lim_{n\to\infty}1/\ln n = 0$.

Definition 0.4  

$$\zeta(s) = \sum_{n=1}^{\infty}\frac{1}{n^s}.$$

It is known that $\zeta(2) = \pi^2/6$ (Euler).

Definition 0.5   We say that the integers $a_1,\dots,a_k$ are relatively prime if $\mathop{\rm g.c.d.\,}\nolimits (a_1,\dots,a_k)=1$. (Note that this does not mean the $a_i$ are pairwise relatively prime; for instance, $6,10,15$ are relatively prime.)