¿Qué son las soluciones diferentes incongruentes de una congruencia lineal? Por ejemplo la congruencia lineal 5x=52 (mod 3) llego que sus...

No se si a algunos la pregunta les parecerá un trabalenguas (no insinúo que la pregunta esté mal hecha, sino que el lenguaje a veces es un poco complicado)… pero intentaré responder de una forma que sea un poco comprensible.

Las clases de congruencia, son clases de equivalencia que se establecen en números enteros según el resto de la división por un entero. Si el entero por el que se divide es "n" se hablará de "clases de congruencia módulo n"… y eso significa que habrá diferentes conjuntos donde los enteros de cada conjunto son equivalentes "módulo n"… se dice que son equivalentes en el sentido de que dan el mismo resto al dividir por n. A ese resto de la división por un entero n en este contexto de clases de congruencia se le suele denominar residuo, o "residuo módulo n" en lugar de 'resto'. Como los restos al dividir por n son enteros entre 0 y (n-1) serán n clases de equivalencia distintas.

Por ejemplo, la pregunta habla de "(mod3)(mod3)" y, entonces, n=3 y nos referimos a las clases de congruencia módulo 3, es decir, 3 subconjuntos de los enteros donde en cada subconjunto todos los elementos producen el mismo resto. Los subconjuntos son:

0(mod3)0(mod3) : subconjunto de enteros cuyo resto al dividir por 3 es 0… es decir, los múltiplos de 3, que son números de la forma 3⋅t3⋅t . Ejemplos: 0, 3, 6, 9… -3, -6, -9 … Al dividirlos por 3 da resto 0 y se dice que son 'congruentes' con el 0(mod3)0(mod3) … 3(mod3)3(mod3) es equivalente o congruente con 0(mod3)0(mod3), etc…

1(mod3)1(mod3) : subconjunto de enteros cuyo resto al dividir por 3 es 1… es decir, los enteros de la forma (1+3⋅t)(1+3⋅t) donde t es un entero cualquiera: t = 0, 1, -1, 2, -2 …
Ejemplos: 1, 4, -2, 7, -5 … Esos son congruentes con 1(mod3)1(mod3)…. Ej: 4(mod3)4(mod3) es equivalente o congruente con 1(mod3)1(mod3).

2(mod3)2(mod3) : subconjunto de enteros cuyo resto al dividir por 3 es 2… es decir, los enteros de la forma (2+3⋅t)(2+3⋅t) donde t es un entero cualquiera: t = 0, 1, -1, 2, -2 …
Ejemplos: 2, 5, -1, 8, -4 … Esos son congruentes con 2(mod3)2(mod3)…. Ej: 5(mod3)5(mod3) es equivalente o congruente con 2(mod3)2(mod3).

Por tanto, los miembros de cada clase son congruentes entre sí… pero son incongruentes con los miembros de las otras clases. ¿Qué quiere decir incongruentes? Pues que tienen diferente resto, que están en clases diferentes, y que no puedes llegar de uno a otro sumando un múltiplo entero de 3.
Por ejemplo, el 5(mod3)5(mod3) es incongruente con el 1(mod3)1(mod3) porque partiendo del 1 no puedes llegar al 5 sumando 3*t … 1+3*1 = 4; 1+3*2 = 7; 1+3*(-1) = -2 … Y, viceversa, tampoco puedes llegar al 1 sumando 3*t al 5: 5+3*(-1) = 2; 5+3*(-2) = -1 …

Entonces, ¿qué quiere decir soluciones diferentes incongruentes? Quiere decir que no hace falta decir todos los enteros que sean de la misma clase de equivalencia, ya que si un entero de una clase es solución entonces todos los enteros de la misma clase también son solución… Por tanto, lo que se pide son enteros de clases diferentes que sean solución de la ecuación, en este caso una ecuación lineal. Y, bueno, cuando se piden soluciones incongruentes creo que de alguna forma se sobreentiende que sean las más simples, las más pequeñas, y habitualmente en el rango de 0 a (n-1). En este caso de 0 a 2.
Dicho de otra forma, las únicas 3 posibles soluciones incongruentes serían 0, 1 ó 2. No habría más posibles soluciones.

Veamos la ecuación:
5x=52(mod3)5x=52(mod3)

El resto al dividir por 3 se puede obtener con la suma de las cifras.
Es decir, el resto al dividir por 3 de un número es SIEMPRE exactamente el mismo que el resto de dividir por 3 la suma de las cifras.
[lo mismo ocurre con los restos al dividir por 9]

Sea este número:

D=c(g)⋅10g+c(g−1)⋅10g−1+…+c(1)⋅10+c(0)D=c(g)⋅10g+c(g−1)⋅10g−1+…+c(1)⋅10+c(0)

Los coeficientes c(0) hasta c(g) son las cifras o dígitos del número decimal D.

Pues bien:

D(mod3)=[c(g)+c(g−1)+…+c(1)+c(0)](mod3)D(mod3)=[c(g)+c(g−1)+…+c(1)+c(0)](mod3)

y

D(mod9)=[c(g)+c(g−1)+…+c(1)+c(0)](mod9)D(mod9)=[c(g)+c(g−1)+…+c(1)+c(0)](mod9)

¿Por qué?
Bueno, simplemente porque 10(mod3)=110(mod3)=1 y 10(mod9)=110(mod9)=1
Al dividir 10 por 3 el resto es 1, y al dividir 10 por 9 el resto es 1 también.

D(mod3)=[c(g)⋅1g+c(g−1)⋅1g−1+…+c(1)⋅1+c(0)](mod3)=D(mod3)=[c(g)⋅1g+c(g−1)⋅1g−1+…+c(1)⋅1+c(0)](mod3)=

=[c(g)+c(g−1)+…+c(1)+c(0)](mod3)=[c(g)+c(g−1)+…+c(1)+c(0)](mod3)

Así que apliquemos la suma de las cifras en este caso.
Tenemos 52(mod3)52(mod3) → las cifras de 52 son el 5 y el 2…
5+2=75+2=7
Por tanto 52(mod3)52(mod3) es equivalente a 7(mod3)7(mod3)
Y el resto de dividir 7 entre 3 es 1. Por tanto:

52(mod3)=1(mod3)52(mod3)=1(mod3)

El 52 está en la misma clase de equivalencia que el 1.
Si un número, como el 5x5x es congruente con 52, lo será con el 1 también.
Por tanto la ecuación es equivalente a:

5x=1(mod3)5x=1(mod3)

Eso significaría: ¿Qué números al multiplicarlos por 5 resultan números que dan resto 1 al dividirlos por 3?

Otra propiedad de las congruencias es que

[a∗b](modn)[a∗b](modn)

es equivalente a

[a(modn)]∗b(modn)[a(modn)]∗b(modn)

En este caso 5(mod3)=2(mod3)5(mod3)=2(mod3)

Por tanto, la ecuación es equivalente a:

2x=1(mod3)2x=1(mod3)

¿Por qué?
Bueno, porque 5=2+35=2+3

5x=(2+3)∗x=2x+3x5x=(2+3)∗x=2x+3x

Pero sea cual sea el x siempre 3x3x es múltiplo de 3 y su resto al dividir por 3 es 0, así que tanto 5x5x como 2x2x caerán en la misma clase de equivalencia módulo 3.

Entonces tenemos la ecuación:

2x=1(mod3)2x=1(mod3)

Como solamente hay 3 posibles soluciones podemos probar cada una de las 3 a ver si son solución

¿ x=0(mod3)x=0(mod3) será solución?
No: 2∗0(mod3)=0(mod3)2∗0(mod3)=0(mod3) … que no es congruente con 1(mod3)1(mod3)

¿ x=1(mod3)x=1(mod3) será solución?
No: 2∗1(mod3)=2(mod3)2∗1(mod3)=2(mod3) … que no es congruente con 1(mod3)1(mod3)

¿ x=2(mod3)x=2(mod3) será solución?
Sí: 2∗2(mod3)=4(mod3)=1(mod3)2∗2(mod3)=4(mod3)=1(mod3)

Por tanto la única solución incongruente con otras posibles soluciones es: 2 (mod 3).

El conjunto de soluciones que dice la pregunta es:

x=−1+3∗tx=−1+3∗t … siendo t un entero.

Ejemplos: -1, 2, -4, 5, -7, 8 ….

Pero aunque esas son muchas soluciones (de hecho, infinitas) todos los elementos de ese conjunto son congruentes, es decir, tienen el mismo resto al dividir por 3… por eso, esas soluciones no son soluciones incongruentes, son todas congruentes entre sí.

A veces también se considera lógico y aceptable dar soluciones negativas…
Si n es par: entre (−n2+1)(−n2+1) y (n2)(n2).
Si n es impar: entre −n−12−n−12 y n−12n−12

En este caso, n = 3, en lugar de soluciones entre 0 y 2 : {0, 1, 2}
se podrían dar soluciones entre -1 y 1 : {-1, 0, 1}

Por tanto, también se podría decir que las soluciones incongruentes son solamente una, que es: -1 (mod 3)

El resto de números enteros o bien no son solución o bien no son incongruentes con esa solución (y, por tanto, es como decir que las otras soluciones "son la misma solución") … por tanto, no serían soluciones "diferentes".
Ej: 5(mod3)5(mod3) también es solución pero es la misma que 2(mod3)2(mod3) y la misma que −1(mod3)−1(mod3) … porque 5(mod3)=2(mod3)=−1(mod3)5(mod3)=2(mod3)=−1(mod3).

Nota: en este caso, al ser solamente 3 posibles soluciones simplemente he probado una a una las posibilidades… pero si n fuese 1000 esa forma de resolverlo no sería adecuada. En general se aplica el algoritmo de Euclides.
Y se llaman también "ecuaciones diofánticas lineales" ¿por qué?
Pues porque hablar de módulos y restos al final es hablar de múltiplos…
Ejemplo:
a∗x=b(modn)a∗x=b(modn)
significa que el resto de dividir a*x entre n es b o equivalente a b(modn)b(modn)
Tenemos:
Dividendo = cociente*divisor + resto

a∗x=cociente∗n+ba∗x=cociente∗n+b

a∗x=n∗y+ba∗x=n∗y+b

a∗x−n∗y=ba∗x−n∗y=b

Esta última es una ecuación diofántica lineal. Es decir, se buscan soluciones enteras (donde "x" e "y" sean enteros) siendo "a", "n" y "b" unas constantes dadas.

En este caso: a = 5; n=3; b = 52

5x−3y=525x−3y=52

Y, como dije antes, esa ecuación es equivalente a:

2x−3y=12x−3y=1

Como 2x es par, no podrá ser "y" par…
Por tanto, y es impar: y=2∗t−1y=2∗t−1

2x−3(2t−1)=12x−3(2t−1)=1

2x−6t+3=12x−6t+3=1

2x−6t=−22x−6t=−2

x−3t=−1x−3t=−1

x=−1+3tx=−1+3t

Si hubiese hecho y=2∗k+1y=2∗k+1
habría sido : x=2+3kx=2+3k

Demasiada artillería para solo 3 posibles soluciones ¿no?

Pero como dije antes, si n es 1000 esta artillería sí tiene sentido.

Ej:
5x=1(mod1001)5x=1(mod1001)

Aquí no vamos a probar todos los valores entre 0 y 1000 a ver cuáles lo cumplen.

5∗x−1001∗y=15∗x−1001∗y=1

MCD(5,1001)=1MCD(5,1001)=1 … entonces tiene solución (porque 1 divide a cualquier entero, en concreto al entero de la derecha, el 1).

1001 / 5 → cociente = 200; resto = 1
1=1001∗1−5∗2001=1001∗1−5∗200

Esto significa que para los valores x=-200; y=1 será:
5∗(−200)−1001∗(−1)=15∗(−200)−1001∗(−1)=1

Así que la única solución (incongruente con otras soluciones) es x=−200x=−200
La cual es equivalente a 1001–200=8011001–200=801

Comprobemos:

5∗801=4005=4∗1001+15∗801=4005=4∗1001+1

Pero en otros casos puede haber varias soluciones incongruentes.
Por ejemplo, esta otra ecuación:

5x=20(mod100)5x=20(mod100)

MCD(5, 100) = 5 … y resulta que 5 divide a 20 así que habrá solución

5x−100y=205x−100y=20

x−20y=4x−20y=4

x=4+20yx=4+20y

Eso, dentro de las clases de congruencia mod 100 da varias soluciones diferentes:

y=0→x=4y=0→x=4
y=1→x=24y=1→x=24
y=2→x=44y=2→x=44
y=3→x=64y=3→x=64
y=4→x=84y=4→x=84

Comprobemos una cualquiera de ellas:
x=64x=64
5∗64=3205∗64=320
320(mod100)=20(mod100)320(mod100)=20(mod100)

En este caso no hay una única solución incongruente, sino 5 incongruentes:

4(mod100),24(mod100),44(mod100),64(mod100),84(mod100)4(mod100),24(mod100),44(mod100),64(mod100),84(mod100)

En general, el número de soluciones [mutuamente] incongruentes en la ecuación a*c = b (mod n) es igual al MCD (Máximo Común Divisor) de n y el coeficiente de la x, es decir, MCD(n,a). Y están separadas a la misma distancia: n/MCD(n, a)

Teorema de congruencia lineal - Wikipedia, la enciclopedia libre

Por ejemplo, una ecuación
6∗x=2(mod10)6∗x=2(mod10)
tendrá exactamente MCD(10,6)=2MCD(10,6)=2 soluciones
¿cuáles son?
Observamos que 6∗2=126∗2=12
Y habrá otra solución, porque hay 2.
Dado que la separación es 10/2=510/2=5
entonces la otra será 2+5=72+5=7

Comprobamos: 6∗7=426∗7=42 … efectivamente, termina en 2 así que es 2(mod10)2(mod10)
Los otros múltiplos de 6 (que no sean congruentes con el 2 o con el 7) no acaban en 2: 6*1 = 6; 6*3 = 18; 6*4=24; etc… Lógicamente, los congruentes con el 2 o con el 7 sí… Por ejemplo, el 12 también acaba en 2 (es congruente con el 2, en las equivalencias módulo 10): 6∗12=726∗12=72 … que acaba en 2. Otro ejemplo sería el 27, que también acaba en 7 (es congruente con el 7) : 6∗27=6∗20+6∗7=120+42=1626∗27=6∗20+6∗7=120+42=162 … que acaba en 2, efectivamente.