Estoy leyendo mi número de la teoría del libro de texto y los estados sin la prueba de que el número total de elementos relativamente primer a $p^2$ para algunos prime $p$$p(p-1)$. ¿Por qué es esto así? Sé que el número de primos relativos de los elementos de a $p$ siempre $p-1$.
Respuestas
¿Demasiados anuncios?
Todos los enteros positivos no relativamente primer a $p^2$ menos que o igual a $p^2$ son de la forma $pv$ donde $v\leq p$. Hay $p$ opciones para $v$; $v=1,2,3...p$, lo de las $p^2$ enteros positivos menores o iguales a $p^2$, $p$ no son relativamente primos. Luego hay $p^2-p$ números de menos de o igual a $p^2$ y relativamente primer a $p^2$.
EDIT: En general, $\phi(p^n)=p^n-p^{n-1}$ con similar razonamiento.
Mr. Brooks
Puntos
639
Vamos a decir $p$ es una extraña prime.
Usted ya sabe esto, pero hagamos un repaso: de$1$$p$, el único número $n$ tal que $\gcd(n, p) > 1$$n = p$; esto es debido a que $p$ es primo y no divisible por cualquier número de$2$$p - 1$. De$p + 1$$2p$, el único número $n$ tal que $\gcd(n, p) > 1$$n = 2p$. Y así sucesivamente y así sucesivamente a$(p - 1)p + 1$$p^2$.
Lo que hemos hecho aquí es tomar $p$ juegos de $p$ enteros consecutivos, y hemos encontrado que en cada uno de estos grupos sólo uno entero $n$ satisface $\gcd(n, p) > 1$, lo que significa que $p - 1$ enteros en el conjunto de los números enteros consecutivos son coprime a $p$. Desde allí se $p$ juegos de $p$ números enteros consecutivos, que significa $(p - 1)p$ enteros de los números enteros de $1$ $p^2$son coprime a$p$$p^2$, al igual que su libro afirmó.
tatan
Puntos
1609
Sugerencia:-
El número de números primos menores que y relativamente primos de un número $x$ está representado por el Phi de Euler función-$\phi(x)=x(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_n})$ donde $p_1,p_2,...,p_n$ son los principales factores (distintos) de $x$.
Ahora, ¿qué va a ser esto si $x$ es un primer como en tu pregunta?
fleablood
Puntos
5913
Cada número, n puede ser escrito como $n = mp + k $ donde $0 \le k < p$. $n$ es relativamente primer a $p$ si y sólo si $k \ne 0$. Hay $p-1$ opciones. Para números menores que $p^2$ (no se indica en el OP, pero con la clara intención por el libro; de lo contrario, hay una infinidad de números primos relativos a cualquier número), $0 \le m < p$. Así que hay $p$ opciones para $m$.
Por lo tanto, hay $p(p-1)$ opciones relativamente primer a $p$.
El libro probablemente asumió que era evidente que sólo el $p, 2p, \ldots, (p - 1)p$ no eran relativamente primos, y como hay p de esos hay $p^2 - p = p(p-1)$ que son relativamente primos.
O tal vez el libro se supone que iba a ser claro que los que no pueden, simplemente, ser catalogado como:
$$1,2,\ldots,p-1$$
$$p+1,p+2,\ldots,2p - 1$$
$$2p+1, 2p+2,\ldots,3p - 1$$
...
$$(p-1)p+1, (p-1)p + 2,\ldots,p^2 - 1$$
Que son evidentemente $p$ secuencias de $p-1$ elementos.
O tal vez el libro había manifestado que no se $p-1$ menos que $p (1 \ldots(p-1))$. $2(p-1)(1\ldots(p-1)$ y $p + 1 \ldots p + (p-1))$ menos de $2p$. Y $m(p-1)$ menos de $mp (1 \ldots p-1, p+1 \ldots p + (p-1), 2p + 1 \ldots 2p + (p-1)$, etc. hasta el $(m-1)p + 1 \ldots (m-1)p + (p-1))$.
