Congruencias con ecuaciones

Se trata de hallar los valores de x que hacen que la función axⁿ + a₁x^n-1 + ... + a_n sea congruente con 0 módulo m.

x⁵ + x  + 1 congruente con 0 módulo 7

Tenemos que buscar las soluciones entre los números 0, 1, 2, 3, 4, 5 y 6, que son los posibles restos.

De estos números, sólo el 2 y el 4 hacen que la ecuación sea congruente con 0 módulo 7.

Congruencias en ecuaciones de primer grado

Hallar los valores de x para los que la función 111x es congruente con 75 módulo 321.

Esta congruencia sólo es posible si el máximo común divisor de 111 y 321 divide a 75.

El máximo común divisor de 111 y 321 es 3, por lo tanto, tiene solución.

Además como 75 es múltiplo de 3 hay 3 soluciones.

Dividiendo todo por 3 nos queda: 37x congruente con 25 módulo 107.

Dividiendo 107 entre 37 nos queda un cociente de 2 y un resto de 33.
Dividiendo 37 entre 33 nos queda un cociente de 1 y un resto de 4.
Dividiendo 33 entre 4 nos queda un cociente de 8 y un resto de 1.
Dividiendo 4 entre 1 nos queda un cociente de 4 y un resto de 0.

A partir de los cocientes obtenemos:

Cocientes:           2        1          8         4
                   1      2        3        26      107

Las soluciones viene dadas por la fórmula:

x == (-1)^{n - 1} P_{n - 1} b (mod m)

En nuestro caso n = 4, Pn - 1 = 26, b = 25.

x == - 26.25 == - 8 == 99 (mod 107)

Las soluciones son: x == 99, x == 99 + 107 y x == 99 + 2.107 (mod 321)

Sistemas de congruencias de primer grado

Sea el sistema:

x == b₁ (mod m₁)
x == b₂ (mod m₂)
..........................
x == b_n (mod m_n)

Siendo los módulos primos entre sí.