¿Cómo resolver ecuaciones de grupos congruentes?

[Palabras clave] El texto del teorema residual del módulo de grupos congruentes:

Teorema 1. (Teorema de Sun Tzu) Supongamos m, m... .. .. m es k dos números positivos relativamente primos, 12k

m=m1m2...mk, m=miMi, i=1, 2,...,k, entonces La solución de los grupos congruentes x≡b1 (modm1), x≡b2 (modm2),..., x≡bk (modmk) es:

x≡M`

1M1b1 M`

2M2b2 ... M`

kMkbk(modm),...(2),

donde M`

iM≡1 ( modmi), i=1, 2,...,k.

Prueba: (mi, mj) = 1, i ≠ j es decir (Mi, mi) = 1, así se puede ver del teorema §1 de que para cada Mi, existe un M`

i, tal que M`

iMi≡1 (modmi).

Por otro lado, m=miMi, entonces mj|Mi, i≠j, entonces M

j?1k`jMjbj≡M`iMibi≡bi (mod mi), esta es la solución de (1).

Si x1, x2 son dos enteros cualesquiera adecuados para (1), entonces

x1 ≡ x2 (mod mi), i = 1, 2,...,k ,

Dado que (mi, mj) = 1, entonces x1 ≡ x2 (mod m), y por lo tanto x1 ≡ x2 (mod m), entonces la solución de (1) es solo (2) FIN 1 Lema 2 Sea el conjunto congruente principal dado:

2/6

X ≡ b1 (mod m1)

X ≡ b2 (mod m2)

...

X ≡ bk (mod mk)

(i) Tome m=[m1, m2, m3,.... .. .mk] , entonces el conjunto de congruencia dado tiene solución, si:

(mi, mj)|(bi?bj)1?i≠j?k,

Si hay una solución , el número de soluciones módulo m es 1 (m1m2...mk no son necesariamente mutuamente excluyentes)

(ii) Encuentre un conjunto de números positivos m1`, m`2, ..mk` que satisfaga. m`

j|mj, 1?j?k, y m1`, m`2,...mk` son primos relativos,

m= m1`m`2mk `

(ⅲ) Si el conjunto congruente

X≡bj(mod mj)1?j?k

tiene solución, entonces su solución es la igual que el grupo congruente

② Supongamos que cuando k = n, si se cumplen las condiciones dadas, el grupo de congruencia compuesto por las n congruencias correspondientes tiene una solución. Cuando k = n 1, el grupo de congruencia dado El grupo restante es:

X≡bi (modmi) i=1, 2, ...., n, n 1

Y las condiciones (mi, mj)|(bi ?bj )i ,j=1,2,...,n,n 1

Necesidad: Probamos que bajo estas condiciones, este grupo congruente tiene solución.

Como (mn, mn?1)|(bn, bn?1).

Entonces X≡bn(modmn) X≡bn?1(modmn?1) tiene una solución

Supongamos que x=ck es un número entero adecuado para estas dos congruencias. Todos los números enteros son adecuados. pues se puede representar por

X ≡cn(mod[mn, mn?1])

. Considere las siguientes n ecuaciones congruentes asociadas

X≡bi(modmi) i=1, 2,...,n-1

X≡cn(mod[mn, mn? )

3/6

Para este conjunto de congruencias, tenemos (mi, mj)|(bi?bj)i, j=1, 2,... ., n-1

Y cn ≡ bn(modmn)

cn ≡ bn?(modmn?1)

bi ≡ bn(mod(mi, mn) )

bi ≡ bn?1(mod(mi, mn?1))

Por lo tanto bi ≡ cn(mod (mi, mn))

bi ≡cn?1(mod(mi，mn?1))

Entonces bi≡cn(mod[(mi，mn)，(mi，mn?1)])

y [(mi, mn), (mi, mn?1)]=(mi, [mn, mn?])i=1, 2, .... ..., n-1

De esta manera, el nuevo conjunto congruente anterior satisface las siguientes condiciones:

bi≡bj(mod(mi,mj))i, j=1, 2,..., n-1

bi≡cn(mod(mi,[mn,mn?1])) i=1, 2,..., n-1

Por lo tanto, según la inducción matemática, tenemos Se puede suponer que este grupo congruente tiene solución y su solución es la misma que la del grupo congruente original. Entonces, cuando n=k+1, el grupo congruente original tiene solución y la proposición es verdadera

(ⅱ, ⅲ) Demuestre en el proceso de (ⅰ) 2 Ejemplos: 1. Han Xin ordenó a los soldados: Si están dispuestos en cinco filas, habrá una persona en la última fila. Si están dispuestos en seis filas, habrá cinco personas en la última fila. están dispuestos en siete filas, habrá cuatro personas en la última fila. Si están dispuestos en once filas, habrá cuatro personas en la última fila. Hay diez personas en la última fila. . Solución: De la pregunta, sabemos que x≡1 (mod 5), x≡5 (mod 6), x≡4 (mod 7), x≡10 (mod 11)

En este momento , m1= 5, m2=6, m3=7, m4=11 son primos entre sí y pueden resolverse mediante el teorema de Sun Tzu:

En este momento, m=5*6*7*11=2310 ,

M1=6*7*11=462,

M2=5*7*11=385,

M3=5*6*11= 330,

M45*6*7=210.

M`

iMi ≡ 1 (modmi), i=1, 2, 3, 4

Obtener M`

1 =3 M`

2=1 M3`=1 M4`=1,

4/6

Por lo tanto x ≡ 3*462*1 1* 385*5 1*330*4 1*210*10 ≡ 6731 ≡ 2111 (mod. 2310).

3

2. Resuelve el conjunto congruente x ≡ 3 (mod 8)

x ≡ 11 (mod 20)

x ≡ 1 (mod 15) <. /p>

Solución: Dado que m1 = 8, m2 = 20, m3 = 15, y no son mutuamente excluyentes, no se puede utilizar el teorema de Sun Tzu, pero se debe utilizar el teorema

2 para resolver

2 p>

(m1.m2) = (8, 20) = 2 2|8 = b2-b1

(m2, m3) = (20, 15 ) = 5 5|10 = b2 -b3

(m1, m3) = (8, 15) = 1 1|2 = b1-b3

Entonces el grupo congruente tiene un solución.

m1=8=23, m2=20=22*5, m3=15=3*5,

m=[m1, m2, m3,...mk] =2*5*3=120 3

Toma m`

1=23=8, m`

2=5, m`

3= 3

Obviamente m`

j|mj, j=1, 2, 3. Y m`

1, m`

2, m`

3 son primos relativos, entonces m=m`1m`

2m`

3

Congruencia y congruencia original

x ≡ 3(mod 8)

x≡11(mod 5)

x≡1(mod 13 )

Solución congruente, ya que m`

1=8, m`

2=5, m`

3= 3 es primo relativo, que se puede resolver según el teorema de Sun Tzu

m=2*5*3=120, 3

M1=5*3=15,

M2 =8*3=24,

M3=58*5=40,

M`

iMi≡1(modmi), i= 1,2 , 3, 4

Entonces M`

1=-1 M`

2= -1 M3`=1

x ≡(-1)*15*3 (-1)*24*11 1*40*1≡-29≡91(mod120).