1.用c语言编程实现一种迭代版本的简单乘法
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
#include<iostream>
using namespace std;
int mul(int a, int b)
{
	int t = 0;
	int result = 0;
	if (b == 0)
		return 0;
	else {
		while (b)
		{
			if (b & 1) //b的二进制末尾为0
				result += (a << t);//跳过不加
			t++;
			b = (b >> 1);
		}
	}
	return result;
}
int main()
{
	int a, b;
	cout << "请输入a，b的值：" << endl;
	cin >> a >> b;
	cout << "a=" << a << ",b=" << b << endl;
	cout << "乘积为：" << mul(a, b) << endl;
	return 0;
}
2.给出定理1.1（除法算法）的完整证明

\[ \begin{aligned} 证明： 1.存在性 \\&构造集合s=\{a-bk:k \in z并且a-bk\geq0\} \\&显然集合s非空,由良序原则，存在一个最小元r\in s,且r=a-qb \\&因此a=qb+r,r\geq0 \\ 2.唯一性 \\&如果r>b,那么存在r1，使得r=r1+b \\&a=qb+(r1+b)=(q+1)b+r1 \\&则r1在集合s中 \\&又r1<r,但r是最小元， \\&此时矛盾 \end{aligned} \]

3.用c语言编程实现一种迭代版本的gcd算法和一种egcd算法，利用gcd算法，写程序完成以下函数的功能。输入：一个正整数n 输出：大于等于n，且于n互为素数的正整数的个数。
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
//迭代版本的gcd算法
#include<iostream>
using namespace std;
double gcd(double a, double b)
{
	double t;
	if (b == 0)
		return a;
	else
	{

		while (b != 0)
		{
			if (a > b)
			{
				t = a - b;
				a = t;
			}
			else
			{
				t = b - a;
				a = b;
				b = t;
			}
		}

	}

	return a;
}
int main()
{

	double a, b;
	cout << "请输入a的值：" << endl;
	cin >> a;
	cout << "请输入b的值：" << endl;
	cin >> b;
	cout << "a=" << a << ",b=" << b << endl;
	cout << "a和b的最大公因子为：" << gcd(a, b) << endl;
	return 0;
}
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
58
59
60
61
62
63
64
65
66
67
68
69
70
//迭代版本的一种egcd算法
#include<iostream>
using namespace std;
int  gcd(int c, int d)
{
	int t;
	if (d == 0)
		return c;
	else
	{

		while (d != 0)
		{
			if (c > d)
			{
				t = c - d;
				c = t;
			}
			else
			{
				t = d - c;
				c = d;
				d = t;
			}
		}

	}

	return c;
}
int egcd(int a, int b)
{
	int m = gcd(a, b); //求a和b的最大公因子
	cout << "a=" << a << ",b=" << b << endl;
	int r0 = 1, r1 = 0, s0 = 0, s1 = 1;
	
	int t1, e1, q, t,e;
		while (b!=0)
		{
			
			q = a / b;
			t1 = r0;
			r0 = r1;
			r1 = t1 - q * r1;
			e1 = s0;
			s0 = s1;
			s1 = e1 - q * s1;
			t = a;
			e = b;
			a = b;
			b = t % e;
			
		}
		int r = r0;//a和b的系数
		 int s = s0;
	cout << "r=" << r<< ",s=" << s<< endl;
	cout << "最大公因子为：" << m;
	return 0;
}
int main()
{
	cout << "请输入两个数t1和t2:(t1>t2)" << endl;
	int t1, t2;
	cin >> t1 >> t2;
	if (t1 < t2)
		swap(t1, t2);
	egcd(t1, t2);
	return  0;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//写程序完成以下函数的功能。输入：一个正整数n 输出：大于等于n，且于n互为素数的正整数的个数。
#include<iostream>
using namespace std;
int gcd(int a, int b)
{
	if (b == 0)
		return a;
	else return gcd(b, a % b);
}
int main()
{
	int n, j = 0;
	cout << "请输入n的值" << endl;
	cin >> n;
	for (int i = n; i >=1; i--)
	{
		if (gcd(n, i - 1) == 1)
			j++;
	}
	cout << "与"<<n<<"互为素数的个数："<<j << endl;
}
4.第二章的第六题

\[ 假设g^a\equiv1(mod \quad m)且g^b\equiv1(mod \quad m),请证明g^{gcd(a,b)}\equiv1(mod \quad m). \]

\[ \begin{aligned} 证明： \\由已知条件可得 \\g^a&=k_1m+1,g^b=k_2m+1 \\&由Bezout定理得:gcd(a,b)=ar+bs \\&g^{gcd(a,b)} \\&=g^{ar+bs} \\&=g^{ar}*g^{bs} \\&=(g^a)^r*(g^b)^r \\&=(k_1m+1)^r*(k_2m+1)^s \\&又因为：(k_1m+1)^r\equiv1(mod \quad m),(k_2m+1)^s\equiv1(mod \quad m) \\&所以：g^{gcd(a,b)}\equiv1(mod \quad m). \end{aligned} \]

5.第二章的第八题

\[ 证明：如果gcd(a,b)\equiv d,则gcd(a/d,b/d)\equiv1. \]

\[ \begin{aligned} \\证明： \\&由gcd(a,b)=d得, \\&d是a和b的最大公因子. \\&设gcd(a/d,b/d)=k(k>1), \\&则a/d,b/d的最大公因子为k, \\&那么a和b的最大公因子为kd与d矛盾, \\&即假设不成立，则k=1,即得证； \end{aligned} \]