Number of pairs $(a, b)$ with $gcd(a, b) = 1$ Given $n\geq1$, how can I count the number of pairs $(a,b)$, $0\leq a,b \leq n$ such that $gcd(a,b)=1$?
I think the answer is $2\sum_{i}^{n}\phi(i)$. Am I right?
 A: Easy. From the points in $G=\{(x,y)|1\leq x,y\leq n\}\cap\mathbb{Z}^2$, take away all points $Q\in G$ for which another, distinct (smaller) point $P\in G$ lies on the line segment $\overline{OP}$ between $P$ and the origin $O(0,0)$. Call the set of remaining poins $H$. There is thus one point $(1,1)\in H$ on the line $y=x$, the same number of points above and below $y=x$, and one point on each axis (thank you @pedja!). This will give us $3+2f(n)$ points for some function $f$ of $n$:
$$
f(n)=\#\left\{\frac{a}{b} : 0<a<b\leq n\right\}=\sum_{b=2}^n\phi(b),
$$
since there are $\phi(b)$ choices for $1\leq a<b$.
Hence
$$
\#H
 = 3+2\sum_{k=2}^n\phi(k)
 = 1+2\sum_{k=1}^n\phi(k).
$$
Also, since $\sum_{0<d|n}d=n$ and $\phi(k)<k$ for $k>1$,
we can (very roughly) say that $1+2n<\#H<1+n^2$ for $n>2$.
A: The answer is in fact quite interesting. Let's define the function $p(n)$ to be the number of pairs you ask for. It is not hard to see that
$$p(n) = n^2 - \sum_{k=2}^{n} p(\lfloor n/k \rfloor)$$
Quick explanation. You count all pairs as $n^2$but you over counted. You take out all pairs $(k*a', k*b')$ for all $k \geq 2$ and $\gcd(a', b') = 1$, which is precisely the sum over $p(\lfloor n/k \rfloor)$.
We notice that $p(n) = p(\lfloor n/1\rfloor)$, therefore we can rewrite the equation as
$$n^2 = \sum_{k=1}^{n} p(\lfloor n/k \rfloor)$$ (notice how the sum starts from 1 now).
We then apply the Möbius inversion formula. We get
$$p(n) = \sum_{k=1}^{n}\mu(k)\lfloor n/k \rfloor^2$$
where $\mu(n)$ is the Möbius function.
On a more computational note, $\mu(n)$ can be computed in $O(\sqrt n)$. Also, the sequence $(\mu(1), ..., \mu(n))$ can be computed in O(n). Sample implementations are here.
NOTES:


*

*This was all explained to me in this thread a few years ago.

*As noted in other (deleted) answers $-1 + 2*\sum_{k=1}^{n} \phi(k)$ would probably work too. You count all pairs $(a, b)$ where $a < b$ by summing over all b $\phi(b)$, then multiplying by 2 and noticing that $(1, 1)$ was counted twice. I can't see however how this would lead to an efficient algorithm.. On second thought, this can be done using a modification of the Sieve of Eratosthenes. See this.

*The approach above extends to any k-tuple. You replace the power of 2 by k.

A: you are looking for Euler's totient function:
http://en.wikipedia.org/wiki/Euler%27s_totient_function
A: Definition :
$\phi(n) ~$ is the number of integers $k$ in the range $1 ≤ k ≤ n$ for which $\gcd(n, k) = 1$
Let's denote number of pairs $(a,b)$ as $N$ then :
$N= 2\cdot\displaystyle \sum_{i=1}^{n} \phi(i)+1 $
This is because you have to add pairs $(0,1) ~~\text {and}~~ (1,0)~~\text {and}~~ $pair $(1,1)$ can be included only once time .
A: Perhaps it could be mentioned that if we consider the probability $P_{n}$ that two randomly chosen integers in $\{1, 2, \dots, n \}$ are coprime
$$
P_{n} = \frac{\lvert \{(a, b) : 1 \le a, b \le n, \gcd(a,b) =1 \}\rvert}{n^{2}},
$$
then
$$
\lim_{n \to \infty} P_{n} = \frac{6}{\pi^{2}}.
$$
See this Wikipedia article.
