En este apartado se presentan las definiciones y teoremas básicos sobre divisibilidad de números enteros, la puerta de entrada al álgebra de congruencias.
Lo primero que hay que saber es la división entera con residuo (el algoritmo de la división en los enteros). Una vez apropiándose del concepto de residuo, el estudiante debe aprender a demostrar el lema fundamental de la teoría de números (o bien aprender a usarlo en la solución de problemas –la demostración puede esperar). Hay varias demostraciones, todas elementales pero la más básica (creo)es la que invoca el algoritmo de Euclides.
Del mismo algoritmo de Euclides se deriva el teorema que asegura la existencia de una combinación lineal de dos números para expresar su máximo común divisor.
Relacionado con el máximo común divisor (MCD) está el mínimo común múltiplo (mcm) de dos números y el teorema que asegura que el producto de los números es igual al producto MCD(mcm).
Teoremas adicionales se abordarán en los tópicos de divisibilidad.
Primero que nada, los objetos a estudiar son los números enteros, estos son:
0, 1, 2, 3, ... y también los negativos -1, -2, -3, ...
Todos estamos familiarizados con ellos, los hemos estudiado desde la escuela primaria y algunos incluso desde el preescolar. Por lo que podemos dar por conocidas sus siguientes propiedades:
Sean $a$, $b$ y $c$ tres números enteros cualesquiera entonces:
Queda como ejercicio convencerse de la veracidad de estos resultados. Para lo cuál es recomendable asignar valores a los números $a$, $b$ y $c$ y checar que los número elegidos satisfacen cada propiedad.
Ahora pasemos al concepto que será la propiedad principal de estudio en todo este libro, este es el concepto de divisibilidad.
Definición: Un entero $b$ es divisible por un entero $a \neq 0$ si existe un entero $x$ tal que $b=ax$ y se escribe así $a|b$. En el caso en que $b$ no sea divisible por $a$ se escribe $a \not | b$.
De manera reflexiva también se dice que $a$ divide a $b$.
Básicamente lo que significa es que el resultado de la división $b \div a$ es un entero. Pero definido como arriba, es claro que $a | 0$ para todo entero $a \neq 0$; pues en tal caso, $0 = a \cdot 0$.
Unos resultados menos triviales derivados de esta definición son los siguientes:
Teorema 1. Si $a$, $b$ y $c$ son tres enteros entonces son ciertas las siguientes afirmaciones:
- Si $a|b$ entonces $a | bc$ para todo entero $c$.
- Si $a|b$ y $b|c$ entonces $a|c$
- Si $a|b$ y $a|c$ entonces $a|(bx+cy)$ para todo $x,y$ enteros.
- Si $a|b$ y $b|a$ entonces $a= \pm b$.
- Si $a|b$ y $a,b >0$ entonces $a\leq b$.
Demostración del Teorema 1.
La demostración es muy sencilla y algo tediosa, así que sólo demostraré un par de ellas, las demás quedan como ejercicio.
Propiedad 2. Las hipótesis se traducen en que existe $x$ y existe $y$ tales que $b=ax$ y $c=by$. Sustituyendo $b=ax$ en $c=by$ obtenemos que $c=(ax)y$, es decir, $c=a(xy)$ por lo tanto $a| c$.
Propiedad 3. Nuevamente las hipotésis se traducen en que existen dos números, que llamaremos $p$ y $q$, tales que $b=ap$ y $c=aq$, luego, $$bx+cy=(ap)x+(aq)y = a(px+qy)$$ por lo que, $a$ divide a $bx+cy$.
Con esto hemos cubierto los conceptos básicos de divisibilidad.
Cuando dividimos un número $a$ entre otro $b$(digamos 5 entre 2) lo que hacemos es ubicar a entre dos términos de la sucesión: $0, b, 2b, \ldots$ (5 está ubicado entre 2(2) y 3(2) –y sobra 1). El cociente $q$ nos dice cuántas veces “cabe” $b$ en $a$, y el residuo $r$ es la distancia entre $qb$ y el número $a$.
.png)
El algoritmo de la división nos dice que, dados dos números $a$ y $b$, siempre es posible encontrar $q$ y $r$ de tal manera que $a=qb+r$, con $r$ un número entre $0$ y $b-1$. (Para 5 y 2, encontramos 2 y 1 tales que 5=2(2)+1.)
Lo que nos dice este resultado de la teoría de números ya lo sabíamos desde la escuela (de la clase de aritmética). La diferencia es que en teoría de números tenemos que usarlo teoréticamente, mientras que la habilidad para aplicarlo en la aritmética es totalmente mecánica (nunca nos habíamos tomado la molestia de averiguar porqué funciona puesto que siempre lo hemos aplicado de esa forma).
Si $ a $ divide a $ bc $ pero $ a $ es primo relativo [3] con $ b $ entonces $ a $ divide a $ c $.
Como $ a $ divide a $bc$, entonces $ a $ tiene que poder ser factorizado en $bc$. (Imagine el lector que trata de poner $bc$ en la forma $ka$.) Pero $ a $ no tiene factores en común con $ b $. Por lo tanto todos los factores de $ a $ están en $ c $. De aquí que podemos apartar $ b $ en $\frac{bc}{a}$, pues no aporta ningún factor para la cancelación.
Queda entonces
Es decir, $\frac{c}{a}=m$, como se quería.
A pesar de ser elemental, este resultado es poderoso. Y para comprender a cabalidad la demostración el lector que se inicia en estos temas de números necesita realizar varios ejemplos de aplicación. El significado del lema se obtiene con su uso.
La demostración presentada usa el siguiente argumento:
… $ a $ divide a $bc$….Pero $ a $ no tiene factores en común con $ b $. Por lo tanto todos los factores de $ a $ están en $ c $.”
Entonces, cuando se habla de factores se está hablando de los divisores primos un número. De hecho, en todo el tiempo se está pensando en el teorema fundamental de la aritmética:
Todo número puede escribirse de foma única como producto de sus factores, i.e, de la forma $p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_k^{\alpha_k}$.
Ahora bien, el lema fundamental es fundamental y es lema pues sirve de ayuda para probar el teorema fundamental. Por ello, la prueba presentada aqui, aunque es muy clara, no es la prueba correcta, pues se está usando el teorema fundamental que requiere del lema que se está probando con el teorema fundamental que requiere el lemma para su prueba :-?
Una prueba que evita usar el teorema fundamental es usando la Identidad de Bezout [4].
Como $ a $ y $ b $ son primos relativos, por la identidad de Bezout [4] sabemos que existen $ x $ y $ y $ enteros [5] tales que $ax+by = 1$. Multiplicando por $ c $ se tiene que:
Pero evidentemente $ a $ divide a $acx$ y por hipótesis divide a $ bcy$, en consecuenciea $ a $ divide a $acx+bcy$ que es $ c $. Y esto termina la prueba.
El conocimiento de este tema hace la diferencia entre un estudiante preparado para la olimpiada y uno que sólo domina las matemáticas escolares.
Este tema es fundamental en la olimpiadas de matemáticas, no conocerlo es como no haber estado en la olimpiada.
En el ámbito de la teoría de los números, la teoría de clases residuales ( o de modulos) es el segundo paso hacia el estudio de teoría de número.
[6]
El algoritmo de la división [7] es el que todos conocemos, es el que nos han enseñado desde la primaria para calcular divisones. Por ejemplo, la imagen de la izquierda muestra cómo hago yo para calcular la división 2841÷17.
En estas cuentas se pueden observar dos números importantes, el de arriba de la casita (el 167) y el de hasta abajo (el 2). Estos dos números son llamados repectivamente cociente y residuo.
También nos dijeron desde la primaria, cómo interpretar estos dos números. El cociente (en el ejemplo es el 167) es el número de veces que el divisor (el 17) cabe en el dividento (el 2841) y el residuo (el 2) es lo que sobra. Aritméticamente, esto se expresa así: $2841 = 17 \times167 + 2$.
Es importante señalar que el residuo obtenido en una división siempre es menor que el divisor [8] y pude ser cero en el caso que el divisor divida al dividendo [9].
Estas observaciones respecto al algoritmo de la división se pueden resumir matemáticamente así:
Dados dos números $n$ (dividendo) y $d$ (divisor), exiten dos únicos número enteros $q$ (cociente) y $r$ (residuo) tales que $n = d \cdot q + r$ y $0 \leq r< d$.
Ahora bien, ¿qué importancia tienen los residuos en la teoría de los números?
Pues una de las aplicaciones más importantes de los residuos es la siguiente equivalencia [10]
Dos números tienen el mismo residuo al dividerse por un número m si y sólo si su resta es divisible por m.
Veamos un ejemplo.
Como vimos en la sección anterior el número 2841 tiene residuo 2 al dividirse por 17. Y por otro lado, el número 36 también tiene residuo 2 al dividirse por 17. Entonces, por la afirmación del párrafo anterior, sabemos que 2841-36 será divisible por 17. Si lo desean, pueden hacer las cuentas.
Y de manera reciproca, 2841 - 2807 = 34 y 34 es divisible por 17 entonces, el residuo de 2807 deber ser el mismo que el de 2841. Por lo tanto, el residuo de 2807 es 2 al dividirse por 17.
Actividad. Busca un número que tenga el mismo residuo que 2008 al ser divididos por 15. Verifica que la resta efectivamente sea divisible por 15.
Ahora bien, la razón por la que la resta de dos números con el mismo residuo es divisible por el número es muy simple. Sean n y n' dos números con residuo r al dividirse por m, es decir, existe q y q' tales que:
De la ecuación se desprende inmediatamente que m divide a n - n'.
Para demostrar por completo la afirmación, faltaría demostrar que si m divide a n-n' entonces, n y n' tienen el mismo residuo.
Usando el algoritmo de la división sabemos que deben existir q, q', r y r' tales que:
\begin{eqnarray*} n &=& mq + r\\ n'& =&mq'+r' \end{eqnarray*}Además r,r' < m y r,r'≥0 . Ahora bien, sabemos que n-n' es divisibles por m, por lo que existe un número p tal que n-n' = mp.
Entonces, poniendo todo junto se observa:
\[mp= n-n' = (mq+r) - (mq' +r')\]
En consecuencia:
\[m(p-q+q') = r-r'\]
De donde se observa que m debe dividir a r-r'. Sin perdida de generalidad, supongamos que r≥r', es decir r-r'≥0. Como m > r ≥ r-r', se sigue que r-r' es un número entre 0 y m-1 (pues m es estrictamente mayor que r-r'). Pero el único número entre 0 y m-1 que es divisible por m es el cero, por lo tanto, r-r' = 0, es decir, r = r'. O lo que es lo mismo, n y n' tienen el mismo residuo al dividirse por m.
Como vimos anteriormente [11], la resta de dos números, del mismo residuo al dividir entre $m$ , es divisible por $m$ . Es por ello, que se inventó la notación de módulos:
| $a \equiv b$ $(\textrm{mod}$ $m) $ significa que a y b tienen el mismo residuo al dividirse por m. |
Esta notación se lee así: a congruente con b módulo m.
En principio puede parecer una definición sin sentido, pero la gran ventaja de esta notación es la clara forma de expresar los siguientes resultados tan valiosos:
| Propiedades | |
|---|---|
| $a \equiv b$ $(\textrm{mod}$ $m)$ y $c \equiv d$ $(\textrm{mod}$ $m) \Rightarrow$ $a+c \equiv b+d$ $(\textrm{mod}$ $m)$ | Conservación de la suma. |
| $a \equiv b$ $(\textrm{mod}$ $m)$ y $c \equiv d$ $(\textrm{mod}$ $m) \Rightarrow$ $ac \equiv bd$ $(\textrm{mod}$ $m)$ | Conservación del producto. |
Estos resultados se dejan como actividad para el lector. Pero, es mejor calentar primero con la siguientes propiedades básicas.
| Propiedades básicas | |
|---|---|
| $a \equiv a$ $(\textrm{mod}$ $m)$ | Reflexión. Un número siempre es congruente consigo mismo. |
| $a \equiv b$ $(\textrm{mod}$ $m) \Rightarrow$ $b \equiv a$ $(\textrm{mod}$ $m)$ | Simétrica. a congruente con b , es lo mismo que b congruente con a |
| $a \equiv b$ $(\textrm{mod}$ $m)$ y $b \equiv c$ $(\textrm{mod}$ $m) \Rightarrow$ $a \equiv c$ $(\textrm{mod}$ $m)$ | Transitividad. a congruente con b y este congruente con c, entonces a y c son congruentes. |
Cabe señalar, aunque caiga fuera de los objetivos de esta página, que las propiedades de la tabla anterior convierten a la congruencia en una relación de equivalencia.
Bueno, nada más por no dejar presentamos las pruebas de la preservación de la suma y del producto.
Deseamos probar:
\[a \equiv b \pmod{m} \textrm{ y } c \equiv d \pmod{m} \Rightarrow a+c \equiv b+d \pmod{m} \]
Entonces, por hipótesis, se tiene que a y b tienen el mismo residuo al dividir entre n y, de la misma manera, c y d. Traducido en términos algebraicos, esto significa que existe $ p $ y $ q $ tales que: $a-b = mp$ y $c-d = mq$. Ahora bien, al sumar estas dos últimas igualdades se obtiene que $(a-b) +(c-d) = mp+mq =m(p+q)$. Reagrupando, $(a+c) -(b+d) = m(p+q)$. Lo anterior significa que la resta de (a+c) y de (b+d) es divisible por m, o lo que es lo mismo, tienen el mismo residuo. Por lo tanto $a+c \equiv b+d$ $(\textrm{mod}$ $m)$.
Es un buen ejercicio dejar esta prueba para los alumno, pero se presenta aquí para aquél que deseé consultarla. Bueno, pues deseamos probra que:
| $a \equiv b$ $(\textrm{mod}$ $m)$ y $c \equiv d$ $(\textrm{mod}$ $m) \Rightarrow$ $ac \equiv bd$ $(\textrm{mod}$ $m)$ |
Entonces, sabemos que existen $ p $ y $ q $ tales que:
\begin{eqnarray}\label{equation_1} a-b&=&mp\\ \label{equation_2} c-d&=&mq \end{eqnarray}Ahora bien, multiplicando la ecuación (\ref{equation_1}) por $ c $ y la ecuación (\ref{equation_2}) por $ b $, se obtienen las siguientes igualdades:
\begin{eqnarray*} ac-bc &=& mpc\\ bc-bd &=& mqb \end{eqnarray*}Sumando ambas ecuaciones se obtiene que $ac -bd = m(pc+qb)$, es decir, $ac \equiv bd$ $(\textrm{mod}$ $m)$ .
Algunas consecuencias inmediatas de la preservación de la suma y del producto en las congruencias son las siguientes tres:
$a \equiv b \pmod{m}$ implica que $a + c \equiv b+c \pmod{m}$ para cualquier entero $c$.
Esto es evidentemente cierto, pues $c \equiv c \pmod{m}$ (propiedad reflexiva), y por la preservación de la suma llegamos al resultado.
$a \equiv b \pmod{m}$ implica que $c\cdot a \equiv c \cdot b \pmod{m}$ para cualquier entero $c$.
Es igual de evidente que la anterior, se usa la propiedad reflexiva junto con la preservación del producto.
$a \equiv b \pmod{m}$ implica que $a^{n} \equiv b^{n} \pmod{m}$ para cualquier entero $n \geq 0$.
Esta observación es menos obvia que la anteriores, pero es igualmente cierta y fácil de probar. Primero que nada, el caso $n=0$ es evidentemente cierto pues $a^n =1 = b^n$. Entonces, lo interesante es probar para $n \geq 1$,
Para la demostración formal debe procederse por inducción, pero en esta ocasión sólo vamos a convencernos de ello, analizando los pasos de dicha demostración.
Primero que nada, observemos que como $a \equiv b \pmod{m}$ y $a \equiv b \pmod{m}$ (sí... dos veces lo mismo), podemos multiplicar ambas congruencias por la regla de preservación del producto y obtener que $a^2 \equiv b^2 \pmod{m}$.
Podemos repetir esta regla del producto, pero ahora para $a^2 \equiv b^2 \pmod{m}$ y $a \equiv b \pmod{m}$, y de esta manera obtener que $a^3 \equiv b^3 \pmod{m}$.
Entonces, no es muy difícil convencerse que este proceso nos lleva a que $a^n \equiv b^n \pmod{m}$ para cualquier entero positivo $n$, como queríamos probar.
Ejemplo: Prueba que 6 divide a 20112000+5.
La solución con congruencias es muy fácil. Como queremos ver si algo es divisible entre 6 pues usaremos modulo 6.
Sin mucho trabjo se puede calcular el residuo de 2011, que es 1. Es decir:
Ahora bien, también se tiene la siguiente congruencia:
¡Pero si es la misma! 8-o
Sí es la misma, pero lo importante es que viendola escrita dos veces queda claro que se pueden usar las propiedades de conservación del producto (sólo que a=c y b=d). Entonces, por la conservación del producto se tiene que:
O lo que es lo mismo:
Ahora, si aplicamos nuevamente la conservación del producto se obtiene:
Que es lo mismo que:
De esto se observa que podermos seguir así hasta probar que:
Por último, se sabe que:
Y usando la conservación de la suma se obtiene:
Peo como 6 es congruentre con 0 modulo 6, entonces se tiene que:
O lo que es lo mismo: $2011^n + 5 $ es divisble por 6 para todo valor de n.
Una aplicación clásica de los módulos es en la prueba de los criterios de divisibilidad, y en particular en la prueba de los criterio del 9 y del 11.
Bueno, para entender con exactitud los criterios de divisibilidad hay que recordar el significado de la notación decimal que usamos hoy en día. Que no es más que la notación decimal es posicional y de base 10. Esto se ve en la secundaria (y también algo en la primaria), para los que no se acuerden, esto significa únicamente que, por ejemplo, $$2457 = 2 \times 10 ^3 + 4 \times 10^2 + 5 \times 10 +7$$
En términos más abstractos, pero es exactamente lo mismo, se dice así:
Teorema. Para cualquier entero positivo $N$ existe una sucesión (lista) finita de enteros única $a_0, a_1, a_2, \ldots, a_n$ entre 0 y 9, tales que $$N = a_n10^n + a_{n-1}10^{n-1} + \cdots + a_110 + a_0$$,
El teorema, en otras palabra, dice que todo entero positivo se puede escribir en base 10.
Una función polinomial, es una función de la forma $f(x) = c_nx^n+c_{n-1}x^{n-1} + \cdots + c_1x+c_0$.
Por ejemplo, $p(x) = 5x^2+2x+9$ es una función polinomial de grado 2. No es muy difícil de convencerse de que $p(10) = 529$.
De esta manera, si $N = a_n10^n + a_{n-1}10^{n-1} + \cdots + a_110 + a_0$, es la notación decimal de $N$, entonces, $N=f(10)$ donde $f(x) =a_nx^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0 $
Ahora bien, recordemos que si $b \equiv d \pmod{m}$ entonces $b^k \equiv d^k \pmod{m}$ para todo entero positivo $k$, por lo que, $a_kb^k \equiv a_kd^k \pmod{m}$, y sumando todas estas congruencias obtenemos que $$a_nb^n + a_{n-1}b^{n-1} + \cdots + a_1b + a_0 \equiv a_nxd^n + a_{n-1}d^{n-1} + \cdots + a_1d + a_0 \pmod{m}$$ Que es lo mismo que decir que $$f(b) \equiv f(d) \pmod{m}.$$ Hemos probado entonces que:
Teorema. Si $b\equiv d \pmod{m}$ entonces $f(b) \equiv f(d) \pmod{m}$ para toda función polinomial $f$ con coeficientes enteros.
Como $10 \equiv 1 \pmod{9}$, entonces, $f(10) \equiv f(1) \pmod{9}$.
Si $N = a_n10^n + a_{n-1}10^{n-1} + \cdots + a_110 + a_0$ es la expansión decimal del número N, entonces, $f(10)=N$, y $f(1) = a_0+a_1+ \cdots a_n$ donde $f(x) =a_nx^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0 $ . Por lo tanto, $$N \equiv a_0+a_1+ \cdots a_n \pmod{9}.$$
Ejemplo. Con el número $N= 12756$ se tiene que $12756 \equiv 1+2+7+5+6 \pmod{9}$, es decir, $22756 \equiv 21 \equiv 2+1 \equiv 3 \pmod{9}$. Por lo que el residuo de dividir a 12, 756 entre 9 es 3.
Ahora bien, en este ejemplo se ve que $9$ no divide a 12,756. Pero como 3 divide a 9, podemos cambiar el módulo por módulo 3. Esto nos da que $12756 \equiv 0 \pmod{3}$, por lo tanto, 3 sí divide a 12,756.
Como $10 \equiv -1 \pmod{11}$ podemos ahora usar el mismo argumento y obtener que si $N = a_n10^n + a_{n-1}10^{n-1} + \cdots + a_110 + a_0$ entonces $N \equiv a_0 - a_1 +a_2-a_3 + \cdots+ (-1)^{n}a_n \pmod{11}$
Ejemplo. Con el número $N= 12756$ se tiene que $12756 \equiv 6-5+7-2+1 \equiv 7 \pmod{11}$, por lo que el residuo de dividir 12,756 entre 11 es 7.
En los ejemplos, se observa que estos criterio no sólo nos determinan si el número es o no divisible por el divisor en cuestión, si no que además nos ayuda a encontrar el residuo de la división sin tener que hacer la división.
Pare motivar la definición que veremos más adelante resolvamos primero los siguientes problema ejemplos.
Problema 1. Encuentra los números $x$ que satisfacen la congruencia $2x \equiv 1 \pmod{5}$.
Solución. Como sabemos $x \equiv 0,1,2,3 \textrm{ o } 4 \pmod{5}$ para cualquier número $x$. Entonces, al multiplicar por 2 obtenemos que $2x \equiv 0, 2,4,1 \textrm{ o } 3 \pmod {5}$, en consecuencia, sólo cuando $x \equiv 3 \pmod{5}$ se satisfacerá la congruencia $2x \equiv 1 \pmod{5}$. Esto nos determina por completo las soluciones, que serán los números $x$ que dejan residuo 3 al dividirse entre 5.
Problema 2. Encuentra los números $x$ que satisfacen la congruencia $2x \equiv 4 \pmod{6}$.
Solución. De manera similar, sabemos que $x \equiv 0,1,2,3, 4, \textrm{ o } 5 \pmod{6}$ para todo número $x$. Lo que significa que $2x \equiv 0, 2,4,0, 2, \textrm{ o } 4 \pmod {6}$, en consecuencia, las únicas posibilidad se dan cuando $x \equiv 2 \textrm{ o } 5 \pmod{6}$. Entonces las soluciones son los números que dejan residuo 2 o 5 al dividirse entre 6.
Problema 3. Encuentra los números $x$ que satisfacen la congruencia $2x \equiv 3 \pmod{6}$.
Solución. Por el análisis del problema anterior, los residuos posibles de $2x$ son sólo 0, 2 y 4. Entonces esta ecuación no tiene solución.
Al leer con cuidado estos ejercicios, se observa que para dar las soluciones de una ecuación de la forma $ax \equiv b \pmod{m}$ basta con encontrar todos los residuos módulo $m$ que satisfacen la ecuación.
Por cuestiones prácticas de argumentación en demostraciones, es conveniente permitir que los residuos sean dados por números no necesariamente menores al módulo, por ejemplo, en lugar de decir que 2 y 5 son las soluciones de la ecuación $2x \equiv 4 \pmod{6}$, podríamos decir, que 8 y -1 son las soluciones de esta ecuación, pues finalmente $8 \equiv 2 \pmod{6}$ y $5 \equiv -1 \pmod{6}$.
Más formalmente, decimos que $x_1, x_2, \ldots, x_k$ son las soluciones de la ecuación $ax \equiv b \pmod{m}$, si se satisface que:
La primera condición dice que los números $x_1, x_2, \ldots, x_k$ son soluciones de la ecuación y la segunda que cualquier otra solución es congruente a una y sólo una de éstas.
Bueno, ahora pasaremos al teorema principal
Teorema. La ecuación diofantina $ax \equiv b \pmod{m}$ tiene solución si y sólo si $(a,m) | b$. Más aun, si $(a,m) | b$ entonces la ecuación tendrá $(a,m)$ soluciones no congruentes.
Demostración: Supongamos que existe solución $x_0$, entonces $ax_0 -b$ será un múltiplo de $m$, es decir, $ax_0 -b = km$ para algún entero $k$. Luego tenemos que $ax_0 - ḱm = b$ y de aquí se sigue que $(a,m) | b$.
Ahora probemos en la otra dirección, supongamos que $(a,m) | b$ y tratemos de demostrar que existe solución. Llamemos $g = (a,m)$ y por la identidad de Bezout [12] existen enteros $x_0$ y $y_0$ tales que $ax_0 + my_0 = g$. Como $b$ es múltiplo de $g$ tendremos que existe $k$ tal que $b = kg$, entonces multiplicando la expresión del enunciado anterior por $k$ tendremos que: $$a(kx_0) + m(k y_0) = b.$$
Aplicando módulo $m$ tendremos que $a(kx_0) \equiv b \pmod{m}$ y por lo tanto $kx_0$ es solución de la ecuación de $ax \equiv b \pmod{m}$.
Esto termina la primera parte, ahora sólo nos falta demostrar que son exactamente $(a,m)=g$. Denotemos con $x_1$ una solución cualquiera, demostraremos primero que $x_1 + (m/g)*t$ con $t=0,1, \dots, g-1$ son todas las solución. Efectivamente son soluciones, pues $a(x_1+(m/g)t) = ax_1 + (a/g)mt \equiv ax_1 \equiv b \pmod{m}$.
Ahora verifiquemos que cualquier solución tiene que tener dicha forma. Denotemos con $x$ una solución genérica, deberá satisfacer que $ax \equiv ax_1 \pmod{m}$, es decir que, $a(x_1 -x) \equiv 0 \pmod{m}$. Ahora, dividiendo entre $g$ obtenemos $a/g(x_1 -x) \equiv 0 \pmod{m/g}$. Como $a/g$ y $m/g$ son primos relativos (pues les quitamos el máximo común divisor) , podemos cancelar $a/g$ y resulta entonces que $x \equiv x_1 \pmod{m/g}$. La anterior ecuación es equivalente a decir que $x$ tiene la forma $x = x_1 + t(m/g)$ para alguna $t$
El parámetro $t$ se debe reducir módulo $g$, pues $t \equiv t_0 \pmod{g}$ si y sólo si $x_1 + t(m/g) \equiv x_1 + t_0(m/g) \pmod{m}$. Ésto termina la prueba
Enlaces:
[1] http://matetam.homelinux.org/dokuwiki/doku.php?id=numeros:temas:divisibilidad:algoritmo_de_la_division#fn__1
[2] http://matetam.homelinux.org/dokuwiki/doku.php?id=numeros:temas:divisibilidad:algoritmo_de_la_division#fnt__1
[3] https://www.matetam.com/glosario/definicion/primos-relativos
[4] https://www.matetam.com/glosario/teorema/identidad-bezout
[5] https://www.matetam.com/glosario/definicion/numeros-enteros
[6] http://matetam.homelinux.org/dokuwiki/lib/exe/detail.php?id=numeros%3Atemas%3Adivisibilidad%3Acongruencias&cache=cache&media=numeros:temas:topicos_sobre_divisibilidad:division.png
[7] https://www.matetam.com/glosario/definicion/algoritmo-division-inexacta
[8] https://www.matetam.com/glosario/definicion/divisor
[9] https://www.matetam.com/glosario/definicion/dividendo
[10] http://www.matetam.homelinux.org/dokuwiki/doku.php?id=glosarios:logica:index#equivalencia
[11] https://www.matetam.com/de-consulta/books/teoremas-basicos-divisibilidad/congruencias-modulos
[12] https://www.matetam.com/../../../../../../glosario/teorema/identidad-bezout