← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 3698.b.2.a

欧拉定理推广费马小定理

理解等级:中级

若n>1且gcd(a,n)=1,则a^φ(n)≡1(mod n)。

当n为素数p时φ(p)=p−1,得到a^{p−1}≡1(mod p),前提是p不整除a;另对所有整数a有a^p≡a(mod p)。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第31章 数论算法 · 查看原书依据

      Theorem 31.30 (Euler’s theorem) For any integer n > 1, ▪ Theorem 31.31 (Fermat’s theorem) If p is prime, then Proof By equation (31.22), ϕ(p) = p – 1 if p is prime. ▪ Fermat’s theorem applies to every element in ℤp except 0, since . For all a ∈ ℤp, however, we have ap = a (mod p) if p is prime. If , then every element in is a power of g, modulo n, and g is a primitive root or a generator of . For example,

    参考来源

    - 位置:《算法导论(第4版)》第31章《数论算法》(OEBPS/chapter031.xhtml,文本字符[50000,55000))。 - 结论依据:公式图 Art_P1203 的定理31.30为 a^φ(n)≡1 (mod n),条件 n>1、a∈ℤₙ*;Art_P1204 的定理31.31为 a^{p−1}≡1 (mod p),条件 p 为素数、a∈ℤₚ*。原文紧随其后给出 a^p≡a (mod p) 对所有 a∈ℤₚ 成立。 - 原始内容:Theorem 31.30 (Euler’s theorem) For any integer n > 1, ▪ Theorem 31.31 (Fermat’s theorem) If p is prime, then Proof By equation (31.22), ϕ ( p ) = p – 1 if p is prime. ▪ Fermat’s theorem applies to every element in ℤ p except 0, since . For all a ∈ ℤ p , however, we have a p = a (mod p ) if p is prime. If , then every element in is a power of g , modulo n , and g is a primitive root or a generator of . For example,