如何运用扩展欧几里得算法、欧拉定理和费马小定理解决最大公约数及同余问题？

本文共计1590个文字，预计阅读时间需要7分钟。

题目描述：求a和b的最大公约数，是古老的一种解法，即辗转相除法。例如，a=15，b=12时，a和b的最大公约数是3。问题描述：a和b的最大公约数是多大？古代解法：辗转相除法。迭代过程：例如，a=12，b=15

问题描述a和b的最大公约数是多少古代解法辗转相除法迭代过程例如{a15和b12}{a12,

问题描述： 

            a 和 b的最大公约数是多少？

古代解法：辗转相除法

迭代过程：例如：

{a = 15 和 b = 12  }

=>{ a = 12,b =  15 - (15/12)* 12 = 3 }

=> {a = 3,b=  12 - (12/3)*3 = 0 }

=> { b = 0 所以a为最大公因数}

c++代码: 

int gcd(int a,int b){return b?gcd(b,a%b):a;}

一行搞定。