Un conjunto de n enteros es un residuo completo módulo n si no hay dos elementos congruentes módulo n.

Un conjunto de n enteros es un residuo completo módulo n si no hay dos elementos congruentes módulo n.

Entiendo el teorema, pero ¿cómo hago para demostrarlo? ¡Cualquier ayuda sería apreciada!

Mi intento.

El teorema 3.17 establece

Sea n un número natural. Cualquier conjunto {a1,a2,...,an} de n enteros para los cuales dos no son congruentes es un sistema de residuos completo módulo n.

Intuitivamente, esto tiene sentido, si no hay dos congruentes, entonces todos tienen residuos distintos.

Prueba por contradicción aplicando el principio del casillero (nunca lo he usado en una prueba).

Supongamos que tenemos un conjunto de n enteros, llámelo A={a1,a2,...an} en el que no hay dos congruentes módulo n y supongamos que tenemos un conjunto de residuos R={r1,r2...rn-1 } donde tenemos menos de n residuos.

Como a1 no es congruente mod n con ningún ai para 1

Como a2 no es congruente mod n con ningún ai para 2

Ahora bien, an no es congruente con ningún ai mod n para ningún 1<=i<=n-1, por lo que según el DA, an=n(qn)+rn, lo que implica que an es congruente con rn mod n, pero esto es imposible ya que R tiene menos de n elementos (restos), por lo que an es congruente con algún ai para algún n<=i<=1, pero esto contradice que an no es congruente con ningún ai.

Esto generalmente se denomina "sistema completo de residuos" y, a menudo, se define como un conjunto de norte enteros sin mod congruente de dos norte . Si se le ha pedido que pruebe esto, probablemente se le haya proporcionado alguna otra definición de "sistema completo de residuos". ¿Qué definición tienes?
¿Principio del casillero?
¡Mi libro dice que cada entero (en Z) es congruente con solo uno y solo un elemento en mi conjunto de n enteros!
Sigue usando la división con resto para mostrar que cada elemento es congruente con uno único de los números {0,1, ..., n-1} y luego usando la división con resto para decir que cada entero es congruente con uno único de estos.
Ok, ¿entonces lo que estás diciendo es que cada resto será único? ¿Y por lo tanto todos los números enteros no son congruentes entre sí en absoluto?
No diría "y, por lo tanto, todos los números enteros no son congruentes entre sí", ya que suena como una deducción. Eso no es una deducción, sino más bien una reafirmación de su hipótesis de que "no hay dos elementos congruentes módulo n". Pero sí, esa hipótesis implica que “cada resto será único”.
La prueba real depende en gran medida de cuán formal esté siendo (por ejemplo, cuál es la definición de "Un conjunto de norte enteros?") Pero en el fondo, el argumento es el algoritmo de división y el principio del casillero.
Así que nunca he trabajado realmente con el director del casillero, para ser honesto, no creo que pueda trabajar con él. Puedo hacer una prueba totalmente manual de esto, pero usar el principio de Pidgeon Hole me mataría
El principio del casillero es en realidad quizás la técnica de prueba más fácil de describir que existe. (Usarlo puede ser complicado a veces, pero aquí no hay ningún truco). No dude en usarlo. Que tu conjunto de n enteros sean las palomas, y que el conjunto de residuos que dan al dividir por n sean los casilleros. Supongamos, para llegar a una contradicción, que este conjunto de residuos no es {0, 1, 2, ..., n-1}, por lo que tiene menos de n elementos. Ahora puedes aplicar el principio del casillero y llegar a una contradicción.
No veo dónde usas el principio del casillero. Cambiaría lo siguiente: deje que R sea específicamente el conjunto de residuos cuando divide cada uno de a 1 , … , a norte por n Supongamos, para llegar a una contradicción, que el conjunto R tiene menos de norte elementos. Entonces, usando el principio del casillero con los elementos de R como los agujeros y los elementos a 1 , … , a norte como las palomas, puedes decidir que...

Respuestas (1)

Si v = r mod n y w = r mod n entonces v = w mod n.

Por definición, un residuo completo módulo n es un conjunto de n enteros { r i } donde no hay dos congruentes entre sí. Lo que necesitamos probar es que cualquier otro conjunto { s i } de n enteros también es un residuo completo.

Bien { r i } siendo un residuo completo significa, cada s i = r j modificación norte para algunos r j . Otro s k dónde s k ≠ s i es congruente con algunos r yo . Si r yo = r j el s i un s k son congruentes entre sí. Así cada uno s k es congruente con otro r j y así cada uno s i está en una clase de congruencia única y como { r i } representa todas las clases y existe una correspondencia directa entre { r i } y { s i }, { s i } es un residuo completo.

Un conjunto de n enteros es un residuo completo módulo n si no hay dos elementos congruentes módulo n.
RespuestasAquíPolítica de privacidad1y, 0v