学步园

昂。。。最近在学数论= =。。。真的是能死人的赶脚。

原根神马的= =。。。

原根：已知n，求使得 a^Ф(n)≡1 (mod n)成立的a。。。（多个）

下面的a,n全部都是gcd(a,n)=1 && n>0。

上来先搞的是已知a,n ，求最小的x使得a^x≡1 (mod n)

这里的x被叫做 a模n的阶，记作ord_na 。

定理1：a^x≡1 (mod n) 当且仅当ord_na | x  。

推论1.1： ord_na |Ф(n)  。因为由欧拉定理，a^Ф(n)≡1 (mod n)成立。

定理2：aⁱ≡a^j (mod n) 当且仅当i≡j (mod n) 。

定理3：如果r是模n的一个原根，那么下列整数构成了模n的既约剩余系（对n的余数互不相同）。

               r¹, r²,… r^Ф(n)

^{定理4：如果ord_na = r，那么有ord_n(au) = r/gcd(r,u) ，其中u是某个正整数。}

推论4.1：如果r是模n的一个原根 ，那么r^u  也是模n的一个原根当且仅当gcd(u,Ф(n))=1。

定理5：如果n有一个原根，那么它一共有Ф(Ф(n))个原根，即 r^u ,其中gcd(u,Ф(n))=1。