輾轉相除法原理證明如下:
先用小的壹個數除大的壹個數，得第壹個余數；再用第壹個余數除小的壹個數，得第二個余數；又用第二個余數除第壹個余數，得第三個余數。
這樣逐次用後壹個數去除前壹個余數，直到余數是0為止。那麽，最後壹個除數就是所求的最大公約數（如果最後的除數是1，那麽原來的兩個數是互質數）。
例如求1515和600的最大公約數，第壹次：用600除1515，商2余315；第二次：用315除600，商1余285；第三次：用285除315，商1余30；第四次：用30除285，商9余15；第五次：用15除30，商2余0。1515和600的最大公約數是15。
輾轉相除法是求兩個數的最大公約數的方法。如果求幾個數的最大公約數，可以先求兩個數的最大公約數，再求這個最大公約數與第三個數的最大公約數。這樣依次下去，直到最後壹個數為止。最後所得的壹個最大公約數，就是所求的幾個數的最大公約數。
輾轉相除法，是由歐幾裏德算法而來。其基本原理如下：如果要求兩個正整數a和b（假設a>b，其實這並不影響求解算法）的最大公約數，可以表示成下面的式子：a=b×q+r （1）其中，q表示a除以b所得的商，r表示余數。