Modular la congruencia no sumar

Question

Estoy teniendo problema realmente, realmente la comprensión del modulo de congruencia.

Entiendo que es intuitivamente muy bien. Sin embargo, me temo que mi experiencia en desarrollo no está ayudando.

Escritura:

$x \equiv y \pmod m$

Significa que tanto $X$ $Y$ pertenecen tienen el mismo resto después de ser dividido por $m$. Por ejemplo:

$17 ≡ 20 \pmod 3$

Como ambos pertenecen a la misma "clase" de los números con un recordatorio de las $2$ cuando se divide por $3$.

En MATEMÁTICA la CRIPTOLOGÍA por Keijo Ruohonen confirma esto:

La congruencia $x ≡ y$ $mod$ $m$ dice que cuando se divide $x$ $y$ $m$ el resto es el mismo, o en otras palabras, $x$ $y$ pertenecen a la misma clase residual modulo $m$

A continuación, un caso específico.

$59 ≡ -1 \pmod{60}$

Aquí mi entendimiento se rompe. Ambos pertenecen a la misma clase (los números que se están "detrás" de una de $60$ multuple, intuitivamente hablando). Sin embargo, dividiendo $x$ $y$ $m$ el resto es el mismo (Ruohonen) no es cierto, ya $59 % 60 = 59$y $-1 % 60 = -1$.

Lo que me estoy perdiendo?

Answer 1

Estás malinterpretando la definición matemática de división con resto cuando es extendido a los enteros negativos. Su estado de cuenta -1 % 60 = -1 es NO verdadero.

Citando el artículo de la Wikipedia sobre el Resto:

Si $a$ $d$ son enteros, con $d$ no-cero, puede ser demostrado que no existen enteros únicos $q$$r$, de tal manera que $a=qd+r$$0\le r<|d|$. El número de $q$ se llama el cociente, mientras que $r$ se llama el resto.

Tenga en cuenta que, por definición, el resto puede NO ser negativo. Esa es una razón por la que el ejemplo está mal: el resto no puede ser "$-1$".

Aquí es una manera de mirar (algo de manera informal). Por ejemplo, usted dijo que $20$ tiene un resto de $2$ cuando se divide por $3$. Sí, eso es cierto, pero ¿por qué? Apuesto a que se les enseñó a buscar el mayor múltiplo de $3$ que no exceda $20$. Esto va a ser $18$, y el resto es $20-18=2$.

Bueno, todo lo que tienes que hacer ahora es aplicar exactamente la misma lógica para los números negativos también! Vamos a ver el resto de $-20$ modulo $3$. ¿Cuál es el mayor múltiplo de $3$ que no exceda $-20$? Es NO $-18$, debido a $-18>-20$, no menos. En su lugar, el mayor múltiplo de $3$ que no exceda $-20$$-21$, y el resto es $(-20)-(-21)=1$.

En términos de la definición, $a=\color{blue}{q}d+\color{red}{r}$ donde $\color{blue}{q}$ es el cociente e $\color{red}{r}$ es el resto, $0\le\color{red}{r}<|d|$, para estos dos ejemplos tenemos: $20=\color{blue}{6}\cdot3+\color{red}{2}$ para la primera, y $-20=\color{blue}{(-7)}\cdot3+\color{red}{1}$ para el segundo.

Mismo para el último ejemplo. ¿Cuál es el mayor múltiplo de $60$ que no exceda $-1$? Es NO $0$, debido a $0>-1$, no menos. En su lugar, el mayor múltiplo de $60$ que no exceda $-1$$-60$, y el resto es $(-1)-(-60)=59$. En términos de la definición: $-1=\color{blue}{(-1)}\cdot60+\color{red}{59}$.

Answer 2

Tenga en cuenta que al dividir un número por $60$ el resto debe ser un entero $r$ se $0 \leq r < 60$. El algoritmo de la división nos dice que un número entero siempre existe en este rango. Observar que $$59 = (0)\cdot 60 + 59$$ and $$-1 = (-1)\cdot 60 + 59 $$

Así que podemos ver que $59 \equiv -1 \ (\operatorname{mod} 60)$. Ambos tienen un resto de $59$.