[feriva]

Es más general. Porque cuando se pone “r” se suele entender un resto tal cual, no una equivalencia a un resto. Es decir, si fuera módulo 8, por ejemplo, se entiende por resto alguno de éstos 0,1,2,3,4,5,6,7. Entonces, si r=10, por ejemplo, es un representante del resto 2, porque 8+2=10, pero no es un resto en sí (quizá se podría hacer una diferencia entre residuo y resto en este sentido, pero buscando en Google no me queda claro que se haga).

Spoiler

Y con una equivalencia al resto también se cumple lo que dices:

\( x=ms+r \)

\( y=mv+a \)

\( x-y=m(s-v)+r-a \).

Ahora, si tuviéramos la equivalencia \( a\equiv r\,(mod\,m) \), entonces \( r-a\equiv0\,(mod\,m) \), con lo que

\( x-y\equiv m(s-v)+r-a\Rightarrow \)

\( x-y\equiv m(s-v)+0 \)

\( x-y\equiv m(s-v) \)

o sea, “m” divide a x-y.

Se puede ver un ejemplo (considero módulo m=5, por poner un caso):

\( x=4\cdot5+3 \)

\( y=7\cdot5+33 \)

Vemos que \( 33=3 \) módulo 5, pues es \( (6\cdot5)+3=3 \), o sea, \( 0+3=3 \).

Restando

\( x-y=(4-7)\cdot5+3-33\Rightarrow \)

\( x-y=0-30 \)

y, efectivamente, -30 es divisible entre m=5.

Esto ocurrirá siempre con el resto o un representante suyo, un número congruente con él.
Saludos

[cerrar]

.

No sé Feriva... no me parece más general, aunque sí una notación más simple: dados dos números \( x,y \) que al restarlos da un factor \( m \) es más fácil escribir \( x\equiv{y}  \) mod(\( m \)). Eso es cierto.

Por otro lado, la idea, al menos cuando yo utilizo este pequeño artilugio, es ajustar los restos, \( r \), de tal modo que siempre \( r<m \). Nada más. Así, empleando los ejemplos \( x,y \) que has puesto tenemos que:

\( x=4\cdot5+3 \) Aquí ok, porque el 3<5 y por tanto el 3 hace de resto


\( y=7\cdot5+33 \) aquí no tienes ningún resto, para ello debes reescribir \( y \) de esta forma \( y=13·5+3 \). Entonces sí tienes un número múltiplo de \( m  \) más un resto \( r \).

Ahora, reescrito el número \( y \), no sólo salta a la vista que \( x,y \) son congruentes mod(5), sino que: \( 5(13-4)-3+3=5(9) \). Además de ser también congruentes módulo 3,9,15, 45.

De hecho, dado un modulo \( m \) cualquiera todo número natural \( x \) siempre se puede escribir como:

\( x=m·s+r \), siendo \( 0\leq{r}<m \)

Y en base a ello puedes operar como te venga en gana.

Por ejemplo es muy fácil demostrar que todos los cuadrados perfectos son siempre congruentes en modulo 3:

\( x=3s+1\Longleftrightarrow{(3s+1)^2}=(3s)^2+6s+1=3p+1 \)
\( y=3v+2\Longleftrightarrow{(3v+2)^2}=(3v)^2+12v+3+1=3q+1 \)

Por eso si se le resta 1 a cualquier cuadrado perfecto siempre da un múltiplo de 3 (pequeño teorema de Fermat)

En todo caso, como nub preguntaba si había una forma rápida de ver si dos números dados son congruentes entre sí en algún módulo, simplemente esta era mi propuesta.

Claro, pero en las congruencias surgen los representantes, que es algo que da trabajo al resolverlas. Si pones la misma “r” en los dos números, al restar te queda de manera obvia un múltiplo del módulo. Las congruencias tienen eso precisamente, si siempre fueran iguales a un resto propiamente dicho, el múltiplo del módulo quedaría determinado, no haría falta esa notación; es decir, por ejemplo: \( 5k+1\equiv16 \), si el resto módulo 5 sólo puede aparecer como tal (en este caso 1, en vez de 6, 11... etc.) pues esa k sólo puede valer 3, no hace falta el signo de congruencia, es directamente una igualdad (y lo mismo pasa con el 16, queda como representante, pero fijo).

Saludos.

[Nub]

Por el algoritmo de la división, si dividimos 22 entre 3, toca a 7, porque por 8 se pasa, entonces

\( 22=7\cdot3+1 \)

donde 1 es el resto y, por tanto, restando 1 a ambos lados \( 22-1=3\cdot7 \).

Ahora, si sumamos el módulo a ambos lados

\( 22+3=7\cdot3+4 \)

\( 25=7\cdot3+4 \)

y restamos 4 a ambos lados

\( 25-4=21 \).

Podemos sumar el módulo todas las veces que se quiera, es como sumar cero a efectos de divisibilidad, es neutro; equivale al resto cero.

Esto quiere decir que lo podemos sumar sólo al lado del resto y también se mantiene la equivalencia:

\( 22\equiv7\cdot3+1+3 \)

\( 22\equiv7\cdot3+4 \)

\( 18\equiv7\cdot3 \); son equivalentes porque 18 y 21 divididos por el módulo dan resto cero. (si dan el mismo resto los números son equivalentes según el módulo). A veces se pone el signo "=" siempre que se sepa el contexto, siempre que hablemos de congruencias.

Hola, no entendí tanto, voy a escribir lo que voy interpretando. Teniamos 22 y modulo 3, por división entera \( 22=3*7+1 \) luego si pasamos el resto para el otro lado \( 22-1=3*q\Rightarrow{3|22-1\Rightarrow{22\equiv{1}}},mod(3) \) hasta aca bien, luego lo demas no lo entendi por lo siguiente, si sumamos el modulo ambos lados \( 25=3*7+4 \) luego hacemos lo mismo \( 25-4=3*q\Rightarrow{3|25-4\Rightarrow{25\equiv{4},mod(3)}} \) y bueno, ahora ni tenemos algo congruente a 22, osea cosa que yo no pedía

[Nub]

Bueno, como yo no estoy muy familiarizado con la aritmética modular estoy usando otra forma de hacer congruencias, mientras voy aprendiendo a usarlas a mi ritmo:

Cualquier número \( x \) que sea congruente  con otro \( y \) en módulo \( m \) (ambos tienen el mismo resto, \( r \), al dividirlos por \( m \)) es como expresar:

\( x=mv+r \Longleftrightarrow{x-mv=r} \), siendo \( v \) un natural cualquiera
\( y=ms+r \Longleftrightarrow{y-ms=r} \), siendo \( s \) un natural cualquiera
 
Por tanto:
\( x-mv=y-ms \Longleftrightarrow{x-y=m(v-s)}  \)

En otras palabras, si restas dos números y te sale que la resta es un múltiplo de \( m \), entonces es que esos dos números que has restado son congruentes en módulo \( m \).

Por ejemplo:

\( x=34 \), \( y=52 \)

\( 52-34=18 \). Por tanto, el 34 y el 52 son congruentes en los módulos: 2,3,6,9,18

No sé si eso te sirve

Si, es básicamente lo que decía, probablemente la forma rápida era, tengo un numero, pienso que le puedo restar tal que quede múltiplo del modulo

[feriva]

Por el algoritmo de la división, si dividimos 22 entre 3, toca a 7, porque por 8 se pasa, entonces

\( 22=7\cdot3+1 \)

donde 1 es el resto y, por tanto, restando 1 a ambos lados \( 22-1=3\cdot7 \).

Ahora, si sumamos el módulo a ambos lados

\( 22+3=7\cdot3+4 \)

\( 25=7\cdot3+4 \)

y restamos 4 a ambos lados

\( 25-4=21 \).

Podemos sumar el módulo todas las veces que se quiera, es como sumar cero a efectos de divisibilidad, es neutro; equivale al resto cero.

Esto quiere decir que lo podemos sumar sólo al lado del resto y también se mantiene la equivalencia:

\( 22\equiv7\cdot3+1+3 \)

\( 22\equiv7\cdot3+4 \)

\( 18\equiv7\cdot3 \); son equivalentes porque 18 y 21 divididos por el módulo dan resto cero. (si dan el mismo resto los números son equivalentes según el módulo). A veces se pone el signo "=" siempre que se sepa el contexto, siempre que hablemos de congruencias.

Hola, no entendí tanto, voy a escribir lo que voy interpretando. Teniamos 22 y modulo 3, por división entera \( 22=3*7+1 \) luego si pasamos el resto para el otro lado \( 22-1=3*q\Rightarrow{3|22-1\Rightarrow{22\equiv{1}}},mod(3) \) hasta aca bien, luego lo demas no lo entendi por lo siguiente, si sumamos el modulo ambos lados \( 25=3*7+4 \) luego hacemos lo mismo \( 25-4=3*q\Rightarrow{3|25-4\Rightarrow{25\equiv{4},mod(3)}} \) y bueno, ahora ni tenemos algo congruente a 22, osea cosa que yo no pedía

Teníamos que 22 es congruente con 1 módulo 3, o sea.

\( 22\equiv1(mod\,3) \)

y aquí tenemos que 25 es congruente con 4 módulo 3

\( 25\equiv4(mod\,3) \)

pero 4=3+1, o sea, \( 4\equiv1\,(mod\,3) \), y en consecuencia 25 es congruente con 1 módulo 3:

\( 25\equiv1(mod\,3) \)

Entonces

\( 25\equiv22(mod\,3) \)

Pues hemos visto que tanto 22 como 25 son congruentes ambos con 1; así que son congruentes entre ellos. Y restando 25-22 pues da 3, se que es divisible entre 3 y, por tanto, 25 y 22 son congruentes módulo 3

Saludos.

[Nub]

Por el algoritmo de la división, si dividimos 22 entre 3, toca a 7, porque por 8 se pasa, entonces

\( 22=7\cdot3+1 \)

donde 1 es el resto y, por tanto, restando 1 a ambos lados \( 22-1=3\cdot7 \).

Ahora, si sumamos el módulo a ambos lados

\( 22+3=7\cdot3+4 \)

\( 25=7\cdot3+4 \)

y restamos 4 a ambos lados

\( 25-4=21 \).

Podemos sumar el módulo todas las veces que se quiera, es como sumar cero a efectos de divisibilidad, es neutro; equivale al resto cero.

Esto quiere decir que lo podemos sumar sólo al lado del resto y también se mantiene la equivalencia:

\( 22\equiv7\cdot3+1+3 \)

\( 22\equiv7\cdot3+4 \)

\( 18\equiv7\cdot3 \); son equivalentes porque 18 y 21 divididos por el módulo dan resto cero. (si dan el mismo resto los números son equivalentes según el módulo). A veces se pone el signo "=" siempre que se sepa el contexto, siempre que hablemos de congruencias.

Hola, no entendí tanto, voy a escribir lo que voy interpretando. Teniamos 22 y modulo 3, por división entera \( 22=3*7+1 \) luego si pasamos el resto para el otro lado \( 22-1=3*q\Rightarrow{3|22-1\Rightarrow{22\equiv{1}}},mod(3) \) hasta aca bien, luego lo demas no lo entendi por lo siguiente, si sumamos el modulo ambos lados \( 25=3*7+4 \) luego hacemos lo mismo \( 25-4=3*q\Rightarrow{3|25-4\Rightarrow{25\equiv{4},mod(3)}} \) y bueno, ahora ni tenemos algo congruente a 22, osea cosa que yo no pedía

Teníamos que 22 es congruente con 1 módulo 3, o sea.

\( 22\equiv1(mod\,3) \)

y aquí tenemos que 25 es congruente con 4 módulo 3

\( 25\equiv4(mod\,3) \)

pero 4=3+1, o sea, \( 4\equiv1\,(mod\,3) \), y en consecuencia 25 es congruente con 1 módulo 3:

\( 25\equiv1(mod\,3) \)

Entonces

\( 25\equiv22(mod\,3) \)

Pues hemos visto que tanto 22 como 25 son congruentes ambos con 1; así que son congruentes entre ellos. Y restando 25-22 pues da 3, se que es divisible entre 3 y, por tanto, 25 y 22 son congruentes módulo 3

Saludos.

Gracias feriva esto me lleva a recordar una vez que me dijiste que todo natural se podia escribir como \( 3k \),\( 3k+1 \) y \( 3k+2 \), y no podia ser \( 3k+3 \) pues \( 3(k+1) \) y luego \( 3k' \), no se si tiene algo que ver

[feriva]

Gracias feriva esto me lleva a recordar una vez que me dijiste que todo natural se podia escribir como \( 3k \),\( 3k+1 \) y \( 3k+2 \), y no podia ser \( 3k+3 \) pues \( 3(k+1) \) y luego \( 3k' \), no se si tiene algo que ver

Claro que tiene que ver

En realidad las congruencias no son más que una forma de escribir eso y plantear ecuaciones que van a tener infinitas soluciones.

Saludos.

[Nub]

Gracias feriva y RDC

[feriva]

Gracias feriva y RDC

De nada.

*Bueno, no siempre van a tener infinitas, como te decía depende de las congruencias; las lineales sí.

Mira esto, por ejemplo:

\( 5x\equiv1(mod\:14) \)

Hay que buscar un número tal que multiplicado por 5 deje resto 1 al ser dividido entre 14; o sea, que sea congruente con 1 módulo 14.

Pues eso es esta ecuación

\( 5x-1=14y \)

de tal forma que 14 divide a 5x-1 quedando igual a un entero “y”.

Despejando

\( 5x+14y=1 \)

Y ahora haz 5=a y 14=b y tienes una identidad de Bezóut.

No es más que la ecuación de una recta, si te fijas, sólo que los puntos (x,y) a obtener son solamente los de coordenadas enteras; y son infinitos, claro.

Saludos.

.

[Nub]

Gracias feriva y RDC

De nada.

*Bueno, no siempre van a tener infinitas, como te decía depende de las congruencias; las lineales sí.

Mira esto, por ejemplo:

\( 5x\equiv1(mod\:14) \)

Hay que buscar un número tal que multiplicado por 5 deje resto 1 al ser dividido entre 14; o sea, que sea congruente con 1 módulo 14.

Pues eso es esta ecuación

\( 5x-1=14y \)

de tal forma que 14 divide a 5x-1 quedando igual a un entero “y”.

Despejando

\( 5x+14y=1 \)

Y ahora haz 5=a y 14=b y tienes una identidad de Bezóut.

No es más que la ecuación de una recta, si te fijas, sólo que los puntos (x,y) a obtener son solamente los de coordenadas enteras; y son infinitos, claro.

Saludos.

.

Si, podria resolver la diofántica y tendria infinitas soluciones enteras, pero creo que cuando haces una ecuación de congruencias no tienes infinitas, se puede pensar que si, pero modulo 14 creo que agruparías todas en una clase de congruencia (no se si esto esta bien, estuve viendo por ahi )

[feriva]

Si, podria resolver la diofántica y tendria infinitas soluciones enteras, pero creo que cuando haces una ecuación de congruencias no tienes infinitas, se puede pensar que si, pero modulo 14 creo que agruparías todas en una clase de congruencia (no se si esto esta bien, estuve viendo por ahi )

Pero si es prácticamente lo mismo escrito de otra manera.

Esta ecuación \( 5x+14y=1 \) tiene soluciones

\( x=14k+3 \)

\( y=-5k-1 \).

Y funciona para “k” el entero que quieras; funciona en la ecuación y en la congruencia.

Por ejemplo, con k=3 tenemos x=45, y= -16.

Entonces sustituyendo en la congruencia \( 5x\equiv1\,(mod\,14) \) queda

\( 5\cdot45\equiv1\,(mod\,14) \)

\( 225\equiv1\,(mod\,14) \)

\( 224\equiv0\,(mod\,14) \)

Y entonces “y”, en principio, sería (para este caso, para k=3) \( y=\dfrac{224}{14}=16 \); pero en la ecuación escrita así \( 5x+14y=1 \) tiene que ir con signo menos.

Saludos.