CINTA作业三：同余、模指数、费尔马小定理、欧拉定理
题一
实现求乘法逆元的函数，给定a和m，求a模m的乘法逆元，无解时请给出无解提示，并且只返回正整数。进而给出求解同余方程（ax = b mod m）的函数，即给定a，b，m，输出满足方程的x，无解给出无解提示。
第一问
#include<iostream>
using namespace std;
//输入：a，m
//输出：a模m的乘法逆元
int a_mod_m(int a, int m)
{
bool exchange = false;//
//(gcd 判断是否互素)
int a1 = a;
int m1 = m;
if (a1 < m1)
{
int i;
i = a1;
a1 = m1;
m1 = i;
exchange = true;
}
while (a1 % m1 != 0)
{
int i = m1;
m1 = a1 % m1;
a1 = i;
}
if (m1 != 1) { cout << "无解"; return 0; }
if (exchange == false) { a1 = a;m1 = m; }
else { a1 = m;m1 = a; }
//egcd
int r1, r2, s1, s2;
r1 = 1;r2 = 0;
s1 = 0;s2 = 1;
int t1, t2;
while (true)
{
int c, d;
c = a1 / m1;
d = a1 - m1 * c;
if (d == 0)break;
t1 = r1 - c * s1;
t2 = r2 - c * s2;
a1 = m1;r1 = s1;r2 = s2;
m1 = d;s1 = t1;s2 = t2;
}
if (exchange==false)return t1;
else return t2;
}
int main()
{
cout<<a_mod_m(3, 11);
}
第二问
与第一问类似，最后乘上b即可
#include<iostream>
using namespace std;
int ax_b_mod_m(int a, int m,int b)
{
bool exchange = false;//
//(gcd判断互素)
int a1 = a;
int m1 = m;
if (a1 < m1)
{
int i;
i = a1;
a1 = m1;
m1 = i;
exchange = true;
}
while (a1 % m1 != 0)
{
int i = m1;
m1 = a1 % m1;
a1 = i;
}
if (m1 != 1) { cout << "无解"; return 0; }
if (exchange == false) { a1 = a;m1 = m; }
else { a1 = m;m1 = a; }
//egcd
//a s+m t=1
int r1, r2, s1, s2;
r1 = 1;r2 = 0;
s1 = 0;s2 = 1;
int t1, t2;
while (true)
{
int c, d;
c = a1 / m1;
d = a1 - m1 * c;
if (d == 0)break;
t1 = r1 - c * s1;
t2 = r2 - c * s2;
a1 = m1;r1 = s1;r2 = s2;
m1 = d;s1 = t1;s2 = t2;
}
if (exchange == false)return t1*b;
else return t2*b;
}
int main()
{
cout << ax_b_mod_m(3, 11, 2);
}
题二
实现模指数运算的函数，给定x、y和m，求x的y次方模m。
#include<iostream>
using namespace std;
//乘法的取余运算：(a * b) % c = ((a % c) * (b % c)) % c
int mod_exp(int x, int y, int m)
{
int res = 1;
while(y>0)
{
if ((y & 1) == 1)//与运算，判断末位是否为1
{
res = (res * x) % m;
}
y = y / 2;
x = (x *x) % m;
}
return res;
}
int main()
{
cout << mod_exp(2, 16, 11);
题三
设p = 23和a = 5，使用费尔马小定理1计算a^{2020} mod p?
解：
P为素数
5^ {2020}≡5 ^{9122+18} （mod 23)
9122=91*（23-1）
根据费尔马小定理：
5^ {91*22+18}≡5 ^{18}≡6 (mod 23)
题四
使用欧拉定理计算2^{100000}2 mod 55。
Φ（55）=Φ（5）Φ（11）=410=40
根据欧拉定理：
2^{40}≡1 (mod 55)
2^ {1000000}≡2^ {40*2500}≡1 (mod 55)
题五
手动计算7^{1000}的最后两个数位等于什么？
法一
（一个数mod 100，则可以得到最后两位，于是有了法一）
手动计算 7^{ 1000} 的最后两个数位等于什么？
设 7^{x}≡1 (mod 100)
x=Φ(100)= Φ(2* 2* 5* 5)= Φ(2)* Φ(2)* Φ(5)* Φ(5)=16
7^ { 1000}≡7^ {16*62+8}≡7^ {8} ≡1 mod 100
法二
（看到法一的结果竟然是1，想想（mod 10）也可能可以，于是有了法二）
② 7^{x}≡1 (mod 10)
x=Φ(10)=4
7^{ 1000}≡7^{4*250}≡1 mod 100
∴最后两个数位为01