Simplificación de ecuaciones de congruencia difíciles

Question

$$2842x \equiv 1547 \pmod{103}$$

¿Cómo puedo simplificar esto? $GCD(2842,103)=1$ así que mi opinión sería dividir la ecuación por 7, que es la $GCD$ de 2842 y 1547. Así que:

$$406x \equiv 221 \pmod{103}$$

Vale, ahora parece un poco más sencillo.

Sin embargo, he oído que el $61x \equiv 2 \pmod{103}$ es igual a la ecuación superior aquí. ¿Pero cómo es posible? ¿Lo es? Y si es así, ¿por qué es así?

Answer 1

Como $2842\equiv61\pmod {103}$

y $1547\equiv2\pmod {103}$

---

Alternativamente, $2847x\equiv1547\pmod{103}$ $\implies 2847x=1547+103y$ para algún número entero $y$

Como $2842=27\cdot103+61$ y $1547=15\cdot103+2$

podemos escribir $(27\cdot103+61)x=15\cdot103+2+103y$

$\implies 61x=2+103(y-27x-15)\equiv2\pmod {103}$ como $y-27x-15$ es un número entero como $x,y$ son números enteros