A Concise Introduction to the Th

A Concise Introduction to the Th

作者: 赫尔特 | 来源:发表于2019-08-25 20:01 被阅读0次

A Concise Introduction to the Theory of Numbers- Baker A
第3章

米莉姆
1.

更进一步，若自然数k满足 $ka\equiv ka'\ (mod\ n),那么$

$a\equiv a'\ (mod\ n/(k,n))，因为k/(k,n)和n/(k,n)互质$

2.中国剩余定理
$ax\equiv b\ (mod\ n)有解当且仅当(a,n)|b.$

必要性容易证明，下面证其充分性:

$假设d=(a,n),因为(a,n)|b$

$令a'=a/d,b'=b/d,n'=n/d$

$转化为证明a'x\equiv\ b'\ (mod\ n')有解$

$因为(a',n')=1,$

$所以a'x可以取得模n的一个完全剩余系中的所有值。证毕。$

特别地，
$当a满足:1\leq a \leq n，且(a,n)=1时，$

$a组成了一个叫“a\ reduced\ set\ of\ residues\ (mod\ n)”的东西$
（在一个完全剩余系中与n互质的数，假设就叫它n的互质系）

$比如:n=12,那么a可以是1,5,7,11$

假设 $(n,n')=1$ . 让 $a和a'分别取遍n与n'的互质系$

$可以得出an'+a'n取遍nn'的互质系(*)$

$即\phi(n)\phi(n')=\phi(nn')$

下面证明 $(*)$ 式：

1

3.费马小定理
对于任意的自然数a,如果p是素数，那么

$a^p\equiv a(mod\ p)$ .

特别地，如果 $(a,p)=1,$

$那么a^{p-1}\equiv 1(mod\ p)$

欧拉给出了更一般的结论:
$如果自然数(a,n)=1,那么$
$a^{\phi(n)}\equiv 1(mod\ n)$

$证明欧拉的结论:$
$如果x跑遍了n的互质系，那么ax也可以跑遍一个n的互质系$

$所以\prod(ax)\equiv \prod(x)(mod\ n)$

$(这里x取n的互质系里的所有值)$

$因为(x,n)=1,所以两边同时除掉x^{\phi(x)}$

$即得:a^{\phi(n)}\equiv 1(mod\ n)$

相关文章

网友评论

读书笔记

本文标题：A Concise Introduction to the Th

本文链接：https://www.haomeiwen.com/subject/diykectx.html

延伸阅读

深度阅读

您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

栏目导航

热点阅读

读书笔记

关于我们|服务条款|联系我们|A Concise Introduction to the Th|投稿指南|网站地图|RSS订阅|排版工具|手机版

提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网版权所有

备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！