模运算

模运算,有时被称为模运算或时钟算法在其最基本的形式,算术完成与计数,重置本身零每次某个整数N大于1,即模数(mod)。例子是24小时的数字时钟系统,将自己重置为0(午夜N= 24),和一个在360度圆形量角器明显(N= 360)。模运算是很重要的数论,这是一个基本工具的解决方案丢番图方程(尤其是那些限制整数解决方案)。概括主题导致重要的19世纪试图证明费马最后定理和发展的重要部分近世代数。

下模运算(modN),唯一的数字是0,1,2,…,N−1,他们被称为残留模N。残留物被添加以通常的算术求和,然后从之和减去模量多少次就需要减少数量的总和米0到N−1包容。米被称为数字之和模吗N。使用德国数学家提出的符号卡尔•弗里德里希•高斯例如,在1801年,一个写2 + 4 + 3 + 7≡6(国防部10),读取符号≡”在哪里相等的”。

利用模运算的例子发生在古老的中国,印度和伊斯兰教文化。特别是,他们发生在日历的和天文问题,因为这些涉及周期(人为或自然),但是我们也可以发现模运算在纯粹的数学问题。从3臭名昭著——一个例子广告语文书,孙子的Sunzi suanjing(孙大师的数学手册),问

我们有许多的事情,但是我们不知道到底有多少。如果我们剩下三个有两个数。如果我们用剩下5我们有三个数。如果我们计算七剩下有两个。有多少东西?

这相当于要求的解决方案同时刻画X≡2 (mod 3),X≡3 (mod 5)X≡2(国防部7),一个解决方案是23。这类问题的一般解决方案被称为中国剩余定理。

瑞士数学家欧拉开创了现代方法同余约1750,当他明确引入了同余的概念模一个数字N和显示这个概念分区的整数N同余类,或残留类。两个整数在同一个模同余类N如果他们的区别是整除N。例如,如果N是5,那么−6和4是相同的成员同余类{…,−6,−1,4,9日…}。因为每个同余类可能是由它的任何成员,这个特殊的类,例如,“−6模5的同余类”或“4模5的同余类。”

在欧拉系统N数字在除留余数不同N可能代表同余类模吗N。因此,一个可能的系统运算模5将−2,−1,0,1,2。添加模同余类N从每个类被定义为选择任何元素,添加的元素放在一起,然后把同余类模吗N这属于之和作为答案。欧拉同样减法和乘法残留类的定义。例如,−3乘以4 (mod 5),第一次乘−3×4 =−12;自从−12≡3 (mod 5),解决方案是−3×4≡3 (mod 5)。欧拉表明一个会得到相同的结果的任何两个元素对应的同余类。

注意,当模量N不是质数,部门并不总是可能的。例如,1÷2≡3 (mod 5),因为2×3≡1 (mod 5)。然而,这个方程1÷2≡X(国防部4)没有一个解决方案,因为没有X这样2×X≡1 (mod 4)。当模数N不是质数,可以将一个类代表了吗r类为代表年代当且仅当年代和N互质(也就是说,如果他们唯一共同的吗因素1)。例如,7÷4≡4(国防部9)自4×4≡7 (mod 9)——这种情况下,7和9是互质。