Find the number of relatively prime numbers from $10$ to $100$

Question

Find the number of ordered pairs $(a,b)$ such that $10\le a,b\le100$ and $gcd(a,b) = 1$

My attempt:

It is clear that for any $a$ you need to start checking from $b = a+1$ wether the two numbers are relatively prime or not, to prevent repetitions. Any prime $p$ would have $100-p- \lfloor\frac{100}{p}\rfloor$ pairs in which it is present. How do I proceed after this?

Answer 1

THere are $91$ numbers between $10$ and $91$ inclusively. So there are $91^2$ ordered pairs.

There are $46$ even numbers. An ordered pair with $2$ even numbers can't be relatively prime. So we toss out those $46^2$ pairs. We now have $91^2 - 46^2$ ordered pairs.

There are $30$ multiples of $3$. And ordered pair with $2$ numbers divisible by $3$ can't be relatively prime so we toss those $30^2$ pairs. But we that is double tossing the multiples of $3$ that are even-- we've already tossed those. There are $16$ multiples of $6$ so we now have $91^2 - 46^2 - 30^2 + 16^2$.

These are the sets of ordered pairs $(a,b)$ where $a$ and $b$ are not both even, nor are they both multiples of three.

There $19$ multiples of $5$ or which $9$ are even, $6$ are multiples of $3$ and $3$ are multiples of $6$. We toss those out.

We now have $(91^2) - (46^2) - (30^2 - 16^2) - (19^2 - 9^2 - 6^2 + 3^2)$

On to the next prime; $7$. There are .... geeze let's se $100\div 7 = 14$ and subtract the one less than $10$... $13$ multiples of $7$. $7$ are multiples of $14=2*7$ and $4$ of them are multiples of $21=3*7$ and $2$ of them are multiples of $35=5*7$. But $2$ are multiples of $2*3*7=42$ and $1$ is $2*5*7=70$. Yet there are no multiples if $3*5*7$ nor $2*3*5*7$.

When we toss all the ordered pairs that are both multiples of $7$ we have.

$(91^2) - (46^2) - (30^2 - 16^2) - (19^2 - 9^2 - 6^2 + 3^2)-(13^2 - 7^2 -4^2 -2^2 + 2^2 + 1^2)$

Now that the primes are more than the square root of $100$ things will get. Easier.

There are $9$ multiples of $11$ but $4,3,1,1$ of them are multiples of $2,3,5,7$. $1$ of them is a multiple of $6$. So now we have:

$(91^2) - (46^2) - (30^2 - 16^2) - (19^2 - 9^2 - 6^2 + 3^2)-(13^2 - 7^2 -4^2 -2^2 + 2^2 + 1^2)- (9^2 - 4^2-3^2-1^2-1^2 + 1^2)$

There are $7$ multiples of thirteen $3,2,1,1$ of them are multiples of $2,3,5,7$ and $1$ of them is a multiple of $6$. So now we have:

$(91^2) - (46^2) - (30^2 - 16^2) - (19^2 - 9^2 - 6^2 + 3^2)-(13^2 - 7^2 -4^2 -2^2 + 2^2 + 1^2)- (9^2 - 4^2-3^2-1^2-1^2 + 1^2)-(7^2 - 3^2-2^2-1^2-1^2 + 1^2)$

There are $5$ multiples of $17$ and $2,1,1$ of them are multiples of $2,3,5$. So now we have:

$(91^2) - (46^2) - (30^2 - 16^2) - (19^2 - 9^2 - 6^2 + 3^2)-(13^2 - 7^2 -4^2 -2^2 + 2^2 + 1^2)- (9^2 - 4^2-3^2-1^2-1^2 + 1^2)-(7^2 - 3^2-2^2-1^2-1^2 + 1^2) - (5^2 - 2^2 - 1^2 -1^2)$

There are $5$ multiples of $19$ and $2,1,1$ of them are multiples of $2,3,5$ so now we have:

$(91^2) - (46^2) - (30^2 - 16^2) - (19^2 - 9^2 - 6^2 + 3^2)-(13^2 - 7^2 -4^2 -2^2 + 2^2 + 1^2)- (9^2 - 4^2-3^2-1^2-1^2 + 1^2)-(7^2 - 3^2-2^2-1^2-1^2 + 1^2) - (5^2 - 2^2 - 1^2 -1^2) - (5^2 - 2^2 - 1^2 -1^2)$

There are $4$ multiples of $23$ and $2$ and $1$ are multiples of $2$ and $3$. So :

$(91^2) - (46^2) - (30^2 - 16^2) - (19^2 - 9^2 - 6^2 + 3^2)-(13^2 - 7^2 -4^2 -2^2 + 2^2 + 1^2)- (9^2 - 4^2-3^2-1^2-1^2 + 1^2)-(7^2 - 3^2-2^2-1^2-1^2 + 1^2) - (5^2 - 2^2 - 1^2 -1^2) - (5^2 - 2^2 - 1^2 -1^2)-(4^2 - 2^2 - 1^2)$

There are $3$ multiples Of $29$ and one of them are mutiplse of $2$ and $3$ so:

$(91^2) - (46^2) - (30^2 - 16^2) - (19^2 - 9^2 - 6^2 + 3^2)-(13^2 - 7^2 -4^2 -2^2 + 2^2 + 1^2)- (9^2 - 4^2-3^2-1^2-1^2 + 1^2)-(7^2 - 3^2-2^2-1^2-1^2 + 1^2) - (5^2 - 2^2 - 1^2 -1^2) - (5^2 - 2^2 - 1^2 -1^2)-(4^2 - 2^2 - 1^2)-(3^2 - 2)$

The remaining primes are $31,37,41,43,47$ of which there are $2$ multiples of but one of them is a mulitiple of $2$. And $53,61,67,71,73,79,83,89,97$.

So we have

$(91^2) - (46^2) - (30^2 - 16^2) - (19^2 - 9^2 - 6^2 + 3^2)-(13^2 - 7^2 -4^2 -2^2 + 2^2 + 1^2)- (9^2 - 4^2-3^2-1^2-1^2 + 1^2)-(7^2 - 3^2-2^2-1^2-1^2 + 1^2) - (5^2 - 2^2 - 1^2 -1^2) - (5^2 - 2^2 - 1^2 -1^2)-(4^2 - 2^2 - 1^2)-(3^2 - 2)- 14$

Ordered pairs $(a,b)$ in which $a,$ and $b$ have no factors in common. But we want unordered pairs. And as we have no pairs $(a,a)$ we just divide this result in half.

Total number is $\frac {(91^2) - (46^2) - (30^2 - 16^2) - (19^2 - 9^2 - 6^2 + 3^2)-(13^2 - 7^2 -4^2 -2^2 + 2^2 + 1^2)- (9^2 - 4^2-3^2-1^2-1^2 + 1^2)-(7^2 - 3^2-2^2-1^2-1^2 + 1^2) - (5^2 - 2^2 - 1^2 -1^2) - (5^2 - 2^2 - 1^2 -1^2)-(4^2 - 2^2 - 1^2)-(3^2 - 2)- 14}2$

Answer 2

The number of $a$ with $1 \le a \le b$ and $\text{gcd}(a,b) = 1$ is $\varphi(b)$, where $\varphi$ is Euler's totient function. The partial sums of $\varphi$ form OEIS sequence A002088. In particular, $A002088(100) = 3044$. After adjusting for $a \ge 10$ (which is a bit messy), you'll want to multiply by $2$.