CINTA_02

第一题

题目：利用 egcd 算法的思路，手动计算以下数值的 Bézout 系数和最大公因子:

a = 132，b = 78

a = 273，b = 131

解：

egcd算法可以帮助我们计算两个整数 (a) 和 (b) 的最大公因子（gcd），以及找到贝祖系数 (x) 和 (y)，使得：

$$ax + by = \text{gcd}(a, b)$$

1: a = 132,b = 78

$$\begin{aligned} \begin{pmatrix} 1 & 0& 132 \\ 0 & 1 &78 \end{pmatrix} &\rightarrow \begin{pmatrix} 0 & 1 & 78 \\ 1 & -1 &54 \end{pmatrix} \rightarrow \begin{pmatrix} 1 & -1 &54 \\ -1 & 2 &24 \end{pmatrix}\\\\ &\rightarrow \begin{pmatrix} -1 & 2 &24 \\ 3 & -5 & 6 \end{pmatrix} \rightarrow \begin{pmatrix} 3 & -5 & 6 \\ & & 0 \end{pmatrix} \\ \text{结果：} r = 6, s = -5, d = 6 \end{aligned}$$

2: a = 273,b = 131

$$\begin{aligned} \begin{pmatrix} 1 & 0& 273 \\ 0 & 1 &131 \end{pmatrix} &\rightarrow \begin{pmatrix} 0 & 1 & 131 \\ 1 & -2 &11 \end{pmatrix} \rightarrow \begin{pmatrix} 1 & -2 &11 \\ -11 & 23 &10 \end{pmatrix}\\\\ &\rightarrow \begin{pmatrix} -11 & 23 &10 \\ 12 & -25 & 1 \end{pmatrix} \rightarrow \begin{pmatrix} 12 & -25 & 1 \\ & & 0 \end{pmatrix} \\ \text{结果：} r = 12, s = -25, d = 1 \end{aligned}$$

第二题

$$\text{假设 } g^a \equiv 1 \pmod{m} \text{ 且 } g^b \equiv 1 \pmod{m}, \text{ 请证明 } g^{\gcd(a,b)} \equiv 1 \pmod{m}.$$

证明

$$令\gcd(a,b) = ar + bs，则g^{\gcd(a,b)}=g^{ar + bs} = g^{ar} * g^{bs}$$ $$则g^{\gcd(a,b)}\pmod{m} = ((g^a)^r\mod{m}) * ((g^b)^s\mod{m})$$ $$又 g^a \mod{m} = 1 ,g^b \mod{m} = 1$$ $$根据模指数运算，可得g^{\gcd(a,b)} \mod{m} 的结果也是1$$ $$所以得证g^{\gcd(a,b)} \equiv 1 \pmod{m}$$

第三题

$$证明:对任意整数n,2n+1 \text{和}9n+4互素$$

证明

$$\begin{aligned} \begin{pmatrix} 1 & 0& 2n+1 \\ 0 & 1 &9n+4 \end{pmatrix} &\rightarrow \begin{pmatrix} 1 & 2 & 2n+1 \\ -4 & 1 &n \end{pmatrix} \rightarrow \begin{pmatrix} -4 & 1 &n \\ 9 & -2 &1 \end{pmatrix}\\\\ &\rightarrow \begin{pmatrix} 9 & -2 &1 \\ & & 0 \end{pmatrix} \\ 存在整数r=9,s=-2 \\ 使得(2n+1)*9(9n+4) * (-2) = 1 \\ 所以得证 \end{aligned}$$

第四题

用代码(语言不限)实现egcd算法，并利用自己的代码求以下a和b的最大公因子和Bezout系数。

1）a = 154954179184694689280846339291, b = 6413915469668918084633

2）a = 1260343087433328623791076926584, b = 84279984323383

def egcd(a, b):
    j0, j1, s0, s1 = 1, 0, 0, 1
    while(b):
        a, b ,q= b, a%b ,a//b
        j0=j1
        j1=j0 - q*j1
        s0= s1
        s1=s0 - q*s1
    return a, j0, s0
a1 = 154954179184694689280846339291
b1 = 6413915469668918084633
gcd1, x1, y1 = egcd(a1, b1)
print(f"a1,b1最大公因数为{gcd1},bezout系数为{x1}{y1}")

a2 = 1260343087433328623791076926584
b2 = 84279984323383
gcd2, x2, y2 = egcd(a2, b2)
print(f"a2,b2最大公因数为{gcd2},bezout系数为{x2}{y2}")