如何证明这种欧几里得(最大公约数)算法的正确性？

Question

#include<stdio.h>
unsigned int gcd(unsigned int M, unsigned int N)
{
    int rem;
    if(M < N)/*exchange value to=>M>N*/
    {
        int temp = M;
        M = N;
        N = temp;
    }
    
    while(N > 0)
    {
        rem = M % N;
        M = N;
        N = rem;
    }
    return M;
}
int main()
{
    printf("%d\n", gcd(25, 45));
    return 0;
}

这种算法通过不断的求余数，直到最后结果为0，倒数第二个数就是最大公因数。这个算法很高效，但是自己怎么能证明最后非0的那个余数就一定是正确答案昵，作为数学渣有点困扰。

Answer 1

手打公式太繁，改用拍照。

Answer 2

参见

1. 辗转相除法。

2. Greatest Common Divisor。

Answer 3

（借张图）两个数都是由最大公约数堆出来的，所以相减、取模最大公约数肯定是不变的。（直观解释）