# How many coprimes ?

#### Greens

The Euler totient function gives the count of coprimes less than some $n$, which can also mean the number of ordered pairs of the form $(n,k)$ for all the $k \leq n$ that are also coprime.

By summing the totient of every number up to 100 we get the number of ordered coprime pairs (including $(1,1)$)

$\displaystyle \sum_{n=1}^{100} \phi(n) = 3044$

Now, to count the reverse of each ordered pair, we multiply by $2$. We also have to subtract one from this since $(1,1)$ is counted for twice otherwise.

$\displaystyle 2 \left(\sum_{n=1}^{100} \phi(n)\right) -1 = 6087$

This Desmos graph is nice to work with, but I don't know who made it ( CoprimePairStuff )

• idontknow and Maschke

#### skipjack

Forum Staff
I checked my program against results for smaller intervals given here.

• Greens

#### Greens

I've checked the totient method as well and it also seems to hold for these smaller intervals.

Also, the number of coprime pairs less than $t$ can also be represented by

$\displaystyle p(t) = 2\sum_{n=1}^{t} \sum_{k=1}^{n} \text{gcd}(k,n) \cos{\left( \frac{2 \pi k}{n} \right)} -1$

which is the expansion of totient, so calculation is easier.

• idontknow

#### Maschke

6087 it is. I found my error.