定义一 任给两个整数a,b，其中b≠0, 如果存在一个整数q使得等式 a=bq 成立，则称b整除a,记作b|a 。此时称b为a的约数，a为b的倍数。
定理二 设a,b是两个整数，其中b>0，则存在唯一的整数q及r，使得a=bq+r,0≤r<b成立。
定义三 设a1,a2,…,an 是n个不全为零的整数，若整数d是它们之中每一个数的约数，那么d就叫a1,a2,…,an一个公约数，整数a1,a2,…,an的公约数中最大的一个叫最大公约数，记作（a1,a2,…,an ），若（a1,a2,…,an ）=1，则称a1,a2,…,an 互素。
定理四 若a|bc,(a,b)=1,则a|c.
定理五 （a1,a2,…,an ）=(（a1,a2,…,an-1 ）an).
例:
在中国古代就有一个很好的算法来计算a,b的最大公约数（a,b）,称为辗转相除法，在西方称为Euclid(欧几里得)算法。下面通过计算（1397，2413）来阐述这一算法。
首先，我们用这两个数1397和2413中两个数中小的去除大的，得商为1，余数为1016。将原来两个数中大的2413扔掉，将1397作为大数，将余数1016作为新的小数。重复上面的过程：用1016去除1397，得商为1，余数为381。扔掉1397，将381作为除数，1016作为被除数。用381去除1016，得商为2余数为254，扔掉1016，用254 去除381，得商为1 ，余数为127，再扔掉381，用127去除254，发现能整除，于是127就是最大公约数。整个计算过程为：
2413=1397*1……1016，
1397=1016*1……381，
1016=381*2……254，
381=254*1……127，
254=127*2……0，
所以（1397，2413）=127。
为什么这样求出是就是最大公约数呢？下面对a,b为正整数（a>b）的情形给出说明。根据定理二，商q和余r数满足
a=bq+r,且0≤r ≤b-1.
若r=0，显然（a,b）=b;若r≠0,由于a=bq+r，每个能整除b,r的整数都能整除a，当然能同时整除a,b,所以（b,r）|（a,b）;另一方面，r=a-bq，每个能整除a,b的整数都能整除r, 当然能同时整除b,r, 所以(a,b)|(b,r).因此（a,b）=(b,r). 辗转相除法进行一步后，b 取代原来的a，用r取代原来的b,最大公约数保持不变，因此我们的算法可以一直进行下去：
a=bq1+r1,
b=r1q2+r2,
r1=r2q3+r3,
…
rk-3=rk-2qk-1+rk-1,
rk-2=rk-1qk.
一旦出现rk-2=rk-1qk（即rk=0）,则有
rk-1=（rk-2，rk-1）=…=（r1，r2）=（b，r1）=（a，b）.
这个算法用c语言来实现
源代码如下:
#include <stdio.h>
void main()
{
int a,b,m,n,temp,c,d;
printf("请输入两个数字\n");
scanf("%d%d",&m,&n);
d=m*n;
while (temp)
{
a=m>n?m:n;
b=m<=n?m:n;
temp=a%b;
m=temp;
n=b;
}
printf("这两个数的最大公约数是%d\n",b);
c=d/b;
printf("这两个数的最小公倍数是%d\n",c);
}
(两个数的成积除以两个数的最大公约数就是这两个数的最小公倍数)