Al [[Algoritmo de la división|dividir]] <math>a</math> entre <math>b</math> (números enteros), se obtiene un [[Cociente (aritmética)|cociente]] <math>q</math> y un [[Resto|residuo]] <math>r</math>. Demostremos Es posible demostrarprimero que el máximo común divisor de <math>a</math> y <math>b</math> es el mismo que el de <math>b</math> y <math>r</math>.: Sea c el máximo común divisor de <math>a</math> y <math>b</math>, como <math>a=bq+r</math> y <math>c</math> divide a <math>a</math> y a <math>b</math> divide también a <math>r</math>. Si existiera otro número mayor que <math>c</math> que divide a <math>b</math> y a <math>r</math>, también dividiría a <math>a</math> , por lo que <math>c</math> no sería el mcd de <math>a</math> y <math>b</math>, lo que contradice la hipótesis). Éste es el fundamento principal del algoritmo. También es importante tener en cuenta que el máximo común divisor de cualquier número <math>a</math> y <math>0</math> es precisamente <math>a</math>. Para fines prácticos, la notación <math>\mathrm{mcd}(a,b)</math> significa ''máximo común divisor de <math>a</math> y <math>b</math>''.
Según lo antes mencionado, para calcular el máximo común divisor de 2366 y 273 se puede proseguir de la siguiente manera:
