25*n=1 mod36,求n
时间: 2024-03-30 17:34:44 浏览: 117
首先,我们可以通过枚举法,找到满足25*n mod 36 = 1的n值。不过,这种方法比较费时费力,我们可以使用扩展欧几里得算法来求解。该算法可以求出两个整数a和b的最大公约数gcd(a,b),并且可以得到一组整数x和y,使得ax+by=gcd(a,b)。我们可以利用这个算法求解25和36的最大公约数,同时得到满足25*n mod 36 = 1的n值。
具体步骤如下:
Step 1:求解gcd(25, 36)。
利用辗转相除法,可以得到:
36 = 1*25 + 11
25 = 2*11 + 3
11 = 3*3 + 2
3 = 1*2 + 1
2 = 2*1 + 0
因此,gcd(25, 36) = 1。
Step 2:使用扩展欧几里得算法,求解25和36的乘法逆元n。
根据扩展欧几里得算法,我们可以得到:
1 = 3 - 1*2
= 3 - 1*(11 - 3*3)
= 4*3 - 1*11
= 4*(25 - 2*11) - 1*11
= 4*25 - 9*11
= 4*25 - 9*(36 - 25)
= 13*25 - 9*36
因此,25的乘法逆元为13,即25*13 mod 36 = 1。
所以,n = 13。因此,满足25*n mod 36 = 1的正整数n为13。
阅读全文