¿Cuál es el método general para encontrar la solución entera positiva x, y para [math] ax + por \ equiv c \ pmod {ab} [/ math] que minimiza [math] x [/ math]?

Answer 1

La congruencia [matemática] ax + por \ equiv c \ pmod {ab} [/ matemática] implica las dos congruencias

[math] ax + by \ equiv c \ pmod {a} [/ math] y [math] ax + by \ equiv c \ pmod {b} [/ math].

Estas congruencias se reducen a [math] en \ equiv c \ pmod {a} [/ math] y [math] ax \ equiv c \ pmod {b} [/ math]. Cada uno tiene solución si y solo si [math] \ gcd (a, b) \ mid c [/ math].

Suponga que [math] g = \ gcd (a, b) \ mid c [/ math]. Entonces [math] ax \ equiv c \ pmod {b} [/ math] implica [math] a ^ {\ prime} x \ equiv c ^ {\ prime} \ pmod {b ^ {\ prime}}, [/ math ] donde [matemática] a ^ {\ prime} = \ frac {a} {g} [/ math], [math] b ^ {\ prime} = \ frac {b} {g} [/ math] y [ matemáticas] c ^ {\ prime} = \ frac {c} {g} [/ matemáticas]. Como [math] \ gcd \ big (a ^ {\ prime}, b ^ {\ prime} \ big) = 1 [/ math], podemos encontrar enteros [math] r [/ math], [math] s [ / math] tal que [math] ra ^ {\ prime} + sb ^ {\ prime} = 1 [/ math]. Multiplicar ambos lados de la congruencia [matemáticas] a ^ {\ prime} x \ equiv c ^ {\ prime} \ pmod {b ^ {\ prime}} [/ matemáticas] por [matemáticas] r [/ matemáticas] da [matemáticas ] x \ equiv rc ^ {\ prime} \ pmod {b ^ {\ prime}} [/ math].

Por lo tanto, el conjunto de soluciones para [math] ax \ equiv c \ pmod {b} [/ math] es [math] \ {x_0, x_0 + b ^ {\ prime}, x_0 + 2b ^ {\ prime}, \ ldots , x_0 + (g-1) b ^ {\ prime} \} [/ math], donde [math] x_0 \ equiv rc ^ {\ prime} \ pmod {b ^ {\ prime}}. [/matemáticas]

El menos positivo [matemático] x [/ matemático] es [matemático] x_0 [/ matemático], a menos que [matemático] x_0 = 0 [/ matemático], en cuyo caso el menos positivo [matemático] x [/ matemático] es [matemático ] b ^ {\ prime} [/ math]. [matemáticas] \ blacksquare [/ matemáticas]