Una de las primeras propiedades que se presentan cuando aprendemos divisibilidad es la siguiente:
Si $d$ es divisor de $a$ y $b$, entonces $ d | ax + by$ para cualesquiera enteros $x,y$.
A menos que se diga lo contrario, supondremos que estamos usando enteros mayores a cero. La propiedad citada lo que nos dice es que, si $d$ es un divisor común de $a$ y $b$ entonces $d$ es divisor de cualquier combinación lineal de ellos. Hemos hablado de dos conceptos muy importantes de los que se profundizará más.
Los divisores en común de dos enteros toman importancia cuando hablamos del máximo común divisor de ellos, para $a$ y $b$ su el mayor de sus divisores en común se denota como mcd(a,b) y a veces simplemente como (a,b). Aquí mismo en MaTeTaM pueden consultar su definición.
Una gran manera de relacionar el divisor común con las combinaciones lineales de dos enteros es '' La identidad de Bezout''. La cual, afirma que existen $x,y$ tal que
$$ax+by = mcd(a,b)$$
Esta identidad y su demostración, la pueden ver aquí también.
Otra manera de relacionar el mcd con las combinaciones lineales es el algoritmo de Euclides. Que básicamente es el siguiente teorema
El máximo común divisor de dos números enteros positivos $a$ y $b$ , con $a>b>0$ , coincide con el máximo común divisor de $b$ y $r$ , siendo $r$ el resto que se obtiene al dividir $a$ entre $b$.
Demostración:
Sean $d=mcd(a,b)$ y $t=mcd(b,r)$. Vamos a demostrar que $d=t$ .
Por definición de máximo común divisor, se tiene que $d$ es un divisor tanto de $a$ como de $b$ . Por tanto $a=a_1d$ y $b=b_1d$ .
Por otro lado, por el algoritmo de la división se tiene que
$a=bq+r$ , con $r < b$
Por tanto $d$ es un divisor de $r$. Como ya teníamos que también es un divisor de $b$ entonces debe dividir a su máximo común divisor, esto es, $d$ es un divisor de $t$.
Por otro lado, $t$ es un divisor tanto de $b$ como de $r$. Por ello se tiene que $b=pt$ y $r=st$ . Sustituyendo estas dos igualdades en (1) obtenemos lo siguiente:
$$ a= ptq +st = (pq+s)t$$
Por tanto $t$ es un divisor de $a$ . Como también lo era de $b$ debe ser un divisor de su máximo común divisor, es decir, $t$ es un divisor de $d$.
Como 
Este teorema y su demostración lo tomé de la página gaussianos, gracias a ellos por su gran contenido.
Daré unas propiedades del mcd, en los comentarios pueden preguntar sobre su demostración de alguna de ellas:
* Si $m$ es un entero entonces $(ma,mb) = m(a,b)$
*Si $d$ es un divisor común de $a,b$ entonces $(\frac{a}{d},\frac{b}{d}) =\frac{(a,b)}{d}$ en particular si $d=(a,b)$ entonces $(\frac{a}{d},\frac{b}{d})=1$
*Si $(a,m)=(b,m) = 1$ entonces $(ab,m) = 1$
*Para cualquier entero $x$ se tiene que $(a,b+ax)$.
Una definición importante que se desprende de todo esto son los números coprimos. Decimos $a$ y $b$ son coprimos si $(a,b)=1$. Estos toman su importancia por el siguiente teorema:
Si $c | ab$ y $c$ es coprimo con $a$ entonces $c|b$
Este teorema se puede encontrar con demostración en Wikipedia como ''Lema de euclides'' .
Daré las soluciones a algunos problemas que sólo ocupen estos conceptos de divisibilidad y combinaciones lineales.
Problema 1. Demuestra que la siguiente fracción es irreducible para todo $n$ natural:
$$\frac{21n +4}{14n+3}$$
Solución: El sea $d$ el máximo común divisor del numerador y denominador, entonces $d$ debe dividir a $3(14n+3) - 2(21n+4) = 1$ por lo tanto $d=1$ y la fracción es irreducible.
Problema 2. Si la suma de dos fracciones irreducibles es un entero, entonces tienen el mismo denominador.
Solución: Sean $\frac{a}{b}$ y $\frac{c}{d}$ las fracciones del enunciado entonces
$$\frac{ad + bc}{bd}$$ es un entero por lo que $b| ad + bc$ por tanto $b | ad$ pero $(a,b) = 1$ pues por hipotésis las fracciones estaban reducidas. Esto concluye a que $b|d$ de manera análoga $d| ad+bc$ lo que implica que $d|b$ la única manera de que dos números se dividan el uno al otro, es que sean iguales.
Problema 3. Para cada $n$ definimos como $A_n$ el número formado por $n$ 1's por ejemplo $A_5 = 11111$. Encuentra el máximo común divisor de $A_{667}$ y $A_{2001}$
Vamos aplicar el algoritmo de euclides:
$(A_{667}, A_{2001}) = (A_{667},A_{2001} - A_{667})$
$= (A_{667}, A_{1334}\times 10^{667}) = (A_{667},A_{1334})$
$= (A_{667},A_{1334} - A_{667}) = (A_{667},A_{667}\times 10^{667})$
$= (A_{667},A_{667}) = A_{667}$
Para eliminar los $10^{667}$ hemos ocupado que (ab,c)=(b,c) si (a,c)=1.
Problema 4. En cada lado de un pentágono regular se escribe un número natural de manera que números escritos en lados adyacentes sean coprimos, y números que no sean adyacentes no sean coprimos, describe los enteros que no pueden ser puestos sobre el pentágono
Solución: Todos los enteros $n$ que sean potencias de algún número primo no pueden ser puestos sobre el pentágono.
Cualquier duda la pueden dejar en los comentarios y gusto será respondida con la mayor claridad posible. A continuación dejaré una lista de problemas que también pueden intentar y escribirnos su soluciones.
Problemas:
1. Hallar todos los enteros positivos $n$ tal es que
$$ (n,1) + (n,2) + \cdots + (n,n) = 3n - 3$$
2. Demuestra que la siguiente fracción es irreducible para todo $n$ natural
$$\frac{n^2 +n-1}{n^2 +2n}$$
3. La sucesión infinita $a_1,a_2, \dots$ cumple que $(a_i,a_j)=(i,j)$ si $i$ es distinto de $j$. Muestra que $a_i = i$ para toda $i$.
4. Determina todos lo conjuntos finitos no vacíos $S$ tal es que
$$\frac{i+j}{(i,j)} $$ es un elemento de $S$ si $i,j$ pertenecen a $S$.
Definimos [a,b] como el mínimo común múltiplo de $a$ y $b$
5. Demuestra que $(a,b)[a,b] = ab$
6. Encuentra todos los enteros $a,b$ tal es que $(a,b) + [a,b] = a+b$
7. Encuentra el mcd de los siguientes números $2^{20}-1$ y $2^{15}-1$
8. El número 125 puede ser expresado como suma de algunos números mayores que uno y tal que que cualesquiera dos de ellos son coprimos. Determina la máxima cantidad de términos que esta suma puede tener.
9. Demuestra que entre cualesquiera 14 enteros consecutivos siempre hay 6 números tal que cualesquiera dos de ellos son coprimos.
Saludos
germán