Algoritmo de Euclides tradicional Al dividir a {\displaystyle a} entre b {\displaystyle b} (números enteros), se obtiene un cociente q {\displaystyle q} y un residuo r {\displaystyle r} . Es posible demostrar que el máximo común divisor de a {\displaystyle a} y b {\displaystyle b} es el mismo que el de b {\displaystyle b} y r {\displaystyle r} (Sea c el máximo común divisor de a {\displaystyle a} y b {\displaystyle b} ,.Como a=bq+r y c divide a a {\displaystyle a} y a b {\displaystyle b} divide también a r.Si existiera otro número mayor que c que divide a b y a r, también dividiría a a , por lo que c no sería el mcd de a {\displaystyle a} y b {\displaystyle b} , 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 a {\displaystyle a} y 0 {\displaystyle 0} es precisamente a {\displaystyle a} . Para fines prácticos, la notación m c d ( a , b ) {\displaystyle \mathrm {mcd} (a,b)} significa máximo común divisor de a {\displaystyle a} y b {\displaystyle b} .