数论中的一点知识

今天突然看到python3基础教程中关于两个数取模、取整的运算,虽然以前接触过,但是突然发现对于负数的情况没理解记忆到位,特此整理一下思路做个小记录。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#取模(取余)
>>> 10 % 3
1
>>> 10 % -3
-2

#其实取余的本质是将“被除数”映射到以“除数”和“0”为端点的区间里,#所以这就是为什么10 % -3 = -2 而不是等于 1 。

#取整
>>> 10 // 3
3
>>> -10 // 3
-4
>>> -10 // -3
3

##有了取模(取余)的理解之后,取整就好理解了,即:产生余数过程中的关于除数的倍数。

##例子:
##关于求 -10 // 3 和 -10 % 3
##-10 - 3 ✖(-4)= 2
##所以-10 // 3 = -4 、 -10 % 3 = 2

后来让我突然回忆起了如何求模逆,想了一阵才回忆起来,一开始只是依稀记得是通过扩展欧几里得算法来做的,但是教材关于通过扩展欧几里得算法求模逆又臭又长,不便于实际手动计算,不想看教材,所以特此记录下,怕哪天忘记了这个便于理解的方法。

举一个小例子:求30 模 23 的模逆,即求30x mod 23=1中的x(x是{0,1,2,3,……,23}中的一个数)
30 = 23 ✖ 1 + 7 ①
23 = 7 ✖ 3 + 2 ②
7 = 2 ✖ 3 + 1 ③ (余数为1停止拆分)
改写②:23-7✖3=2
代入③:7=(23-7✖3)✖3+1
得: 7✖10=23✖3+1 ④

改写①:30-23✖1=7
代入④:(30-23✖1)✖10=23✖3+1
得: 30✖10-23✖13=1
30是被除数,23是除数,除数的系数-13即为所求,但是还得将-13映射到0到23之间,所以-13加上整数倍的23即可映射,所以结果为10。

注:扩展欧几里得算法的一个应用特例就是:若x与y是互质的,则存在整数a与b使得ax+by=1。