扩展欧几里得法求逆元
扩展欧几里得算法可以用来求逆元。对于两个整数a和b，如果存在整数x和y，使得ax+by=1，则称x和y是方程ax+by=1的解。在扩展欧几里得算法中，我们可以求出这样的解。
具体步骤如下：
1. 如果b等于0，则1和0是方程ax+by=1的解，即x=1，y=0，此时a就是逆元。
2. 如果b不等于0，可以递归调用扩展欧几里得算法，求解方程bx+a%by=1的解。
3. 在求解过程中，如果得到的y为负数，需要取模才能得到逆元。
例如，假设我们要求1848和701的逆元，首先得到x=29，然后可以验证701×29=1(mod 1848)，所以29就是1848的逆元。
需要注意的是，这个算法要求a和b互素，否则无法求得逆元。在实际应用中，例如在加密算法中，通常会选择一个与26互素的整数作为密钥，然后利用扩展欧几里得算法求得对应的逆元。
