数论概论读书笔记 10.同余式、幂与欧拉公式

同余式、幂与欧拉公式

费马小定理很漂亮 $a^{p-1}\equiv 1(mod\ p)$

但限制P是素数且$p\nmid a$

如果p是合数,即使a、p互质,结论也不正确了

因此,研究是否有依赖模m的指数使得 $a^{???}\equiv 1(mod\ m)$

首先,如果a的某个幂模m余1,则a和m必互质(可由线性方程定理证明)

这再次提醒我们观察与m互素的数的集合: $$ {a:1\leqslant a\leqslant m,\quad gcd(a,m)=1} $$ 在1~m之间与m互质的整数个数 是个重要的量,我们赋予这个量一个名称: $$ \varphi(m)={a:1\leqslant a\leqslant m,\quad gcd(a,m)=1} $$ 函数$\varphi(m)$ 叫做欧拉函数

注意p是素数时,每个整数$1\leqslant a<p$ 都与p互素,所以对于素数p有公式 $$ \varphi(p)=p-1 $$ 我们设法模拟费马小定理的证明。例如,假设要求7的幂次模10余1,不取所有1~9,而是恰好取与10互素的数,它们是 $$ 1,3,7,9(mod\ 10) $$ 如果用7去乘每个数可得 $$ 7\cdot 1\equiv 7(mod\ 10)\quad 7\cdot 3\equiv 1(mod\ 10) \ 7\cdot 7\equiv 9(mod\ 10)\quad 7\cdot9\equiv 3(mod\ 10) $$ 得到的4个数是之前的4个数的重排!如果将它们乘起来就得到相同的乘积 $$ (7\cdot 1)(7\cdot 3)(7\cdot7)(7\cdot9)\equiv 1\cdot3\cdot7\cdot9 \qquad (mod\ 10) \ 7^4(1\cdot3\cdot7\cdot9)\equiv 1\cdot3\cdot7\cdot9 \qquad (mod\ 10) $$ 由于$1\cdot3\cdot7\cdot9$与$10$是互质的,因此可以消去,所以得到$7^4\equiv 1(mod\ 10)$ 这个形式和费马小定理很像了!

考虑这里的4和费马小定理中的$p-1$的共同点, 都是1~m中与m互质的数的个数!即欧拉函数 $\varphi(m)$

定理10.1(欧拉公式). 如果$gcd(a,m)=1$ ,则 $$ a^{\varphi(m)}\equiv 1 (mod\ m) $$ 引理10.2 如果$gcd(a,m)=1$,则数列 $$ b_1a,b_2a,b_3a,...,b_{\varphi(m)}a \qquad (mod\ m) $$ 与数列 $$ b_1,b_2,b_3,...,b_{\varphi(m)} \qquad (mod\ m) $$ 相同,尽管它们可能次序不同。

引理的证明 注意到$b_i$和a均与m是互质的,则$b_ia$也与m互质,又因为所有与m互质的数%m后依然与m互质 (如果x-km与m不互质,则x与m也不互质了) 所以数列$b_1a,b_2a,b_3a,...,b_{\varphi(m)}a \qquad (mod\ m)$ 同余于数列$b_1,b_2,b_3,...,b_{\varphi(m)} \qquad (mod\ m)$ 中的某一个数(因为就这$\varphi(m)$个)。又每个数列有$\varphi(m)$个数 ,因此,如果能进一步证明第一个数列中的数对于模m不同,则就得到两个数列(重排后)相同。 从第一个数列中任选两个数,假设它们是同余的,那么意味着$m|a(b_i-b_j)$ 由于a,m是互质的,因而有$m|b_i-b_j$ 又 $b_i ,b_j$在1与m之间,这说明$b_i=b_j$ 即第一个数列中的数模m是不同的。引理证毕。

证明欧拉公式

由引理知第一个数列中数的乘积等于第二个数列中数的乘积: $$ (b_1a)\cdot (b_2a)\cdot (b_3a)\cdot \ ...\ \cdot (b_{\varphi(m)}a) \equiv b_1\cdot b_2\cdot b_3 \cdot \cdot \cdot b_{\varphi(m)} \qquad (mod\ m) $$ 左边提出$\varphi(m)$个a得到 $a^{\varphi(m)}B\equiv B (mod\ m)$ 其中$B= b_1 b_2 b_3 \cdot \cdot \cdot b_{\varphi(m)} $

由于每个$b$与m都是互质的,因此$B$与m也是互质的 因此B可以消去 于是得到 $$ a^{\varphi(m)}\equiv 1 (mod\ m) $$ 证毕。

我们喜欢互质,其往往有不错的性质

习题

1.对于上面的$B$ ,试证明$B\equiv 1(mod\ m)$或$B\equiv m-1(mod\ m)$ 。并寻找m的模式(何时为1,何时为m-1)

hdu4910

威尔逊定理 Wilson定理的若干探讨

当m为素数时,B=$(m-1)!$ 由威尔逊定理,$(m-1)! \equiv m-1 (mod\ m)$

结论:

将m分解分所有质因子相乘,质因子2个数为a,其余质因子个数为b,$ans=(a==0?a:a-1)+b$ ; 当$ans$<2时结果为m-1,否则结果为1.

2.如果对每个整数$a$ ($gcd(a,m)=1$) ,同余式$a^{m-1} \equiv 1(mod\ m)$ 则称合数 m为卡米歇尔数(carmichael)

(1)验证m=561=3 * 11 * 17是卡米歇尔数。

因为561=3 * 11 * 17,若(a,561)=1,则(a,3)=(a,11)=(a,17)=1,由费马小定理知,$a^2\equiv 1(mod\ 3)$ , $a^{10}\equiv 1(mod\ 11)$ , $a^{16}\equiv 1(mod\ 17)$ 由于[2,10,16]=80,故$a^{80}\equiv 1(mod\ 3)$ , $a^{80}\equiv 1(mod\ 11)$ , $a^{80}\equiv 1(mod\ 17)$ 因此$a^{80}\equiv 1(mod\ 561)$ 故$a^{560}=(a^{80})^7\equiv 1(mod\ 561)$

(2)是否有无穷多个卡米歇尔数?

是 详见 (OEIS A002997)

注:

m是卡米歇尔数的充分必要条件是:

①m无平方因子;

②m的每一个素因子p有 $p-1\ |\ m-1$ ;

③m是奇数,且至少有三个不同的素因子。





评论

登录之后就可以评论 / 回复啦(#^.^#)    点此登录    点此注册

评论列表

暂无评论!快写一条吧(๑′ᴗ‵๑)