之前看《初等数论及其应用》时一直都没有记笔记。。。

从这章开始记一些有趣的东西吧OvO

整数的阶

设a和n是互素的整数,使得a^x \equiv 1 (\bmod n)成立的最小正整数x称为a模n的阶

记作ord_na

易知ord_na \mid \phi(n)

原根

ord_nr=\phi(n)时,称r是模n的原根

一些性质

不是很懂。。。

一个正整数有原根当且仅当它为2,4,p^t,2p^t

如果r是n的原根,那么r^1,r^2,...,r^{\phi(n)}构成了模n的既约剩余系(n的完全剩余系中与n互素的数)

ord_na=t \implies ord_n(a^u)=t/(t,u)

由上式可以推出:若r是n的原根,其中n是一个大于1的正整数,那么r^u是模n的一个原根当且仅当(u,\phi(n))=1

如果正整数n有一个原根,那么它一共有\phi(\phi(n))个不同余的原根

书上第二到三节讲的是一些原根存在性的证明。。。不是很想看。。。

离散对数和指数的算术

假设m是一个有原根r的正整数。如果正整数a满足(a,m)=1,则使得r^x \equiv a (\bmod m)成立的唯一整数x称为a对模m的以r为底的指数(或叫离散对数),并记为ind_ra

离散对数和对数有着相同的性质

离散对数可以用来解k次剩余,但离散对数本身好像挺难求的。。。

假设m是个有原根的正整数。若k是一个正整数且a是一个与m互素的整数,那么x^k \equiv a (\bmod m)有解当且仅当a^{\phi(m)/d} \equiv 1 (\bmod m)其中d=(k,\phi(m)),且若有解则恰有d个不同余的解

后面是一些素性检验什么的。。。硬着头皮啃呗。。。

用整数的阶和原根进行素性检验

如果x满足x^{n-1} \equiv 1(\bmod n)x^{(n-1)/q}\neq(不同余) 1(\bmod n)q是n-1的任一素因子,则n是质数

有一个更有效的方法

如果x满足x^{(n-1)/2} \equiv -1(\bmod n)x^{(n-1)/q}\neq(不同余) 1(\bmod n)q是n-1的任一奇素因子,则n是质数

书上还提到了波克林顿素性检验和庞特素性检验

不想看...

通用指数

指的是一个正整数U使得对于所有与n互素的正整数a都有a^U \equiv 1(\bmod n)

比如n拆成n={p1}^{t1}{p2}^{t2}...{pm}^{tm},U可以是[\phi({p1}^{t1}),\phi({p2}^{t2}),...,\phi({pm}^{tm})]

最小通用指数记作\lambda(n),考虑求这个东西

若n有原根,则\lambda(n)=\phi(n),

若n为二的幂,则\lambda(2^t)=2^{t-2}

否则将n分解为n=2^{t0}{p1}^{t1}...{pm}^{tm}

\lambda(n)=[\lambda(2^{t0}),\phi({p1}^{t1}),...,\phi({pm}^{tm})]

且存在一个整数a满足ord_na=\lambda(n)这是一个整数对模n最大可能的阶

后面又讲了卡迈尔数。。。不大想看。。。


告别纷扰,去寻找生活的宝藏。