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