CINTA作业三：同余、模指数、费尔马小定理、欧拉定理

提示：本章主要围绕整数运算中模关系的运算

文章目录

• CINTA作业三：同余、模指数、费尔马小定理、欧拉定理
• 一、实现求乘法逆元的函数
• 二、实现模指数运算的函数
• 三、费尔马小定理的应用
• 四、欧拉定理的应用
• 五、手动计算7^{1000}的最后两个数位等于什么

一、实现求乘法逆元的函数

要求如下：

给定a和m，
求a模m的乘法逆元，无解时请给出无解提示，并且只返回正整数。
进而给出求解同余方程（ax = b mod m）的函数，即给定a，b，m，输出满足方程的x，无解给出无解提示。

代码如下：

#include<iostream>
//#include<math.h>
using namespace std;
int gcd(int a,int b);
int egcd(int a,int b);
int solve_equations(int a,int b,int m);

void main()
{
	int a,b,m;

	//求a模m的乘法逆元
	cout<<"输入整数a和m"<<'\n';
	cin>>a>>m;
	if(egcd(a,m)==0)   cout<<"不存在a模m的乘法逆元！"<<'\n';
	else               cout<<"a模m的乘法逆元为:"<<egcd(a,m)<<'\n';  


	//求解同余方程
	cout<<'\n'<<'\n'<<"输入同余方程（ax = b mod m）的相关数据a,b,m(m>0)"<<'\n';;
	cin>>a>>b>>m;
	//cout<<"x="<<solve_equations(egcd(a,m),b,m)<<'\n';
	if(solve_equations(a,b,m)==-1)     cout<<"该同余方程无解！"<<'\n';
	else              cout<<"该同余方程的解为:  x="<<solve_equations(a,b,m)<<'\n';
	

}


int gcd(int a,int b)
{
	int t;
	while(b!=0)
	{
	  t=a%b;
	  a=b;
      b=t;
	}
	return a;
}


int egcd(int a,int b)
{
	int m=b;
	if(gcd(a,b)!=1)   return 0;    //a存在模m的乘法逆元的充要条件是gcd(a,m) = 1
	else
	{ 
		int r0=1,r1=0,s0=0,s1=1;
	    while(b)
	    {
		    int q=a/b;
		    int t=b;
		    b=a%b;
		    a=t;

		    int x=r1;
		    r1=r0-q*r1;
		    r0=x;

		    int y=s1;
		    s1=s0-q*s1;
		    s0=y;
	    }

		if(r0>0)    return r0;  
		else        return r0+m;
     }
}

int solve_equations(int a,int b,int m)
{
	if(b%gcd(a,m)!=0)    return -1;     //同余方程有解的充要条件是 gcd(a,m)∣b
	else
	{
		int x=1;
		b=egcd(a,m)*b;
	    while((x-b)%m!=0)
	         x++;
	    return x;
	}
}

总结：

1.a存在模m的乘法逆元的充要条件是gcd(a,m) = 1
2.同余方程有解的充要条件是 gcd(a,m)∣b

二、实现模指数运算的函数

要求如下：

给定x、y和m，求x的y次方模m。

代码如下（示例）：

#include<iostream>
using namespace std;
int rec_mod_exo(int x,int y,int p);    //迭代法

void main()
{
	int x,y,m;
	cout<<"**** 求x的y次方模m ****"<<'\n';
	cout<<"输入x、y和m"<<'\n';
	cin>>x>>y>>m;
	cout<<"结果为："<<rec_mod_exo(x,y,m)<<'\n';;
}

int rec_mod_exo(int x, int y, int p)
{
	int z;
	if(y==0)   return 1;
	z=rec_mod_exo(x,y/2,p);
	if(y%2==0)      //y为偶数
		return z*z%p;
	else            //y为奇数
		return x*z*z%p;
}

三、费尔马小定理的应用

要求如下：

设p = 23和a = 5，使用费尔马小定理计算a^{2020} mod p

 
解： 5 2020 5^{2020} 52020 ≡ \equiv ≡ 5 91 ∗ 22 + 18 5^{91*22+18} 591∗22+18 (mod 23)
     ∴ \therefore ∴ 5 91 ∗ 22 + 18 5^{91*22+18} 591∗22+18 ≡ \equiv ≡ 5 18 5^{18} 518 (mod 23)

    又 ∵ \because ∵ 5 2 5^{2} 52 mod 23 = 2
         5 4 5^{4} 54 mod 23 = 4
         5 8 5^{8} 58 mod 23 = 8
         5 16 5^{16} 516 mod 23 = 18

     ∴ \therefore ∴ 5 18 5^{18} 518 (mod 23) ≡ \equiv ≡ 5 10010 5^{10010} 510010 (mod 23)
     ∴ \therefore ∴ 原式 = (18x2) mod 23 =13

四、欧拉定理的应用

要求如下：

使用欧拉定理计算2^{100000} mod 55

 
解：由欧拉Phi函数公式可知， ϕ \phi ϕ(55) = ϕ \phi ϕ(5) ϕ \phi ϕ(11)
    又由欧拉Phi函数性质知， ϕ \phi ϕ(5)=4, ϕ \phi ϕ(11)=10
    ∴ \therefore ∴ ϕ \phi ϕ(55) = 4 x 10 = 40
    由欧拉定理知， 2 ϕ ( 55 ) 2^{ϕ(55)} 2ϕ(55) ≡ \equiv ≡ 1 (mod 55) ;
    即， 2 40 2^{40} 240 ≡ \equiv ≡ 1 (mod 55)
    ∴ \therefore ∴ 2 100000 2^{100000} 2100000 mod 55 = 2 40 ∗ 2500 2^{40*2500} 240∗2500 mod 55 = 1

五、手动计算7^{1000}的最后两个数位等于什么

要求如下：

手动计算7^{1000}的最后两个数位等于什么

解：要求 7 1000 7^{1000} 71000 的最后两个位数，即求 7 1000 7^{1000} 71000 mod 100
     ∵ \because ∵ gcd(7,100) = 1
     ∴ \therefore ∴由欧拉定理知， 7 ϕ ( 100 ) 7^{ϕ(100)} 7ϕ(100) ≡ \equiv ≡ 1 (mod 100)
    由欧拉Phi函数公式可知， ϕ \phi ϕ(100) = ϕ \phi ϕ(25) ϕ \phi ϕ(4) = 20 x 2 = 40
     即， 7 40 7^{40} 740 ≡ \equiv ≡ 1 (mod 100)
     ∴ \therefore ∴ 7 1000 7^{1000} 71000 mod 100 = 2 40 ∗ 25 2^{40*25} 240∗25 mod 100 = 1
     ∴ \therefore ∴ 7 1000 7^{1000} 71000 的最后两个数位等于01