25*n=1 mod36，求n

首先，我们可以通过枚举法，找到满足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。

相关问题

25*n=1 mod72，求n

首先，我们可以通过枚举法，找到满足25*n mod 72 = 1的n值。不过，这种方法比较费时费力，我们可以使用扩展欧几里得算法来求解。该算法可以求出两个整数a和b的最大公约数gcd(a,b)，并且可以得到一组整数x和y，使得ax+by=gcd(a,b)。我们可以利用这个算法求解25和72的最大公约数，同时得到满足25*n mod 72 = 1的n值。

具体步骤如下：

Step 1：求解gcd(25, 72)。

利用辗转相除法，可以得到：

72 = 2*25 + 22
25 = 1*22 + 3
22 = 7*3 + 1
3 = 3*1 + 0

因此，gcd(25, 72) = 1。

Step 2：使用扩展欧几里得算法，求解25和72的乘法逆元n。

根据扩展欧几里得算法，我们可以得到：

1 = 22 - 7*3
= 22 - 7*(25 - 1*22)
= 8*22 - 7*25
= 8*(72 - 2*25) - 7*25
= 8*72 - 23*25

因此，25的乘法逆元为-23，即25*(-23) mod 72 = 1。

所以，n = -23。但是，由于n应该是正整数，因此我们需要将-23转换为一个正整数，即n = 49。因此，满足25*n mod 72 = 1的正整数n为49。

素数p = 7，q = 17. n = p*q = 119 φ(n) = (p - 1) * (q - 1) = 96 e = 11 e * d ≡ 1 mod φ(n) 计算d

根据公式：e * d ≡ 1 mod φ(n)，可以转化为 e * d = 1 + k * φ(n)（k为任意整数）。

我们先求出 k 的值：

e * d ≡ 1 mod φ(n)

11 * d ≡ 1 mod 96

可以通过扩展欧几里得算法求出 11 和 96 的最大公约数，以及对应的 Bézout 系数 x 和 y：

gcd(11, 96) = 1，x = 35，y = -4

因为 x 和 y 中有负数，所以我们将它们转换成对应的正数：

x = x + k * φ(n)，y = y - k * e

35 + 96k > 0，-4 - 11k > 0，解得 0 ≤ k < 4，因此 k 可以取 0、1、2 或 3。

当 k = 0 时，x = 35，y = -4，此时 e * d = 1 + k * φ(n) = 1，d = 1 / e = 1 / 11。

当 k = 1 时，x = 131，y = -15，此时 e * d = 1 + k * φ(n) = 97，d = 97 / 11 = 8 余 9。

当 k = 2 时，x = 227，y = -26，此时 e * d = 1 + k * φ(n) = 193，d = 193 / 11 = 17 余 6。

当 k = 3 时，x = 323，y = -37，此时 e * d = 1 + k * φ(n) = 289，d = 289 / 11 = 26 余 3。

因此，d 的取值可能是 1、8、6 或 3，其中 1 是不合适的，因为它不满足 d 与 e 互质的条件。所以，在这个例子中，可以选择 d = 8 或 d = 6。