Number of reduced fractions with denominator d
Problem If n is the numerator and d the denominator of a fraction, that fraction is defined a reduced fraction if and only if GCD(n,d)==1. For example $\displaystyle\frac{5}{16}$ is a reduced fraction, while $\displaystyle\frac{5}{16}$ is not, as both 6 and 16 are divisible by 2, thus the fraction can be reduced to $\displaystyle\frac{3}{8}$. Now, if you consider a given number d, how many reduced fractions can be built using d as a denominator?...