a^φ(n) ≡ 1 (mod n)
来源:学生作业帮 编辑:搜狗做题网作业帮 分类:数学作业 时间:2024/06/28 11:31:45
a^φ(n) ≡ 1 (mod n)
a^φ(n)中的φ(n)是什么,代表什么
若n,a为正整数,且n,a互素,(a,n) = 1,则 a^φ(n) ≡ 1 (mod n)
a^φ(n)中的φ(n)是什么,代表什么
若n,a为正整数,且n,a互素,(a,n) = 1,则 a^φ(n) ≡ 1 (mod n)
![a^φ(n) ≡ 1 (mod n)](/uploads/image/z/11639133-45-3.jpg?t=a%5E%CF%86%28n%29+%E2%89%A1+1+%28mod+n%29)
这是数论中的欧拉定理 φ(n)是一个函数即小于n与n互素的数的个数
证明
首先证明下面这个命题:对于集合Zn={x1,x2,...,xφ(n)},其中xi(i=1,2,…φ(n))是不大于n且与n互素的数,即n的一个化简剩余系,或称简系,或称缩系),考虑集合S = {a*x1(mod n),a*x2(mod n),...,a*xφ(n)(mod n)} 则S = Zn 1) 由于a,n互质,xi也与n互质,则a*xi也一定于n互质,因此 任意xi,a*xi(mod n) 必然是Zn的一个元素 2) 对于Zn中两个元素xi和xj,如果xi ≠ xj 则a*xi(mod n) ≠ a*xj(mod n),这个由a、n互质和消去律可以得出.所以,很明显,S=Zn 既然这样,那么 (a*x1 × a*x2×...×a*xφ(n))(mod n) = (a*x1(mod n) × a*x2(mod n) × ...× a*xφ(n)(mod n))(mod n) = (x1 × x2 × ...× xφ(n))(mod n) 考虑上面等式左边和右边 左边等于(a*(x1 × x2 × ...× xφ(n))) (mod n) 右边等于x1 × x2 × ...× xφ(n))(mod n) 而x1 × x2 × ...× xφ(n)(mod n)和n互质 根据消去律,可以从等式两边约去,就得到:a^φ(n) ≡ 1 (mod n) 推论:对于互质的数a、n,满足a^(φ(n)+1) ≡ a (mod n) 费马定理:a是不能被质数p整除的正整数,则有a^(p-1) ≡ 1 (mod p) 证明这个定理非常简单,由于φ(p) = p-1,代入欧拉定理即可证明.同样有推论:对于不能被质数p整除的正整数a,有a^p ≡ a (mod p)
证明
首先证明下面这个命题:对于集合Zn={x1,x2,...,xφ(n)},其中xi(i=1,2,…φ(n))是不大于n且与n互素的数,即n的一个化简剩余系,或称简系,或称缩系),考虑集合S = {a*x1(mod n),a*x2(mod n),...,a*xφ(n)(mod n)} 则S = Zn 1) 由于a,n互质,xi也与n互质,则a*xi也一定于n互质,因此 任意xi,a*xi(mod n) 必然是Zn的一个元素 2) 对于Zn中两个元素xi和xj,如果xi ≠ xj 则a*xi(mod n) ≠ a*xj(mod n),这个由a、n互质和消去律可以得出.所以,很明显,S=Zn 既然这样,那么 (a*x1 × a*x2×...×a*xφ(n))(mod n) = (a*x1(mod n) × a*x2(mod n) × ...× a*xφ(n)(mod n))(mod n) = (x1 × x2 × ...× xφ(n))(mod n) 考虑上面等式左边和右边 左边等于(a*(x1 × x2 × ...× xφ(n))) (mod n) 右边等于x1 × x2 × ...× xφ(n))(mod n) 而x1 × x2 × ...× xφ(n)(mod n)和n互质 根据消去律,可以从等式两边约去,就得到:a^φ(n) ≡ 1 (mod n) 推论:对于互质的数a、n,满足a^(φ(n)+1) ≡ a (mod n) 费马定理:a是不能被质数p整除的正整数,则有a^(p-1) ≡ 1 (mod p) 证明这个定理非常简单,由于φ(p) = p-1,代入欧拉定理即可证明.同样有推论:对于不能被质数p整除的正整数a,有a^p ≡ a (mod p)
a^φ(n) ≡ 1 (mod n)
a≡m(mod d) a^2 ≡n(mod d) 其中m,n什么关系?
(a+b) mod n 和[(a mod n) +b]mod n 有什么区别?
a,b,k为大于2的正整数a^k mod (k+1)=n;b^k mod (k+1)=m; 证明 n*m mod (k+
证明:若a≡b(mod m),那么a^n≡b^n(mod m),(其中n为非0自然数).
n mod 2 =
mod n指什么
VB解析 For n = 1 To 100 If n Mod 4 = 0 Then a = a & CStr(n) &
欧拉定理证明中:{既然这样,那么(a*x1 × a*x2×...×a*xφ(n))(mod n)= (a*x1(mod
举例证明同余的乘方性质:如果a ≡ b (mod m),那么a^n ≡ b^n (mod m)
Excel公式求助:mod(sum(N(sheet1!$A$1:$A1sheet1!$A$2:$A2)),2)?
a^b mod n 怎么用汇编实现