同余式

作者: 摇摆苏丹 | 来源:发表于2021-01-19 23:05 被阅读0次

表述

如果m | (a-b),就说a,bm同余,记为a \equiv b (mod \ m)
特别的,当a=qm+r的时候,余数rm同余。r \in \{1,2,\cdots,m-1\},任何整数都必然可以整除其中一个r

同余式的性质

如果有a_1 \equiv b_1 (mod \ m),a_2 \equiv b_2(mod \ m),则有:
\begin{array}{c} a_1 \pm a_2 \equiv b_1 \pm b_2 (mod \ m) \\ a_1 * a_2 \equiv b_1*b_2(mod \ m) \end{array}
这两条性质证明非常容易,此处略去不表。

a \equiv b (mod \ m)时,显然有:
a*c \equiv b*c (mod \ m)
但是:
a*c \equiv b*c (mod \ m) \to a \equiv b (mod \ m)
只有在gcd(m,c)=1,也就是c,m互质时成立。因为:
a*c \equiv b*c (mod \ m) \iff m \mid c(a-b)
m,c互质,则有m \mid a-b,即a \equiv b (mod \ m)

相关文章

  • 信息安全数学基础3——同余式

    解一次同余式的基本步骤 (1)判断同余式是否有解,以及同余式的解数 (2)化简原同余式 两边同时除以(a,m),之...

  • 近世代数理论基础7:同余式·中国剩余定理

    同余式·中国剩余定理 同余式 定义:给定整系数多项式,则称同余方程为模m的同余式,若,则称它为n次同余式 若,满足...

  • 同余式

    表述 如果,就说模同余,记为。特别的,当的时候,余数与同余。,任何整数都必然可以整除其中一个。 同余式的性质 如果...

  • 中国剩余定理

    表述 设为互素的整数,b与c为任意整数。那么同余式组:恰好有一个解。 证明 等价于,带入得。根据线性同余式定理,上...

  • 线性同余式定理

    引言 当同余式中存在未知数的时候,我们会关心未知数的取值,这可以与解方程类比。其中最简单的一种带未知数的同余式就是...

  • 求解一次同余式

    33x≡22(mod 77)解: 计算最大公因数(33,77)=11.因为(33,77)=11|22,所以原同余式...

  • 同余式与同余类

    第二章 同余 同余式与同余类 模 同余 设 是非零整数, 和 是整数. 如 ,则称 和 模 同余 (...

  • 模p多项式根定理

    引言 对于多项式方程,根据代数基本定理,我们能算出其根的数量。对于同余式,是否也有相似的定理?没错,它就是模p多项...

  • 行测-数量-奥数-数论知识及题目总结

    数论分为初等数论和高等。在初等数论中,中心问题是整数的整除性,主要包括:整除性、不定方程、同余式、连分数和素数分布...

  • 产品经理数学课(3)

    关键词:剩余,同余定理,数论,hash 参考:杨迎球,中国剩余定理与同余式组,[D]安顺学院数学与计算机科学系,2...

网友评论

      本文标题:同余式

      本文链接:https://www.haomeiwen.com/subject/mxfhzktx.html