知识卡片

普通读书笔记卡 · 3698.a

模加法在全部剩余类上成群

理解等级:中级

模n的所有剩余类在加法下构成n元素的有限阿贝尔群。零类是单位元,[a]的加法逆元是[−a];代表元可以先正常相加,再对n取余,因为同余类的和不依赖代表元选择。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      Theorem 31.12 The system (ℤn, +n) is a finite abelian group. Proof Equation (31.19) shows that (ℤn, +n) is closed. Associativity and commutativity of +n follow from the associativity and commutativity of +: ([a]n +n [b]n) +n [c]n = [a + b]n +n [c]n = [(a + b) + c]n = [a + (b + c)]n = [a]n +n [b + c]n = [a]n +n ([b]n +n [c]

    参考来源

    - 位置:《算法导论(第4版)》第31章《数论算法》(OEBPS/chapter031.xhtml,文本字符[25000,30000))。 - 结论依据:原文给出最大公约数递推、扩展算法或模运算群的定义和证明;公式图已核对。 - 原始内容:Theorem 31.12 The system ( ℤ n , + n ) is a finite abelian group. Proof Equation (31.19) shows that ( ℤ n , + n ) is closed. Associativity and commutativity of + n follow from the associativity and commutativity of +: ([ a ] n + n [ b ] n ) + n [ c ] n = [ a + b ] n + n [ c ] n = [( a + b ) + c ] n = [ a + ( b + c )] n = [ a ] n + n [ b + c ] n = [ a ] n + n ([ b ] n + n [ c ]