a^bmodm的函数求法

写一个模指数运算函数Mod_Exp,输入a、b和m，输出a^b mod m ,即a的b次方模m.

1
2
3
4
5
6
7
8
9
10
11
12
int Mod_Exp(int a, int b,int c)
{
	int t = 1;
	while (b)
	{
		if (b & 1)//判断末尾的数是0还是1，如果是1,则需要进行取模运算
			t = t * a % c;
		b >>= 1;//b的二进制数右移一位
		a = a * a % c;//2,4,8......次方取余
	}
	return t;
}
求乘法逆元

写一个求乘法逆元的函数Mul_Inverse,输入a和m,求a模m的乘法逆元。提示：要求只输出正整数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
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 m)//利用扩展欧几里得算法求乘法逆元
{
	int r0 = 1, s0 = 0, r1 = 0, s1 = 1;
	int x, y, q, t0, t1;
	while (m != 0)
	{
		q = a / m;
		t0 = r0;
		r0 = r1;
		r1 = t0 - q * r1;
		t1 = s0;
		s0 = s1;
		s1 = t1 - q * s1;
		x = a;
		y = m;
		a = m;
		m = x % y;
	}
	return r0;
}
int Mul_Inverse(int a, int m)//求乘法逆元
{
	if (gcd(a, m) == 1)
	{
		int c = egcd(a, m);
		if (c < 0)
		{
			c = c + m;
			return c;
		}
		else
			return c;
	}
	else
		return 0;
	return 0;
}
int main()
{
	int a, m;
	cout << "请分别输入a,m的值：" << endl;
	cin >> a >> m;
	cout << "a=" << a << ",m=" << m << endl;
	cout << Mul_Inverse(a, m);
	return 0;
}
4.1
$$ \[\begin{split} \begin{flalign} 设p=23和a=3,使用费尔马小定理计算a^{2019}modp?\\ 解： 因为：p是素数，并且3\not \equiv0(mod\quad23)\\ 所以：\\由费尔马小定理得\\3^{22}\equiv1(mod\quad23) 又：2019=22*91+7\\ 所以：\\3^{2019}\equiv3^{22*91+17}\equiv3^{17}(mod \quad23) \\3^3(mod 23)=4 \\3^6(mod 23)=4*4(mod 23)=16 \\3^{12}(mod 23)=16*16(mod 23)=3 \\3^{15}(mod 23)=3*4(mod 23)=12 \\3^{17}(mod 23)=12*9(mod 23)=16 \end{flalign} \end{split}\]

$$

4.5

\[ \begin{split} 请证明13整除2^{70}+3^{70}。[提示：这是一道名为证明题的计算题]\\ 解： 因为：13为素数并且\\2\not \equiv0(mod \quad 13)并且3\not \equiv0(mod 13) \\所以：依据费尔马小定理得： 2^{12}\equiv1(mod \quad 13)\\ 3^{12}\equiv1(mod \quad 13)\\ \\则：2^{\quad{12}*5+10\quad}\equiv2^{10}(mod \quad13)=10 \\3^{12*5+10}\equiv3^{10}(mod \quad13)=3 \\又10+3=13 \\所以13整除2^{70}+3^{70} \end{split} \]

4.6

\[ \begin{split} 使用欧拉定理计算2^{100000}mod\quad55. \\因为：gcd(2,55)=1 \\则：2^{\phi(55)}\equiv1(mod\quad55),\phi(55)=\phi(5)*\phi(11)=4*10=40 \\则：2^{40}\equiv1(mod 55) \\2^{100000}\equiv2^{40*2500}\equiv2^{40^{2500}}\equiv1^{2500}(mod55)=1 \end{split} \]

4.8

\[ \begin{split} 手动计算7^{1000}的最后两位数是多少？ 解： \\即计算7^{1000}\mod100 \\因为gcd(7,100)=1 \\所以7^{\phi(100)}\equiv1(mod 100) \\又\phi(100)=\phi(2^2*5^2)=(2^2-2^1)*(5^2-5^1)=40 \\所以：7^{40}\equiv1(mod \quad100) \\7^{1000}=7^{40*25}=7^{\quad{(40)}^{25}\quad}\equiv1^{25}(mod \quad100)=1 \\所以最后两位数为01 \end{split} \]