Number of Irreducible Fractions

Number Theory Level 4

Find the number of distinct fractions $\dfrac{a}{b}$ , where both $a$ and $b$ are integers with $0\leq a \leq b \leq 50$ and $\gcd(a,b)=1$ .

Note: It's acceptable if $\dfrac{a}{b}$ equals some integer.

Notation: $\gcd(\cdot)$ denotes the greatest common divisor function.

The answer is 775.

1 solution

Maria Kozlowska
Jan 25, 2017

Euler totient function can be used here. For every $b$ , totient function will give us number of coprime $a$ 's. For $a=0, b=1$ we need to add 1 to the result.

$\sum_{b=1}^{50} \phi(b) +1 = 774+1=\boxed{775}$

Can we compute this stuff fast? Without a calculator?

William Nathanael Supriadi - 4 years ago

Dang, I didn't think about adding 1 to solution, so I answered 774 and got it wrong.

Kok Hao - 4 years ago

Number of Irreducible Fractions

The answer is 775.

1 solution

0 pending reports