习题四

作者: 洛玖言 | 来源:发表于2019-10-11 13:32 被阅读0次

习题四

1

证明：连续 $n$ 整数中恰有一个被 $n$ 整除.

Sol:
易知，连续 $n$ 个整数可以表示为， $kn-i,kn-i+1,\cdots,(k+1)n-i-1\,\,(0\leqslant i<n)$
通过适当调整顺序可得模 $n$ 的完全剩余系.
知必存在一数与 $0$ 同余.
所以连续 $n$ 整数中恰有一个被 $n$ 整除.

2

3

(i) 证明：完全平方数模 3 同余于 0 或 1；模4 同余于 0 或 1；模 5 同余于 0，1 或 4.
(ii) 证明：完全立方数模 9 同余于 0 或 $\pm$ 1；整数的四次幂模 16 同余于 0 或 1.

(i)
Sol:
可用 $3n,3n+1,3n+2\,(n\in\mathbb{Z})$ 表示所有整数
$(3n)^2\equiv9n^2\equiv0\pmod{3}$
$(3n+1)^2=3(3n^2+2n)+1\equiv1\pmod{3}$
$(3n+2)^2=3(3n^2+4n+1)+1\equiv1\pmod{3}$
知上述结论成立.

同理也可用 $4n,4n+1,4n+2,4n+3$ 表示所有整数
$(4n)^2=4(4n^2)\equiv0\pmod{4}$
$(4n+1)^2=4(4n^2+2n)+1\equiv1\pmod{4}$
$(4n+2)^2=4(4n^2+4n+1)\equiv0\pmod{4}$
$(4n+3)^2=4(4n^2+6n)+1\equiv1\pmod{4}$
知上述结论成立.

同理也可用 $5n,5n+1,5n+2,5n+3,5n+4$ 表示所有整数
$(5n)^2=5(5n^2)\equiv0\pmod{5}$
$(5n+1)^2=5(5n^2+2n)+1\equiv1\pmod{5}$
$(5n+2)^2=5(5n^2+4)+4\equiv4\pmod{5}$
$(5n+3)^2=5(5n^2+6n+1)+4\equiv1\pmod{5}$
$(5n+4)^2=5(5n^2+8n+3)+1\equiv1\pmod{5}$
知上述结论成立.

(ii)
Sol:
可用 $3n-1,3n,3n+1\,(n\in\mathbb{Z})$ 表示所有整数
$(3n)^3\equiv27n^3\equiv0\pmod{9}$
$(3n+1)^3\equiv9(3n^3+3n^2+n)+1\equiv1\pmod{9}$
$(3n-1)^3\equiv9(3n^3-3n^2+n)-1\equiv-1\pmod{9}$

可用 $2n,2n+1\,(n\in\mathbb{Z})$ 表示所有整数
$(2n)^4\equiv16n^4\equiv0\pmod{16}$
$(2n+1)^4\equiv16(n^2+n)^2+8n(n+1)+1\equiv1\pmod{16}$
补： $n,n+1$ 中必有一为偶数，所以 $8n(n+1)\equiv0\pmod{16}$

综上所述，完全立方数模 9 同余于 0 或 $\pm$ 1；整数的四次幂模 16 同余于 0 或 1.
得证.

4

5

(i) 证明：当 $n\geqslant3$ 时， $\varphi(n)$ 是偶数；
(ii) 证明：当 $n\geqslant2$ 时，不超过 $n$ 且与 $n$ 互素的正整数之和是 $\dfrac12n\varphi(n)$ .

Sol:
当 $n$ 是奇数时，若存在一个 $0<i<\dfrac{n}2$ ，且 $(i,n)=1$ ，
都有 $(n-i,n)=1$ 且 $\dfrac n2<n-i<n$
所以对于任意的 $i$ 有 $(i,n)$ 都有 $n-i$ 与其一一对应.且不存在 $i=n-i$
所以此时 $\varphi(n)$ 为偶数.

当 $n$ 为偶数时， $\dfrac{n}{2}$ 为整数，且 $(n,\dfrac{n}{2})=\dfrac{n}{2}>1$
同样
若存在一个 $0<i<\dfrac{n}2$ ，且 $(i,n)=1$ ，
都有 $(n-i,n)=1$ 且 $\dfrac n2<n-i<n$

所以对于任意的 $i$ 有 $(i,n)$ 都有 $n-i$ 与其一一对应.且不存在 $i=\dfrac{n}{2}$
所以此时 $\varphi(n)$ 为偶数.

所以对与任意 $n\geqslant3$ ，都有 $\varphi(n)$ 时偶数.

(ii)
Sol:
对于任意的与 $n$ 互素的正整数 $i,\,(0<i<\dfrac{n}{2})$ ,有 $n-i$ 也与 $n$ 互素
每一对之和都为 $n$ 一共有 $\dfrac{1}{2}\varphi(n)$ 对与 $n$ 互素的正整数，
所以不超过 $n$ 且与 $n$ 互素的正整数之和是 $\dfrac12n\varphi(n)$ .
得证.

6

设 $n$ 为偶数， $a_1,\cdots,a_n$ 及 $b_1,\cdots,b_n$ 都是模 $n$ 的完系，则 $a_1+b_1,\cdots,a_n+b_n$ 不是模 $n$ 的完系.

反证法：
设 $a_1+b_1,\cdots,a_n+b_n$ 是模 $n$ 的完系，
设 $a_1,\cdots,a_n$ 模 $n$ 的求和为 $A=1+2\cdots+n=\dfrac{n(n+1)}{2}$
$b_1,\cdots,b_n$ 模 $n$ 的求和为 $B=1+2\cdots+n=\dfrac{n(n+1)}{2}$
$\because a_1+b_1,\cdots,a_n+b_n$ 是模 $n$ 的完系
$\therefore a_1+b_1+\cdots+a_n+b_n\equiv(1+2+\cdots+n)\equiv\dfrac{n(n+1)}{2}\pmod{n}$
又 $a_1+a_2+\cdots+a_n+b_1+b_2+\cdots+b_n\equiv n(n+1)\pmod{n}$
由上述两式可知
$\dfrac{n(n+1)}{2}\equiv n(n+1)\pmod{n}$
所以有 $\dfrac{n+1}{2}\equiv0\pmod{n}$
又 $n$ 为偶数，知与题设矛盾.
所以， $n$ 为偶数时， $a_1,\cdots,a_n$ 及 $b_1,\cdots,b_n$ 都是模 $n$ 的完系，则 $a_1+b_1,\cdots,a_n+b_n$ 不是模 $n$ 的完系.

7

8

9

10

11

12

13

用例 1 的方法，求满足下免同余式的 $x$ :
(i) $8x\equiv 5\pmod{23}$
(ii) $60x\equiv 7 \pmod{37}$

这边先引一下例一

例一

求满足 $24x\equiv7\pmod{59}$ 的所有 $x$ .

Sol:
由于 $(24,59)=1$ ，从而

$\begin{aligned} x\equiv&\dfrac{7}{24}\equiv\dfrac{7+59}{24}\equiv\dfrac{66}{24}\\ \equiv&\dfrac{11}{4}\equiv\dfrac{-48}{4}\\ \equiv&-12\pmod{59} \end{aligned}$

(i)
Sol:
由于 $(8,23)=1$ ，从而

$\begin{aligned} x\equiv&\dfrac{5}{8}\equiv\dfrac{5+23}{8}\equiv\dfrac{7}{2}\\ \equiv&\dfrac{7+23}{2}\\ \equiv&15\pmod{23} \end{aligned}$

(ii)
Sol:
由于 $(60,37)=1$ ，从而

$\begin{aligned} x\equiv&\dfrac{7}{60}\equiv\dfrac{7+37}{60}\equiv\dfrac{44}{60}\\ \equiv&\dfrac{11}{15}\equiv\dfrac{11+37}{15}\equiv\dfrac{48}{15}\\ \equiv&\dfrac{16}{5}\equiv\dfrac{16+37}{5}\equiv\dfrac{53}{5}\\ \equiv&\dfrac{53+37}{5}\equiv\dfrac{90}{5}\\ \equiv&18\pmod{37} \end{aligned}$

整数与多项式-【目录】

习题四

习题四

1

2

3

4

5

6

7

8

9

10

11

12

13

例一

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读