Pruebas de Teoría de Números relacionadas con gcd y mod

Question

¿Cómo se demuestra que la congruencia $ax \equiv b \pmod m$ tiene exactamente $d = (a,m)$ ¿Soluciones?

Sé que esta prueba es falsa pero no se me ocurre ningún contraejemplo ¿Alguna idea?

Answer 1

Dejemos que $(a,m)>1$ y $(a,m) \mid b$ . Definimos:

$$d=(a,m) , a_1=\frac{a}{d}, b_1=\frac{b}{d}, m_1=\frac{m}{d}$$

Entonces, $ax \equiv b \pmod m$ equivale a $a_1 x \equiv b_1 \pmod {m_1} (1)$

Como $(a_1,m_1)=1$ (1) tiene exactamente una solución. Por lo tanto, hay una solución $\xi_0$ de (1).

Y como $ax \equiv b \pmod m$ es equivalente a (1), las soluciones de $ax \equiv b \pmod m$ son los elementos del conjunto: $$[\xi]_{m_1}=\{ \xi | \xi_0 \equiv 0 \pmod {m_1}\}=\{qm_1+\xi_0 | q \in \mathbb{Z} \}$$

Ahora tenemos que comprobar cuántos de ellos no son equivalentes $\pmod m$ .

Lo tenemos:

$$q'm_1+\xi_0 \equiv q''m_1+\xi_0 \pmod m \Leftrightarrow q'm_1 \equiv q''m_1 \pmod {dm_1} \Leftrightarrow q' \equiv q'' \pmod d$$

Así que las soluciones $qm_1+\xi_0$ que no son equivalentes $\pmod m$ provienen de los valores de $q$ que no son equivalentes $\pmod d$ Tales valores de $q$ son elementos de un sistema completo de residuos módulo d, por ejemplo de éste: $ \{ 0,1, \dots , d-1 \}$ .

Concluimos que el $d=(a,m)$ números:

$$\xi_0, m_1+ \xi_0, \dots, (d-1)m_1+\xi_0$$

no son equivalentes $\pmod m$ soluciones de $ax \equiv b \pmod m$ y que cualquier otra solución es equivalente $\pmod m$ a uno de ellos.

Answer 2

Si $(a,m)\mid b$ entonces podemos dividir la congruencia por $(a,m)$ para conseguir $\frac{a}{(a,m)}x\equiv\frac{b}{(a,m)}$ mod $\frac{m}{(a,m)}$ .

Desde $(\frac{a}{(a,m)},\frac{m}{(a,m)})=\frac{(a,m)}{(a,m)}=1$ sabemos $\frac{a}{(a,m)}$ es una unidad mod $\frac{m}{(a,m)}$ por lo que podemos dividir para obtener

$$x\equiv \left(\frac{a}{(a,m)}\right)^{-1}\frac{b}{(a,m)}\mod{\frac{m}{(a,m)}}.$$

Cualquier residuo mod $m'$ se eleva hasta $\frac{m}{m'}$ residuos mod $m$ , por lo que hay $m/\hskip -0.06in \frac{m}{(a,m)}=(a,m)$ soluciones.

A la inversa, dada una solución, multiplicando ambos lados por $\frac{m}{(a,m)}$ rinde $m\mid b\frac{m}{(a,m)}\Rightarrow (a,m)\mid b$ por lo que esta condición es necesaria para que haya alguna solución.