La simetría en la reducción de residuos de los sistemas de

Question

Esto puede ser una pregunta estúpida, pero a mí me parece que la reducción de residuos de los sistemas de modulo N son simétricos alrededor de N/2; es decir, que la hay el mismo número de enteros no divisible por un factor de N que son menores que N/2, ya que hay que son más grandes. Es este un caso, y hay literatura que iba a necesitar para hacer referencia en un documento que se utiliza este hecho?

Para ser claros, en este caso, yo uso "la Reducción de los Residuos del Sistema" para hacer referencia al sistema de números de contado por el totient de N, es decir, los números menores que N que son primos relativos con N.

Answer 1

Esto es ciertamente verdadero. No sería necesario citar cualquier literatura de usar tal cosa en un papel, como la prueba se sigue inmediatamente de la definición de divisibilidad (escribí dos abajo). Si realmente quería citar algo, la cita introductoria número de el libro de la teoría que explica la divisibilidad y la aritmética modular.

Para completar, un par de pruebas.

Reclamo: Si $m < n$$\gcd(m,n) = 1$, $\gcd(n-m,n)=1$.

prueba 1: $d|(n-m)$ $d|n \iff d|m$ $d|n$ por la divisibilidad de las definiciones. $\spadesuit$

prueba 2: Vamos a usar Bezout, como un ejercicio. A continuación, $\gcd(n,m)=1 \implies$ no son enteros $a,b$ s.t. $an + bm = 1$. Pero, a continuación,$-b(n-m) + (a+b)n = 1$, por lo que el$\gcd(n-m,n) = 1$. $\clubsuit$