美文网首页读书笔记
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

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

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