[Nub]

Hola, recién comienzo el tema y vi a un profesor que dado un numero casi instantáneamente sabia otro que era congruente y me pregunte como lo hacia tan rápido, yo para ver que un numero es congruente a otro aplico la definición es decir los resto y veo si es divisible entre el modulo, asi que o era muy rápido haciendo esa cuenta o había algo mas, y lo único que encontré que puede funcionar que dado un numero, encontrar uno congruente era una propiedad que decía lo siguiente: Dado un \( n\in{\mathbb{Z^+}} \) y \( a\in{\mathbb{Z}} \) existe un unico r tal que \( a\equiv{r} \) donde \( r \) es el resto de la division entera \( a \) entre \( n \).

Y bueno, \( a=10,n=2 \) podemos ver que \( 10=2*5+0 \) entonces \( 10\equiv{0} \) pero yo quería saber otros números que sean congruentes a 10, entonces pense que \( 10=2*4+2 \) luego \( 10\equiv{2} \) y si usamos la def de congruencias la cumple, pero no debería poder usarse así la propiedad, ya que el resto debe ser menor que 2 y mayor a 0, pero por algún motivo (por def exactamente) \( 10\equiv{2} \)
¿Hay algo que no sepa?, es decir alguna propiedad que haga cosas así fácilmente

En fin, como dado un numero y el modulo obtengo cosas congruentes a dicho numero? claro también pensé en usar la definición literalmente y plantear algo como \( 10=x \) luego \( 2|10-x \), \( 10-2q=x \)  pues le voy dando valores enteros a q y consigo x

[RDC]

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

[feriva]

Y bueno, \( a=10,n=2 \) podemos ver que \( 10=2*5+0 \) entonces \( 10\equiv{0} \) pero yo quería saber otros números que sean congruentes a 10...

Congruentes con 10... ¿módulo qué? No me queda claro del todo.

Por ejemplo:

\( 30\equiv10\,(mod\,20) \).

Quiere decir que si divides 30-10 entre 20 el resto es cero. O sea \( 20\equiv0\,(mod\,20) \).

Otros ejemplos:

\( 22\equiv10\,(mod\,3) \).

Porque 22-10=12, que es divisible entre el módulo, 3.

Ahora bien, 10 es 3+3+3+1, entonces es equivalente a 1, o sea:

\( 22\equiv10\,(mod\,3)\Rightarrow \)

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

y vemos que también funciona, pues 22-1=21 que es divisible entre 3.

Por otra parte, tienes todas las equivalencias que quieras suamando treses al 1:

\( 22\equiv4\,(mod\,3) \)

\( 22\equiv7\,(mod\,3) \)
...
Vemos que funciona, como no puede ser de otra manera: 22-4=18, divisible entre 3; 22-7=15, también...

Y también podemos restar treses

con 1-3=-2

\( 22\equiv-2\,(mod\,3) \)

Si pasas el 2 al otro lado, tienes 24 que es divisible entre 3.

Y, bueno, pues es tomar costumbre.

Saludos.

[Nub]

Y bueno, \( a=10,n=2 \) podemos ver que \( 10=2*5+0 \) entonces \( 10\equiv{0} \) pero yo quería saber otros números que sean congruentes a 10...

Congruentes con 10... ¿módulo qué? No me queda claro del todo.

\( n=2 \), modulo 2, osea basicamente di un numero y un "modulo" (no se si se dice así  ) para encontrar un numero congruente con a modulo \( n \), en este caso 2

[Nub]

Ahora bien, 10 es 3+3+3+1, entonces es equivalente a 1, o sea:

\( 22\equiv10\,(mod\,3)\Rightarrow \)

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

y vemos que también funciona, pues 22-1=21 que es divisible entre 3.

Esto entiendo la mitad, se que funciona porque es evidente que 22-1=21, pero no se de donde sale la idea de que como 10 es 3+3+3+1 luego es 22 congruente con 1

[Nub]

Por otra parte, tienes todas las equivalencias que quieras suamando treses al 1:

\( 22\equiv4\,(mod\,3) \)

\( 22\equiv7\,(mod\,3) \)
...
Vemos que funciona

Lo mismo de arriba, funcionar funciona por definición, pero de donde sale la idea de hacer eso

[feriva]

Ahora bien, 10 es 3+3+3+1, entonces es equivalente a 1, o sea:

\( 22\equiv10\,(mod\,3)\Rightarrow \)

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

y vemos que también funciona, pues 22-1=21 que es divisible entre 3.

Esto entiendo la mitad, se que funciona porque es evidente que 22-1=21, pero no se de donde sale la idea de que como 10 es 3+3+3+1 luego es 22 congruente con 1

Ah, vale.

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.

En general, ese 7 o cualquier número que dé el múltiplo del módulo que sea lo podemos escribir con “k” u otra letra

\( 22=k\cdot3+1 \)

donde en la notación de congruencias no se pone esa “k” que nos da el múltiplo del módulo, sino que dice lo mismo así:

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

Por aclararlo un poco más:

\( 22=k\cdot3+1\Rightarrow \)

\( 22=0+1\Rightarrow \)

\( 22=1 \) módulo tres.

Así se ve raro (es equivalente, no igual) pero si piensas que las 2, las dos horas del reloj análogico, es lo mismo que las 14 horas, pues no es raro: 14=2; ó 12=24; ó 5=17... Tanto si es la 1 de la madrugada como si son las 13 horas de la tarde, en caso de que nos preguntan que qué horas es, sólemos decir “la una” indistintamente, pues sería muy pedante contestar: son las 13 horas congruentemente con la 1 módulo 12

Saludos.

Saludos.

[RDC]

Ahora bien, 10 es 3+3+3+1, entonces es equivalente a 1, o sea:

\( 22\equiv10\,(mod\,3)\Rightarrow \)

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

y vemos que también funciona, pues 22-1=21 que es divisible entre 3.

Esto entiendo la mitad, se que funciona porque es evidente que 22-1=21, pero no se de donde sale la idea de que como 10 es 3+3+3+1 luego es 22 congruente con 1

Ah, vale.

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.

En general, ese 7 o cualquier número que dé el múltiplo del módulo que sea lo podemos escribir con “k” u otra letra

\( 22=k\cdot3+1 \)

donde en la notación de congruencias no se pone esa “k” que nos da el múltiplo del módulo, sino que dice lo mismo así:

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

Saludos.

Exacto. Es lo que hago yo.

Dado que entre \( m \) y \( m(m+1) \) existen diferentes restos, \( r_i \), entonces un número \( x \) que esta entre \( m \) y \( m+1 \) se puede escribir como \( x=m+r  \)siendo r el resto. Entonces, si a \( x \) le vas sumando m vas obteniendo números congruentes con él. por eso decía que cualqueir número se puede escribir usando este sencilla fórmula en base a un módulo \( m \):

\( x=ms+r \)
\( y=mv+r \)

se despejan los restos, r, que se suponen iguales y tenemos que:

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

De modo que basta restar dos números \( x,y \) para determinar su congruencia respecto a un módulo m cualquiera.

[feriva]

Exacto. Es lo que hago yo.

Dado que entre \( m \) y \( m(m+1) \) existen diferentes restos, \( r_i \), entonces un número \( x \) que esta entre \( m \) y \( m+1 \) se puede escribir como \( x=m+r  \)siendo r el resto. Entonces, si a \( x \) le vas sumando m vas obteniendo números congruentes con él. por eso decía que cualqueir número se puede escribir usando este sencilla fórmula en base a un módulo \( m \):

\( x=ms+r \)
\( y=mv+r \)

se despejan los restos, r, que se suponen iguales y tenemos que:

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

De modo que basta restar dos números \( x,y \) para determinar su congruencia respecto a un módulo m cualquiera.

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).

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.

[RDC]

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.