习题八

作者: 洛玖言 | 来源:发表于2019-10-27 21:03 被阅读0次

【Python爬虫】-笨办法学 Python 习题01-10
整数与多项式-【目录】
习题八
八上《赤壁》习题
【Python爬虫】-笨办法学 Python 习题18-26
【Python爬虫】-笨办法学 Python 习题18-26
【Python爬虫】-笨办法学 Python 习题27-34
【Python爬虫】-笨办法学 Python 习题27-34
【Python爬虫】-笨办法学 Python 习题13-17
【Python爬虫】01作业

习题八

1

设 $p$ 是奇素数， $g$ 是模 $p$ 的一个原根. 求 $-g$ 对于模 $p$ 的阶.

Sol:
$\because g$ 是模 $m$ 的一个原根
$\therefore g^{p-1}\equiv 1\pmod{p}$
又 $p$ 是奇素数， $\Rightarrow p-1$ 为偶数
$\therefore (-g)^{p-1}\equiv1\pmod{p}$

2

设 $p$ 是奇素数. 证明：模 $p$ 的任意两个原根之积不是模 $p$ 的原根.

Sol:
任取模 $p$ 的两个原根 $m,n$ ，则 $m^{p-1}\equiv1\pmod{p},\;n^{p-1}\equiv1\pmod{p}$
$\therefore m^{\frac{p-1}2}\equiv-1\pmod{p},\;n^{\frac{p-1}{2}}\equiv-1\pmod{p}$
$\therefore(mn)^{\frac{p-1}{2}}\equiv1\pmod{p}$
$\therefore mn$ 不是模 $p$ 的原根.

4

设 $p$ 是奇素数，用模 $p$ 存在原根来证明威尔逊定理.

Sol:
因为 $p$ 是奇素数
$\therefore p$ 存在原根 $g$ . 且 $g,g^2,\cdots,g^{p-1}$ 构成模 $p$ 的一个缩系
$\therefore (p-1)!\equiv g\cdot g^2\cdots g^{p-1}\equiv g^{\frac{p(p-1)}{2}}\equiv(g^{p-1})^{\frac{p-1}{2}}\cdot g^{\frac{p-1}{2}}$
又 $g^{p-1}\equiv1\pmod{p}$
$\therefore g^{\frac{p-1}{2}}\equiv-1\pmod{p}$
$\therefore (p-1)!\equiv(g^{p-1})^{\frac{p-1}{2}}\cdot g^{\frac{p-1}{2}}\equiv-1\pmod{p}$
即 $(p-1)!\equiv-1\pmod{p}$

7

设 $n,a$ 都是正整数且 $a>1$ ，证明： $n|\varphi(a^n-1)$ .

Sol:
容易看出
$a^n\equiv1\pmod{a^n-1}$
且 $n$ 是满足上同余式的最小整数
又由欧拉定理得
$a^{\varphi(a^n-1)}\equiv1\pmod{a^n-1}$
$\therefore n|\varphi(a^n-1)$

8

设 $n>1$ ，证明： $n\not|\;(2^n-1)$

Sol:
若 $n|(2^n-1)$ ，则 $n$ 为奇数，设 $p$ 为 $n$ 最小的素因子，则 $p$ 为奇素数.
$\therefore$ 由费马定理 $2^{p-1}\equiv1\pmod{p}$ 即 $p|2^{p-1}-1$
又 $p|(2^n-1)$
$\therefore |(2^n-1,2^p-1)$
$\because(n,p-1)=1$
$\therefore(2^p-1,2^n-1)=2^1-1=1$
$\therefore p|1$ 显然矛盾
$\therefore n\not|\;(2^n-1)$