Proporción de fracciones irreducibles en $\frac{1}{n}, \frac{2}{n}, ... ,\frac{n}{n}$?

Question

Cuan pequeña la proporción de fracciones irreducibles si $1 < n < 10^6$?

Answer 1

Una fracción $\dfrac ab$ es irreducible si $\gcd (a,b)=1$. Por lo tanto $\dfrac rn; r\in\{1,2,...,n-1\}$ será irreducible iff $\gcd (r,n)=1$. Esto deja sólo $\phi(n)$ posibilidades de $r$ donde $\phi (n)$ es el de Euler totient función de $n$.

Así, la proporción de tales fracciones irreducibles por lo tanto es $\dfrac{\phi(n)}{n-1}$, teniendo en cuenta las fracciones de hasta $\dfrac {n-1}n$ $\dfrac nn$ siempre es reducible.

Answer 2

La proporción de la fracción es irreducible $$ \dfrac{\phi(n)}{n} = \prod_{p\mediados n} \left(1-\frac{1}{p}\right) $$

Así que la menor proporción se logra cuando $n$ es el producto de todos los números primos tales que $n<10^6$, $n$ es el más grande de primorial menos de $10^6$.

Esto explica Michael respuesta.

Answer 3

$2*3*5*7*11*13*17=510510$.
La proporción de fracciones irreducibles es $$\frac12\frac23\frac45\frac67\frac{10}{11}\frac{12}{13}\frac{16}{17}=\frac{92160}{510510}\approx 0.18$$