前言
大部分答案是我自己写的，仅供参考，不保证严谨性和正确性。
1. 求互质的数
Question：求小于5，8，12，20，25并与这些数互质的数
Answer：以25为例，互质的数为：2，3，4，6，7，8，9，11，12，13，14，16，17，18，19，21，22，23，24
2. 计算
a.
gcd
?
(
2
,
10
)
=
2
?
l
c
m
(
2
,
10
)
=
10
\gcd(2,10)=2\ \mathrm{lcm}(2,10)=10
gcd(2,10)=2?lcm(2,10)=10
b.
gcd
?
(
20
,
8
)
=
4
?
l
c
m
(
20
,
8
)
=
40
\gcd(20,8)=4\ \mathrm{lcm}(20,8)=40
gcd(20,8)=4?lcm(20,8)=40
c.
gcd
?
(
12
,
40
)
=
4
?
l
c
m
(
12
,
40
)
=
120
\gcd(12,40)=4\ \mathrm{lcm}(12,40)=120
gcd(12,40)=4?lcm(12,40)=120
d.
gcd
?
(
21
,
50
)
=
1
?
l
c
m
(
21
,
50
)
=
1050
\gcd(21,50)=1\ \mathrm{lcm}(21,50)=1050
gcd(21,50)=1?lcm(21,50)=1050
e.
gcd
?
(
p
2
q
2
,
p
q
3
)
=
p
q
2
?
l
c
m
(
p
2
q
2
,
p
q
3
)
=
p
2
q
3
\gcd(p^2q^2, pq^3)=pq^2\ \mathrm{lcm}(p^2q^2,pq^3)=p^2q^3
gcd(p2q2,pq3)=pq2?lcm(p2q2,pq3)=p2q3，
p
,
q
p,q
p,q是不同的质数
3. 计算
51
m
o
d
??
13
=
12
51\mod{13}=12
51mod13=12
342
m
o
d
??
85
=
2
342\mod{85}=2
342mod85=2
62
m
o
d
??
15
=
2
62\mod{15}=2
62mod15=2
10
m
o
d
??
15
=
10
10\mod{15}=10
10mod15=10
(
82
?
73
)
m
o
d
??
7
=
(
5
?
3
)
m
o
d
??
7
=
8
(82\cdot 73)\mod{7}=(5\cdot 3)\mod{7}=8
(82?73)mod7=(5?3)mod7=8
(
51
+
68
)
m
o
d
??
7
=
(
2
+
5
)
m
o
d
??
7
=
0
(51+68)\mod{7}=(2+5)\mod{7}=0
(51+68)mod7=(2+5)mod7=0
(
35
?
24
)
m
o
d
??
11
=
(
2
?
2
)
m
o
d
??
11
=
4
(35\cdot 24)\mod{11}=(2\cdot 2)\mod{11}=4
(35?24)mod11=(2?2)mod11=4
(
47
+
68
)
m
o
d
??
11
=
(
3
+
2
)
m
o
d
??
11
=
5
(47+68)\mod{11}=(3+2)\mod{11}=5
(47+68)mod11=(3+2)mod11=5
4. 互质
Question: 找到
s
,
t
s,t
s,t满足
1
=
7
s
+
11
t
1=7s+11t
1=7s+11t，证明
s
,
t
s,t
s,t并非独一无二的。
Answer：
s
=
?
3
,
t
=
2
s=-3,t=2
s=?3,t=2，还可以找到另一组
s
=
?
14
,
t
=
9
s=-14,t=9
s=?14,t=9
5. 证明
Question:
a
,
b
∈
Z
?
s
.
t
.
?
a
>
0
,
b
>
0
→
a
b
=
l
c
m
(
a
,
b
)
?
gcd
?
(
a
,
b
)
a,b\in Z\ \mathrm{s.t.}\ a>0,b>0\to ab=\mathrm{lcm}(a,b)\cdot\gcd(a,b)
a,b∈Z?s.t.?a>0,b>0→ab=lcm(a,b)?gcd(a,b)
Answer: 根据算术基本定理，
a
=
p
1
m
1
p
2
m
2
?
p
n
m
n
a=p_1^{m_1}p_2^{m_2}\cdots p_n^{m_n}
a=p1m1??p2m2???pnmn??,
b
=
k
1
q
1
k
2
q
2
?
k
u
q
u
b=k_1^{q_1}k_2^{q_2}\cdots k_u^{q_u}
b=k1q1??k2q2???kuqu??。
a
a
a和
b
b
b的公因子设为
P
P
P，
a
=
A
P
,
b
=
B
P
a=AP, b=BP
a=AP,b=BP，那么
a
b
=
A
P
2
B
,
l
c
m
(
a
,
b
)
=
A
B
P
,
gcd
?
(
a
,
b
)
=
P
ab=AP^2B, \mathrm{lcm}(a,b)=ABP,\gcd(a,b)=P
ab=AP2B,lcm(a,b)=ABP,gcd(a,b)=P
6. 证明（整除与互质）
Question：如果
a
,
b
a,b
a,b是整数，且有
(
a
∣
c
)
∧
(
b
∣
c
)
(a\mid c)\land (b\mid c)
(a∣c)∧(b∣c)。如果
a
,
b
a,b
a,b互质，证明
a
b
∣
c
ab\mid c
ab∣c；举例说明如果
a
,
b
a,b
a,b不互质，则
a
b
ab
ab不需要整除
c
c
c.
Answer: 由题目知，显然
c
c
c是
a
,
b
a,b
a,b的公倍数，
a
b
=
l
c
m
(
a
,
b
)
ab=\mathrm{lcm}(a,b)
ab=lcm(a,b)，只需要证明公倍数必然是最小公倍数的倍数即可。
假定公倍数并非最小公倍数的倍数，则有
c
=
q
(
a
b
)
+
r
,
0
<
r
<
q
c=q(ab)+r, 0<r<q
c=q(ab)+r,0<r<q，由于
c
c
c和
a
b
ab
ab都是
a
a
a的倍数，
r
r
r必然也是
a
a
a的倍数，同理可得
r
r
r也是
b
b
b的倍数，故
r
r
r也是公倍数，因此大于
a
b
ab
ab，与设想矛盾，故
r
=
0
r=0
r=0，故
a
b
∣
c
ab\mid c
ab∣c
非互质情况反例a=4,b=6,c=12
7. 模运算相关证明
Question：如果
a
,
b
a,b
a,b是整数，
n
n
n是正整数，证明:
a
m
o
d
??
n
=
b
m
o
d
??
n
?
i
i
f
.
?
n
∣
(
a
?
b
)
a\mod{n}=b\mod{n}\ \mathrm{iif.}\ n\mid (a-b)
amodn=bmodn?iif.?n∣(a?b)
Answer:
-
n
∣
(
a
?
b
)
→
a
m
o
d
??
n
=
b
m
o
d
??
n
n\mid (a-b)\to a\mod{n}=b\mod{n}
n∣(a?b)→amodn=bmodn
设
a
=
q
1
n
+
r
1
，
b
=
q
2
n
+
r
2
a=q_1n+r_1，b=q_2n+r_2
a=q1?n+r1?，b=q2?n+r2?，显然
n
∣
(
a
?
b
)
=
n
∣
(
r
1
?
r
2
)
n\mid (a-b)=n\mid (r_1-r_2)
n∣(a?b)=n∣(r1??r2?)
那么
r
1
?
r
2
=
0
r_1-r_2=0
r1??r2?=0 -
a
m
o
d
??
n
=
b
m
o
d
??
n
→
n
∣
(
a
?
b
)
a\mod{n}=b\mod{n}\to n\mid (a-b)
amodn=bmodn→n∣(a?b)
显然，由条件可设
a
=
q
1
n
+
r
,
b
=
q
2
n
+
r
a=q_1n+r, b=q_2n+r
a=q1?n+r,b=q2?n+r,
a
?
b
=
(
q
1
?
q
2
)
n
a-b=(q_1-q_2)n
a?b=(q1??q2?)n是
n
n
n的倍数
8. 公约数相关证明
Question：
d
=
gcd
?
(
a
,
b
)
d=\gcd (a,b)
d=gcd(a,b)，如果
a
=
d
a
′
,
b
=
d
b
′
a=da', b=db'
a=da′,b=db′，证明
gcd
?
(
a
′
,
b
′
)
=
1
\gcd (a',b')=1
gcd(a′,b′)=1
Answer：
d
=
a
s
+
b
t
=
d
a
′
s
+
d
b
′
t
→
a
′
s
+
b
′
t
=
1
d=as+bt=da's+db't\to a's+b't=1
d=as+bt=da′s+db′t→a′s+b′t=1
QED
9. 模运算相关证明
Question:
n
n
n是大于1的一个数，如果
(
a
m
o
d
??
n
=
a
′
)
?
∧
?
(
b
m
o
d
??
n
=
b
′
)
(a\mod{n}=a')\ \land\ (b\mod{n}=b')
(amodn=a′)?∧?(bmodn=b′)，证明
(
a
+
b
)
m
o
d
??
n
=
(
a
′
+
b
′
)
m
o
d
??
n
(a+b)\mod{n}=(a'+b')\mod{n}
(a+b)modn=(a′+b′)modn和
(
a
b
)
m
o
d
??
n
=
(
a
′
b
′
)
m
o
d
??
n
(ab)\mod{n}=(a'b')\mod{n}
(ab)modn=(a′b′)modn
Answer: 题目实际上让证明上一节说的模运算优先与加法和乘法。这里可设
a
=
q
1
n
+
a
′
,
b
=
q
2
n
+
b
′
a=q_1n+a', b=q_2n+b'
a=q1?n+a′,b=q2?n+b′，那么
(
a
+
b
)
m
o
d
??
n
=
(
q
1
n
+
q
2
n
+
a
′
+
b
′
)
m
o
d
??
n
=
(
a
′
+
b
′
)
m
o
d
??
n
(a+b)\mod{n}=(q_1n+q_2n+a'+b')\mod{n}=(a'+b')\mod{n}
(a+b)modn=(q1?n+q2?n+a′+b′)modn=(a′+b′)modn；对于乘法来说：
(
a
b
)
m
o
d
??
n
=
(
q
1
q
2
n
2
+
q
1
n
b
′
+
a
2
n
a
′
+
a
′
b
′
)
m
o
d
??
n
=
(
a
′
b
′
)
m
o
d
??
n
(ab)\mod{n}=(q_1q_2n^2+q_1nb'+a_2na'+a'b')\mod{n}=(a'b')\mod{n}
(ab)modn=(q1?q2?n2+q1?nb′+a2?na′+a′b′)modn=(a′b′)modn
10. 整除相关证明
Question:
a
,
b
a,b
a,b是正整数，让
d
=
gcd
?
(
a
,
b
)
,
m
=
l
c
m
(
a
,
b
)
d=\gcd (a,b), m=\mathrm{lcm}(a,b)
d=gcd(a,b),m=lcm(a,b)。如果
(
t
∣
a
)
∧
(
t
∣
b
)
(t\mid a)\land (t\mid b)
(t∣a)∧(t∣b)，证明
t
∣
d
t\mid d
t∣d。如果
s
s
s是
a
,
b
a,b
a,b的倍数，证明
s
s
s是
m
m
m的倍数。
Answer: 通俗来说，这个题目让证明最大公约数是所有公约数的倍数，最小公倍数是所有倍数的约数。后者在题目6中已经证明过。
证明前者：设
a
=
m
t
，
b
=
n
t
a=mt，b=nt
a=mt，b=nt，且有
a
s
+
b
v
=
d
→
m
t
s
+
n
t
v
=
d
as+bv=d\to mts+ntv=d
as+bv=d→mts+ntv=d，故
t
∣
d
t\mid d
t∣d
11. 模运算相关证明
Question:
a
,
n
a,n
a,n是正整数，让
d
=
gcd
?
(
a
,
n
)
d=\gcd (a,n)
d=gcd(a,n)，证明：
a
x
m
o
d
??
n
=
1
ax\mod{n}=1
axmodn=1有解
i
i
f
.
?
d
=
1
\mathrm{iif.}\ d=1
iif.?d=1
Answer: 分两个方向证明
-
d
=
1
→
d=1\to
d=1→方程有解
显然
a
,
n
a,n
a,n互质，有
a
s
+
n
t
=
1
as+nt=1
as+nt=1，此时
a
s
=
1
?
n
t
as=1-nt
as=1?nt，模
n
n
n必为1，有解。 - 方程有解
→
d
=
1
\to d=1
→d=1
不妨设解为
x
0
x_0
x0?（显然是整数），那么方程可写为
a
x
0
=
q
n
+
1
ax_0=qn+1
ax0?=qn+1，显然说明互质。
12. 互质相关证明
Question: 证明
5
n
+
3
5n+3
5n+3和
7
n
+
4
7n+4
7n+4总是互质的。
Answer: 很明显可以构造出：
7
?
(
5
n
+
3
)
?
5
?
(
7
n
+
4
)
=
1
7\cdot (5n+3)-5\cdot (7n+4)=1
7?(5n+3)?5?(7n+4)=1
13. 互质相关证明
Question:
m
,
n
m,n
m,n是互质的，
r
r
r是任意整数，证明: 存在整数
x
,
y
x,y
x,y满足
m
x
+
n
y
=
r
mx+ny=r
mx+ny=r
Answer: 必有
m
s
+
n
t
=
1
ms+nt=1
ms+nt=1，两边乘
r
r
r得：
m
s
r
+
n
t
r
=
r
msr+ntr=r
msr+ntr=r，故得证。
14. 整除相关证明
Question:
p
,
q
,
r
p,q,r
p,q,r是大于
3
3
3的质数，证明：
3
∣
(
p
2
+
q
2
+
r
2
)
3\mid (p^2+q^2+r^2)
3∣(p2+q2+r2)
Answer: 考虑讨论
(
p
2
+
q
2
+
r
2
)
m
o
d
??
3
(p^2+q^2+r^2)\mod{3}
(p2+q2+r2)mod3，任何一个质数模3的结果只能是
1
，
2
1，2
1，2，其平方模3的结果将只可能是
1
1
1，故
3
3
3必然能整除三个平方和
15. 质数相关证明
Question: 证明任何大于
3
3
3的质数，都能被写成
6
n
+
1
6n+1
6n+1或
6
n
+
5
6n+5
6n+5的形式。
Answer: 显然，这是将模
6
6
6同余的两个等价类，只要分析6种情况即可。
6
n
,
6
n
+
2
,
6
n
+
3
,
6
n
+
4
6n,6n+2,6n+3,6n+4
6n,6n+2,6n+3,6n+4都不是质数，故QED
16. 计算
Question: Determine
7
1000
m
o
d
??
6
7^{1000}\mod{6}
71000mod6 and
6
1001
m
o
d
??
7
6^{1001}\mod{7}
61001mod7
Answer:
7
1000
m
o
d
??
6
=
1
1000
m
o
d
??
6
=
1
7^{1000}\mod{6}=1^{1000}\mod{6}=1
71000mod6=11000mod6=1
6
1001
m
o
d
??
7
=
?
1
m
o
d
??
7
=
6
6^{1001}\mod{7}=-1\mod{7}=6
61001mod7=?1mod7=6
17. 模运算相关证明
Question: 如果
a
,
b
,
s
,
t
a,b,s,t
a,b,s,t是整数，
a
m
o
d
??
s
t
=
b
m
o
d
??
s
t
a\mod{st}=b\mod{st}
amodst=bmodst，证明
a
m
o
d
??
s
=
b
m
o
d
??
s
a\mod{s}=b\mod{s}
amods=bmods and
a
m
o
d
??
t
=
b
m
o
d
??
t
a\mod{t}=b\mod{t}
amodt=bmodt.
s
,
t
s,t
s,t满足什么条件的情况下，反过来也是正确的？
Answer: 显然
a
=
q
1
s
t
+
r
,
b
=
q
2
s
t
+
r
a=q_1st+r, b=q_2st+r
a=q1?st+r,b=q2?st+r，两者对
s
,
t
s,t
s,t分别取模就能验证结论。
18. 计算
Question:
8
402
m
o
d
??
5
8^{402}\mod{5}
8402mod5
Answer:
8
402
m
o
d
??
5
=
3
402
m
o
d
??
5
=
9
201
m
o
d
??
5
=
4
201
m
o
d
??
5
=
(
?
1
)
201
m
o
d
??
5
=
4
8^{402}\mod{5}=3^{402}\mod{5}=9^{201}\mod{5}=4^{201}\mod{5}=(-1)^{201}\mod{5}=4
8402mod5=3402mod5=9201mod5=4201mod5=(?1)201mod5=4
19. 最大公约数相关证明
Question: 证明：
gcd
?
(
a
,
b
c
)
=
1
?
i
i
f
.
?
gcd
?
(
a
,
b
)
=
1
?
∧
?
gcd
?
(
a
,
c
)
=
1
\gcd (a,bc)=1\ \mathrm{iif.}\ \gcd(a,b)=1\ \land\ \gcd(a,c)=1
gcd(a,bc)=1?iif.?gcd(a,b)=1?∧?gcd(a,c)=1
Answer: 分两个方向证明。
-
gcd
?
(
a
,
b
)
=
1
?
∧
?
gcd
?
(
a
,
c
)
=
1
→
gcd
?
(
a
,
b
c
)
=
1
\gcd (a,b)=1\ \land \ \gcd (a,c)=1\to \gcd (a,bc)=1
gcd(a,b)=1?∧?gcd(a,c)=1→gcd(a,bc)=1
a
s
1
+
b
t
1
=
1
=
a
s
2
+
c
t
2
→
b
t
1
=
1
?
a
s
1
,
c
t
2
=
1
?
a
s
2
→
b
c
t
1
t
2
=
1
?
a
s
1
?
a
s
2
+
a
2
s
1
s
2
→
a
(
s
1
?
s
2
+
a
s
1
s
2
)
+
b
c
(
t
1
t
2
)
=
1
as_1+bt_1=1=as_2+ct_2\to bt_1=1-as_1,ct_2=1-as_2\to bct_1t_2=1-as_1-as_2+a^2s_1s_2\to a(s_1-s_2+as_1s_2)+bc(t_1t_2)=1
as1?+bt1?=1=as2?+ct2?→bt1?=1?as1?,ct2?=1?as2?→bct1?t2?=1?as1??as2?+a2s1?s2?→a(s1??s2?+as1?s2?)+bc(t1?t2?)=1
QED -
gcd
?
(
a
,
b
c
)
=
1
→
gcd
?
(
a
,
b
)
=
1
?
∧
?
gcd
?
(
a
,
c
)
=
1
\gcd (a,bc)=1\to \gcd (a,b)=1\ \land\ \gcd(a,c)=1
gcd(a,bc)=1→gcd(a,b)=1?∧?gcd(a,c)=1
这是显而易见的，只要写出
a
s
+
b
c
t
=
1
as+bct=1
as+bct=1，注意到把
s
s
s和
c
t
ct
ct看作
a
,
b
a,b
a,b线性组合的系数就可得到
gcd
?
(
a
,
b
)
=
1
\gcd (a,b)=1
gcd(a,b)=1，同理也可得到后者。
20. 质数无限的相关证明
Question: 证明当
p
1
,
p
2
,
.
.
.
,
p
n
p_1,p_2,...,p_n
p1?,p2?,...,pn?是质数时，
p
1
p
2
?
p
n
+
1
p_1p_2\cdots p_n+1
p1?p2??pn?+1不能被这些质数整除。
Answer: 这题实际上是阿基米德证明质数无限的一个步骤。很显然
(
p
1
p
2
?
p
n
+
1
)
m
o
d
??
p
i
=
1
(p_1p_2\cdots p_n+1)\mod{p_i}=1
(p1?p2??pn?+1)modpi?=1，这意味着不能整除。
21. 质数无限相关证明
Question：证明存在无限个质数。
Answer: 采用阿基米德的方法证明，根据第20题，假定质数有限，为
p
1
,
p
2
,
?
?
,
p
n
p_1,p_2,\cdots ,p_n
p1?,p2?,?,pn?，最大质数为
p
n
p_n
pn?，那么总能构造出一个数
p
=
p
1
p
2
?
p
n
+
1
p=p_1p_2\cdots p_n+1
p=p1?p2??pn?+1不能被这些质数整除，根据算术基本定理Theorem 0.3，大于1的整数要么是质数，要么是质数之积，
p
p
p显然不是质数之积，因此是一个比
p
n
p_n
pn?更大的质数。与假设矛盾。
22. 复数计算
(
?
7
?
3
i
)
?
1
=
?
7
+
3
i
49
+
9
=
?
7
58
+
3
58
i
(-7-3i)^{-1}=\dfrac{-7+3i}{49+9}=-\dfrac{7}{58}+\dfrac{3}{58}i
(?7?3i)?1=49+9?7+3i?=?587?+583?i
23. 复数计算
?
5
+
2
i
4
?
5
i
=
(
?
5
+
2
i
)
(
4
+
5
i
)
16
+
25
=
?
20
+
8
i
?
25
i
?
10
41
=
?
30
41
+
?
17
41
i
\dfrac{-5+2i}{4-5i}=\dfrac{(-5+2i)(4+5i)}{16+25}=\dfrac{-20+8i-25i-10}{41}=\dfrac{-30}{41}+\dfrac{-17}{41}i
4?5i?5+2i?=16+25(?5+2i)(4+5i)?=41?20+8i?25i?10?=41?30?+41?17?i
24. 复数运算相关证明
Question: 证明复数满足
∣
z
1
z
2
∣
=
∣
z
1
∣
∣
z
2
∣
|z_1z_2|=|z_1||z_2|
∣z1?z2?∣=∣z1?∣∣z2?∣
Answer: 直接暴力计算，设
z
1
=
a
1
+
b
1
i
,
z
2
=
a
2
+
b
2
i
z_1=a_1+b_1i, z_2=a_2+b_2i
z1?=a1?+b1?i,z2?=a2?+b2?i，
∣
z
1
z
2
∣
=
∣
a
1
a
2
?
b
1
b
2
+
(
a
1
b
2
+
a
2
b
1
)
i
∣
=
(
a
1
a
2
?
b
1
b
2
)
2
+
(
a
1
b
2
+
a
2
b
1
)
2
=
a
1
2
a
2
2
?
2
a
1
a
2
b
1
b
2
+
b
1
2
b
2
2
+
a
1
2
b
2
2
+
2
a
1
a
2
b
1
b
2
+
a
2
2
b
1
2
=
a
1
2
a
2
2
+
b
1
2
b
2
2
+
a
1
2
b
2
2
+
a
2
2
b
1
2
=
(
a
1
2
+
b
1
2
)
(
a
2
2
+
b
2
2
)
=
∣
z
1
∣
∣
z
2
∣
|z_1z_2|=|a_1a_2-b_1b_2+(a_1b_2+a_2b_1)i|=(a_1a_2-b_1b_2)^2+(a_1b_2+a_2b_1)^2=a_1^2a_2^2-2a_1a_2b_1b_2+b_1^2b_2^2+a_1^2b_2^2+2a_1a_2b_1b_2+a_2^2b_1^2=a_1^2a_2^2+b_1^2b_2^2+a_1^2b_2^2+a_2^2b_1^2=(a_1^2+b_1^2)(a_2^2+b_2^2)=|z_1||z_2|
∣z1?z2?∣=∣a1?a2??b1?b2?+(a1?b2?+a2?b1?)i∣=(a1?a2??b1?b2?)2+(a1?b2?+a2?b1?)2=a12?a22??2a1?a2?b1?b2?+b12?b22?+a12?b22?+2a1?a2?b1?b2?+a22?b12?=a12?a22?+b12?b22?+a12?b22?+a22?b12?=(a12?+b12?)(a22?+b22?)=∣z1?∣∣z2?∣
25. 题目有点不懂，暂空
26. 模2运算
Question：在模2算术中描述
z
+
x
y
+
x
z
z+xy+xz
z+xy+xz的可能结果
Answer: 如果
x
=
0
x=0
x=0，输出
z
z
z，如果
x
=
1
x=1
x=1，输出
y
y
y
27. 子集数量证明
Question: 证明对于任何包含
n
(
n
>
0
)
n (n> 0)
n(n>0)个元素的集合，有
2
n
2^n
2n个子集。
Answer：包含
0
0
0个元素的子集只有
1
1
1个，空集。包含
1
1
1个元素的集合则有
n
n
n个，以个数分类，可以发现子集数目就是组合数相加：
C
n
0
+
C
n
1
+
?
+
C
n
n
=
2
n
C_n^0+C_n^1+\cdots +C_n^n=2^n
Cn0?+Cn1?+?+Cnn?=2n，因为它实际上也是
(
1
+
1
)
n
(1+1)^n
(1+1)n二项式展开。
28. 整除相关证明
Question: 证明
17
∣
(
2
n
3
2
n
?
1
)
17\mid (2^n3^{2n}-1)
17∣(2n32n?1)
Answer: 很显然，取模进行计算即可：
(
2
n
3
2
n
?
1
)
m
o
d
??
17
=
(
2
n
9
n
?
1
)
m
o
d
??
17
=
(
1
8
n
?
1
)
m
o
d
??
17
=
(
1
?
1
)
m
o
d
??
17
=
0
(2^n3^{2n}-1)\mod{17}=(2^n9^n-1)\mod{17}=(18^n-1)\mod{17}=(1-1)\mod{17}=0
(2n32n?1)mod17=(2n9n?1)mod17=(18n?1)mod17=(1?1)mod17=0
29. 合数相关证明
Question: 证明：存在正整数
n
n
n，使得
n
,
n
+
1
,
n
+
2
,
?
?
,
n
+
200
n, n+1, n+2, \cdots , n+200
n,n+1,n+2,?,n+200都是合数。
Answer：显然，只要
n
n
n是
200
!
200!
200!即可
30. 欧几里得准则推广
Question:
p
p
p是质数，
p
∣
a
1
a
2
?
a
n
p\mid a_1a_2\cdots a_n
p∣a1?a2??an?，证明对某些
i
i
i，有
p
∣
a
i
p\mid a_i
p∣ai?
Answer: 反证，假定
p
p
p与所有的
a
i
a_i
ai?都互质，根据第19题的结果使用第一数学归纳法，可推出
p
p
p与
a
1
a
2
?
a
n
a_1a_2\cdots a_n
a1?a2??an?互质，与条件矛盾。
31. 算术基本定理相关证明
Question: 使用欧几里得准则的推广证明算数基本定理的分解唯一性。
Answer: 假定一个整数
a
a
a有两种质因子分解方式，将不同部分记为
p
1
,
p
2
p_1,p_2
p1?,p2?,将相同部分记为
p
p
p，显然
p
2
∣
p
1
?
∧
?
p
1
∣
p
2
p_2\mid p_1\ \land\ p_1\mid p_2
p2?∣p1??∧?p1?∣p2?，显然两种分解相同。
（这里可能写的有点不严谨）
32. 数学归纳法相关
Question: 7美元和9美元的任意数量硬币，不可表达的最大面值是多少？使用数学归纳法证明。
Answer：列出可表达的数：
7
,
9
,
14
,
16
,
18
,
21
,
23
,
25
,
27
,
28
,
30
,
32
,
34
,
35
,
36
,
37
,
39
,
41
,
42
,
43
,
44
,
45
,
46
,
48
,
49
,
50
,
51
,
52
,
53
,
54
?
7, 9, 14,16,18,21,23,25,27,28,30,32,34,35,36,37,39,41,42,43,44,45, \\46,48,49,50,51,52,53,54\cdots
7,9,14,16,18,21,23,25,27,28,30,32,34,35,36,37,39,41,42,43,44,45,46,48,49,50,51,52,53,54?
可以看出，
47
47
47应该是题目要求得数。
- 第一数学归纳法
显然，
48
=
3
?
7
+
3
?
9
48=3\cdot 7+3\cdot 9
48=3?7+3?9，满足条件
假定
n
>
48
n>48
n>48满足
n
=
7
s
+
9
t
n=7s+9t
n=7s+9t
显然，
s
≥
5
?
∨
?
t
≥
3
s\ge 5\ \lor\ t\ge 3
s≥5?∨?t≥3，因为它的相反情况下，
n
n
n不会大于
48
48
48
对于
n
+
1
=
7
s
+
9
t
+
(
7
?
4
?
9
?
3
)
=
7
?
(
s
+
4
)
+
9
?
(
t
?
3
)
=
7
s
+
9
t
+
(
?
7
?
5
+
9
?
4
)
=
7
?
(
s
?
5
)
+
9
?
(
t
+
4
)
n+1=7s+9t+(7\cdot 4-9\cdot 3)=7\cdot (s+4)+9\cdot (t-3)\\ =7s+9t+(-7\cdot 5+9\cdot 4)=7\cdot (s-5)+9\cdot (t+4)
n+1=7s+9t+(7?4?9?3)=7?(s+4)+9?(t?3)=7s+9t+(?7?5+9?4)=7?(s?5)+9?(t+4)
显然，递推可以继续，QED - 第二数学归纳法
显然，
48
,
49
,
50
,
51
,
52
,
53
,
54
,
55
48,49,50,51,52,53,54,55
48,49,50,51,52,53,54,55满足条件
那么对于
n
>
55
n>55
n>55，假定从
55
55
55到
n
n
n都满足，那么
n
=
n
?
7
+
7
=
7
s
+
9
t
+
7
=
7
(
s
+
1
)
+
9
t
n=n-7+7=7s+9t+7=7(s+1)+9t
n=n?7+7=7s+9t+7=7(s+1)+9t，QED
33. 使用良序性证明
Question：使用良序性证明第一数学归纳法
Answer：要求使用良序性，是为了让我们确定一个集合中最小的数。按这个思路考虑，采取反证法，假定数学归纳法的初始点满足性质
p
p
p和递推过程，无法保证所有大于初始点的整数满足
p
p
p，设集合
S
=
{
k
｜
k
不
满
足
p
}
S=\{k｜k 不满足 p\}
S={k｜k不满足p}，由良序性的性质可得，这个集合存在最小值，记为
k
0
k_0
k0?，且我们可知
k
0
?
1
k_0-1
k0??1满足性质
p
p
p，那么，这里与递推条件产生矛盾，故QED
34. 斐波那契数列相关证明
Question: 斐波那契数列：
f
1
=
1
,
f
2
=
1
,
f
n
=
f
n
?
1
+
f
n
?
2
f_1=1,f_2=1,f_n=f_{n-1}+f_{n-2}
f1?=1,f2?=1,fn?=fn?1?+fn?2?当
n
≥
3
n\ge 3
n≥3，证明:
f
n
<
2
n
f_n<2^n
fn?<2n
Answer: 显然，
n
=
3
,
4
,
5
n=3,4,5
n=3,4,5时满足条件
假定对于
n
>
5
n>5
n>5，从
5
5
5到
n
?
1
n-1
n?1的所有自然数都满足条件
那么对于
f
n
=
f
n
?
1
+
f
n
?
2
<
2
n
?
1
+
2
n
?
2
<
2
n
f_n=f_{n-1}+f_{n-2}<2^{n-1}+2^{n-2}<2^n
fn?=fn?1?+fn?2?<2n?1+2n?2<2n
故所证成立
35. 倍数相关证明
Question: 使用归纳法证明，对所有正整数
n
n
n，
n
3
+
(
n
+
1
)
3
+
(
n
+
2
)
3
n^3+(n+1)^3+(n+2)^3
n3+(n+1)3+(n+2)3总是
9
9
9的倍数。
Answer：显然，
n
=
1
n=1
n=1时，得
36
36
36是
9
9
9的倍数。假定
n
>
1
n>1
n>1也满足，即
n
3
+
(
n
+
1
)
3
+
(
n
+
2
)
3
n^3+(n+1)^3+(n+2)^3
n3+(n+1)3+(n+2)3是
9
9
9的倍数；那么对于
n
+
1
n+1
n+1有：
(
n
+
1
)
3
+
(
n
+
2
)
3
+
(
n
+
3
)
3
=
(
n
+
1
)
3
+
(
n
+
2
)
3
+
n
3
+
9
n
2
+
27
n
+
27
(n+1)^3+(n+2)^3+(n+3)^3=(n+1)^3+(n+2)^3+n^3+9n^2+27n+27
(n+1)3+(n+2)3+(n+3)3=(n+1)3+(n+2)3+n3+9n2+27n+27，显然是
9
9
9的倍数。
36. 题目有点看不明白，暂空
37. 模运算相关
Question： 找到所有的
n
n
n，使得
8
×
8
×
8
8\times 8\times 8
8×8×8与
4
4
4模
n
n
n同余。
Answer：显然有
1
，
2
，
4
1，2，4
1，2，4，更大的数后者一定余
4
4
4
512
512
512模
508
,
254
,
127
508,254,127
508,254,127为
4
4
4
38. 模运算相关
Question：证明所有整数
n
n
n满足
n
3
m
o
d
??
6
=
n
m
o
d
??
6
n^3\mod{6}=n\mod{6}
n3mod6=nmod6
Answer: 模
6
6
6共有
0
，
1
，
2
，
3
，
4
，
5
0，1，2，3，4，5
0，1，2，3，4，5这六种可能。
余数为
0
，
1
0，1
0，1时，显然满足条件
余数为
2
2
2时，
2
3
m
o
d
??
6
=
2
m
o
d
??
6
2^3\mod{6}=2\mod{6}
23mod6=2mod6
余数为
3
3
3，
3
3
m
o
d
??
6
=
27
m
o
d
??
6
=
3
m
o
d
??
6
3^3\mod{6}=27\mod{6}=3\mod{6}
33mod6=27mod6=3mod6
余数为
4
4
4，
4
3
m
o
d
??
6
=
16
×
4
m
o
d
??
6
=
16
m
o
d
??
6
=
4
m
o
d
??
6
4^3\mod{6}={16\times 4}\mod{6}=16\mod{6}=4\mod{6}
43mod6=16×4mod6=16mod6=4mod6
余数为
5
5
5，
5
3
m
o
d
??
6
=
25
×
5
m
o
d
??
6
=
5
m
o
d
??
6
5^3\mod{6}=25\times 5\mod{6}=5\mod{6}
53mod6=25×5mod6=5mod6
39. 模运算相关
Question：上午2点，再过3736个小时后是几点。
Answer：
3736
m
o
d
??
24
=
16
3736\mod{24}=16
3736mod24=16，那即是6 P.M.
40-56. 都与之前例子Check digit有关，没看那个例子，跳过
57. 证明函数特性
Question: 证明Theorem 0.8，函数的复合会传递一一，到上这些特性，和一一到上函数里逆的存在。
Answer：首先证明一一的传递
-
α
,
β
\alpha ,\beta
α,β are one-to-one, then
β
α
\beta\alpha
βα is one-to-one.
?
a
i
,
a
j
∈
A
\forall a_i, a_j\in A
?ai?,aj?∈A, 假设
α
(
a
i
)
=
b
i
,
α
(
a
j
)
=
b
j
,
β
(
b
i
)
=
c
i
,
β
(
b
j
)
=
c
j
\alpha (a_i)=b_i,\alpha (a_j)=b_j,\beta (b_i)=c_i, \beta (b_j)=c_j
α(ai?)=bi?,α(aj?)=bj?,β(bi?)=ci?,β(bj?)=cj?，显然，
c
i
≠
c
j
→
b
i
≠
b
j
→
a
i
≠
a
j
c_i\neq c_j\to b_i\neq b_j\to a_i\neq a_j
ci??=cj?→bi??=bj?→ai??=aj? -
α
,
β
\alpha ,\beta
α,β are onto, then
β
α
\beta\alpha
βα is onto.
?
c
i
∈
C
,
?
b
i
∈
B
,
?
a
i
∈
A
\forall c_i\in C, \exists b_i\in B,\exists a_i\in A
?ci?∈C,?bi?∈B,?ai?∈A - 对于函数
α
:
a
→
b
\alpha :a\to b
α:a→b，逆:
α
?
1
:
b
→
a
\alpha^{-1}: b\to a
α?1:b→a，onto保证了逆的定义域
B
B
B都有对应，one-to-one保证了逆中有唯一的元素和
b
b
b对应。
58. 等价关系和等价类相关证明
Question: 假定
S
S
S是实数集，如果
a
,
b
∈
S
a,b\in S
a,b∈S，定义
a
～
b
?
i
f
?
a
?
b
a\sim b\ \mathrm{if}\ a-b
a～b?if?a?b 是整数。证明
～
\sim
～是一个
S
S
S上的等价关系，描述
S
S
S的等价类。
Answer: 两个问题，分别写。
- 显然
a
～
a
a\sim a
a～a，因为
a
?
a
=
0
a-a=0
a?a=0;
a
～
b
→
b
～
a
a\sim b\to b\sim a
a～b→b～a, 差只是符号变了;
a
～
b
?
∧
?
b
～
c
→
a
～
c
a\sim b\ \land\ b\sim c\to a\sim c
a～b?∧?b～c→a～c, 实际上等价于两个整数相加仍是整数这个结论。
-
[
a
]
[a]
[a]，
a
a
a是
0
0
0到
1
1
1的所有实数即可。
59. 等价关系
Question: 假定
S
S
S是整数集，如果
a
,
b
∈
S
a,b\in S
a,b∈S，定义
a
～
b
?
i
f
?
a
b
≥
0
a\sim b\ \mathrm{if}\ ab\ge 0
a～b?if?ab≥0，
～
\sim
～是等价关系吗？
Answer：首先满足反身性，然后满足对称性，也满足传递性，所以是。实际上这个定义等价于两个整数是否同号。
60. 等价关系相关证明
Question：假定
S
S
S是整数集，如果
a
,
b
∈
S
a,b\in S
a,b∈S，定义
a
R
b
?
i
f
?
a
+
b
aRb\ \mathrm{if}\ a+b
aRb?if?a+b is even. 证明:
R
R
R是等价关系，并描述等价类。
Answer：实际上这个等价关系等价于奇偶性相同，反身性满足，两奇数/偶数之和必定是偶数；对称性满足，加法是对称的；传递性满足，因为同奇数同偶数这个特性肯定是可以传递的。等价类即
[
1
]
,
[
2
]
[1],[2]
[1],[2]
61. 等价关系相关证明
Question: 完成Theorem 0.7的证明，即两个元素属于同一无交子集
S
S
S，为一个等价关系。
Answer: 显然满足反身性，对称性。现在说明传递性：
a
,
b
∈
S
,
b
,
c
∈
S
1
a,b\in S,b,c\in S_1
a,b∈S,b,c∈S1?，如果
S
≠
S
1
S\neq S_1
S?=S1?，那么
S
∩
S
1
=
?
S\cap S_1=\emptyset
S∩S1?=?，与条件
S
,
S
1
S,S_1
S,S1?有公共元素
b
b
b矛盾，所以
S
=
S
1
S=S_1
S=S1?。
62. 质数相关证明
Question: 证明，
3
,
5
,
7
3,5,7
3,5,7是仅有的
3
3
3个连续的奇数，且是素数。
Answer: 对于任何大于3的连续三个奇数
n
,
n
+
2
,
n
+
4
n,n+2,n+4
n,n+2,n+4，考虑
n
m
o
d
??
3
n\mod{3}
nmod3的结果只能是
0
,
1
,
2
0,1,2
0,1,2，那么
(
n
+
2
)
m
o
d
??
3
(n+2)\mod{3}
(n+2)mod3的结果则只能
2
,
0
,
1
2,0,1
2,0,1,
(
n
+
4
)
m
o
d
??
3
(n+4)\mod{3}
(n+4)mod3的结果则是
1
,
2
,
0
1,2,0
1,2,0，可以注意到，必有一个能整除
3
3
3
63. 模相关运算
Question: 计算
3
100
3^{100}
3100和
2
100
2^{100}
2100的最后一个数字分别是。
Answer: 实际上就是模
10
10
10的结果。
3
100
m
o
d
??
10
=
8
1
25
m
o
d
??
10
=
1
3^{100}\mod{10}=81^{25}\mod{10}=1
3100mod10=8125mod10=1
2
100
m
o
d
??
10
=
1
6
25
m
o
d
??
10
=
(
6
?
3
6
12
)
m
o
d
??
10
=
(
6
?
6
3
)
m
o
d
??
10
=
6
2^{100}\mod{10}=16^{25}\mod{10}=(6\cdot 36^{12})\mod{10}=(6\cdot 6^3)\mod{10}=6
2100mod10=1625mod10=(6?3612)mod10=(6?63)mod10=6
64. 模运算相关证明
Question: 证明
x
2
?
y
2
=
1002
x^2-y^2=1002
x2?y2=1002没有有理数解。
Answer: 这个命题应该是错的，存在解
x
=
503
2
,
y
=
499
2
x=\dfrac{503}{2},y=\dfrac{499}{2}
x=2503?,y=2499?
65. 函数消去
Question: 假定
γ
\gamma
γ是一一到上的，证明：如果
α
γ
=
β
γ
\alpha\gamma=\beta\gamma
αγ=βγ，那么
α
=
β
\alpha=\beta
α=β
Answer: 直接右乘
γ
?
1
\gamma^{-1}
γ?1即可
|