7.手动计算以下模m下a的乘法逆元。(a)m=11,a=5;(b)m=121,a=13;©m=1021,a=131.

image-20240119215225660

8.编写C语言程序完成模指数运算，即给定整数x,y和m为输入，计算并返回x^y mod m

c
int mod(int x,int y,int m)
{
	int res=1;
	while(y>0)
	{
		if(y&1)
		res=(res*x)%m;
		y>>=1;
		x=(x*x)%m;
	}
	return res;
}

9.用快速指数运算计算斐波那契数列。

c++
struct mat
{
	int m[2][2];
};
mat mult(mat m1,mat m2)
{
	mat temp;
	memset(temp.m,0,sizeof(temp.m));
	for(int i=0;i<2;i++)
	{
		for(int j=0;j<2;j++)
		{
			for(int k=0;k<2;k++)
			{
				temp.m[i][j]=(temp.m[i][j]+m1.m[i][k]*m2.m[k][j])%10000;
			}
		}
	}
	return temp;
}
int F(int n)
{
	mat x;
	x.m[0][0]=1;//相当于x
	x.m[0][1]=1;
	x.m[1][0]=1;
	x.m[1][1]=0;
	mat res;
	for(int i=0; i<2; i++)//相当于1
    {
        for(int j=0; j<2; j++)
        {
            if(i==j) 
			res.m[i][j]=1;
            else 
			res.m[i][j]=0;
        }
    }
	while(n)
	{
		if(n&1)
		res=mult(res,x);
		x=mult(x,x);
		n>>=1;
	}
	return res.m[0][1]%10000;
}

10.给定互素的正整数c和m，请证明在mod m 的意义上存在唯一确定的\整数值c^{-1},它使得

cc−1≡( mod m)。cc^{-1}\equiv(\bmod m)。

存在性：

因为c和m是非零整数，所以根据贝祖定理，存在整数x，y使gcd(c,m)=cx−my,因为c，m互素，所以cx−my=1.即cx≡1( mod m),所以存在c−1=x,使得cc−1≡1( mod m).因为c和m是非零整数，所以根据贝祖定理，\\ 存在整数x，y使gcd(c,m)=cx-my,\\ 因为c，m互素，所以cx-my=1.\\ 即cx\equiv1(\bmod m),\\ 所以存在c^{-1}=x,使得cc^{-1}\equiv1(\bmod m).\\

唯一性：

假设存在不同于x的x′使得cx′≡1( mod m),且x′<x,则cx≡cx′( mod m),根据消去律，x≡x′( mod m),因为x和x′都要小于m，所以x=x′,即乘法逆元唯一。假设存在不同于x的x'使得cx'\equiv1(\bmod m),且x'<x,\\ 则cx\equiv cx'(\bmod m),\\ 根据消去律，x\equiv x'(\bmod m),\\ 因为x和x'都要小于m，\\ 所以x=x',即乘法逆元唯一。

编程题：编写一个 Python 程序计算乘法逆元，即输入互素的正整数 c 和 m，返回 c ,

使得cc−1≡( mod m)。要求:只返回为正整数的c−1。使得 cc^{−1} ≡ (\bmod m)。要求:只返回为正整数的 c^{-1}。

python
def mod_egcd(a,b):#a为模数，b为正整数
    r0,s0,r1,s1=0,-1,1,0
    while(b):
        q,a,b=a//b,b,a%b
        r0,r1=r1,r0-q*r1
        s0,s1=s1,s0-q*s1
    return r0

5