五千年(敝帚自珍)

主题:数学闲话(闲话开始前的闲话) -- 明日枯荷包

共:💬112 🌺684
全看分页树展 · 主题 跟帖
家园 数学闲话(一)——代数结构(3) 同余

一上来,看见被游识猷兄推举认证了,感谢一下游兄,也感谢一下支持的朋友。没说的,继续写。

话说光说不练假把式,光练不说傻把式,要又练又说,那才是真把式。前面谈了的代数结构啥的,大家说啦,你这加减乘除群环域都抽象出来,还叫抽象代数,可举些例子还是自然数实数之类大家都听厌了的,有新鲜一点的东西没?

这篇就讲个稍微新鲜点的东西。不过要开练了,就需要推导证明,数学就这样。所以也许会比较枯燥点,也需要大家自己拿张纸算算写写,以求能够较好地理解。这篇里的东西也是为把如何分摊秘密那篇东西继续写下去所做的准备工作之一,所以如果打算继续看那篇东西的朋友,这篇就不好跳过去不了解其中内容。

“同余”又是个行话,很牛B似的,其实很简单,就是“余数相同”的意思。

先取好一个自然数做被除数,比如10。每个整数都可以除以10,得到一个0到9之间的余数。如果整数以十进制表示就很简单,如果是大于等于0的整数,它除以10的余数就是十进制表示的个位数:

123456789/10 = 12345678*10 + 9

如果是小于0的整数,那么它除以10的余数,就是10减去十进制表示的个位数(如果个位是0,那就不用减了,余数当然还是0):

-123456789/10 = -12345679*10 + 1

如果有人问,123456*777777除以10的余数是多少,大家一般不会傻到先老老实实把123456*777777算出来,再除以10看余数。只要看两数的个位数,算6*7=42,42除以10的余数是2,所以123456*777777除以10的余数也是2。

又比如,算3^1001被10的余数是多少,拿3去自乘1001遍再看个位?也没人愿意那么干。可以这么算:

3^4=9^2=81, 个位是1

于是

3^1000=(3^4)^250是一个个位为1的数字的250次方,它的末尾数字当然也是1。于是3^1001次方的个位是1*3=3。

我们可以看出来,在做加法乘法甚至是多少次方这些运算的时候,如果只要知道结果被10除后的余数,那么参加运算的那些数具体是什么不是很重要,我们可以先用它们除以10后的余数来代替它们,然后再做运算,再算余数。要算123456*777777除以10的余数,我们就可以用6来代替123456,用7来代替777777。

其实呢,何止6可以代替123456,16也可以,-4也可以,甚至是123456789876也可以,只要是除以10的余数是6的那些数都可以代替123456,用它来计算123456*777777除以10的余数。当然方便不方便另讲,但是结果一定不会错。

123456,16,-4还是123456789876,除以10的余数是相同的(都是6),以行话来说,它们“对模10同余”。行话的真正目的当然不是吓唬人,而是为了把话说得精练而严格。看见行话的应付方法就是把行话翻译成你熟悉的话。比方说有人问:“25和-36对模10同余吗?”这是在问25和-36除以10的余数是否相同,你知道一个是5一个是4,不同,于是你回答“否。”

可以模10当然也可以模其他,比如问“7和21对模7同余吗?”,7和21除以7的余数都是0,所以答案是“是”。计算123456*777777除以7的余数是多少也一样,同样不用先计算乘积再计算余数,而可以先计算余数再计算乘积:尤其是777777除以7余0,0乘啥都是0,所以123456*777777除以7的余数是0。

3^1001被7的余数是多少?

3^3=27,而27和-1对模7同余(余数都是6),所以

3^999=(3^3)^333除以7的余数和(-1)^333的余数是一样的,后面这个我们一下看出来(-1)^333=-1。于是

3^1001除以7的余数和-1*3*3=-9除以7的余数一样,是5。

通过观察上面的计算,我们有一种感觉,就是要计算一些数互相加减乘后对除以某数的余数,我们不一定要先算出加减乘的结果再算余数。我们完全可以选择我们觉得方便的,和这些数同余的数去做计算。比如说刚才在算3^999=(3^3)^333除以7的余数时,3^3=27除以7的余数是6,但是接下去如果算6^333还是麻烦,而-1和6对模7同余,并且(-1)^333很好算,于是我们就拿-1来算。

既然如果是互相同余的(当然那个模几先要固定下来的,否则6和-1对模7同余,对模10可不同余),我们就可以换着用而不影响最终结果,那么我们也就不需要区别谁是谁了,对于模7来说,-1就是6,6就是-1;0就是7,7就是0;1就是8就是15就是22就是……

于是如果我们固定好模7,整数集合就被分成了7部分:和0同余的那些数,和1同余的那些数,和2同余的那些数,……,和6同余的那些数,我们可以分别把它们写成[0],[1],[2],……,[6]。想想[7],[8]或者[-1]等都是什么?和8同余的那些数不多不少正是和[1]同余的那些数,于是[1]=[8],同样地[0]=[7],[-1]=[6]。

这些[0],[1]……我们叫它们同余子集,因为每一个都是整数集的子集合。把每个子集合看作一个东西的话,按照前面所说,它们之间是可以做运算的:

[0]+[1] = [1]

[1]+[1] = [2]

……

[5]+[1] = [6]

[6]+[1] = [7] = [0]

最后这个式子有点特别对吧,但是其实很容易理解:除以7余数为6的数,加上除以7余数为1的数,其结果除以7的余数是0。同样地我们也有比如

[6]+[5] = [11] = [4]

[3]+[4] = [7] = [0]

减法也没问题。[0]这个东西很特别,无论谁加[0]还是它自己,跟整数里的0一样,行话叫”零元“。

乘法也一样,比如:

[5]*[5] = [25] = [4]

[2]*[4] = [8] = [1]

等等。[1]这个东西很特别,无论谁乘[1]还是它自己,跟整数里的1一样,行话叫”么元“。

如果我们考虑乘法的逆运算是除法,上面两个式子暗示着我们似乎有

[4]/[5] = [5]

[1]/[4] = [2]

这点其实是最有趣的地方,不过我们晚点再来看这事。

考虑模10的话也能定义出这些东西来,只不过现在有10个同余子集[0],[1],……,[9]。也有类似的加法和减法和乘法,乘法有点特别,比如

[2]*[5] = [10] = [0]

两个不是0的东西乘在一起成[0]了。在模7的时候你就找不到这种情况,大家可以想想这是为什么。

无论如何,在模7或者模10的时候,我们可以推广到模n(其中n>1)的时候,我们都能够把整数集分割成n个子集,如果把这些子集看作单个的东西,这些东西之间可以做加减乘的运算。于是,按照我们前面所说,可以做加减乘,这就是一个环。我们把它记作Zn(书上这个n是写成下标的,Z黑体,西西河上不好写下标,就将就这么写了)。比如上面我们看到,Z10里有10个元素,分别是[0],[1],……,[9]。我们前面看到的整数环,有理数域等等,里面都有无穷个元素,现在我们看到了一些只有有限个元素的环。

注意到Z7里有[0],[1],[2]等等,Z10里也有[0],[1],[2]等等,但此[0]非彼[0],之间没有关系。Z7里的元素们可以互相作运算,Z10里的也一样,但是你不可以用Z7里的[2]去加Z10里的[5],这就乱套了。当我们说这些[2]啊[5]啊的时候,必须首先已经知道了这是对模几说的,也就是Zn得固定下来。这是个细节,但是非常重要。

下一步,我们想办法要做除法,弄出个域来。

关键词(Tags): #数学闲话#代数#同余通宝推:瓷航惊涛,witten1,

本帖一共被 1 帖 引用 (帖内工具实现)
全看分页树展 · 主题 跟帖


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河