《数论妙趣—数学女王的盛情款待》
“古怪的对数——回复原始”(节选)
出乎人们意料之外的是,一贯被认为专属连续领域的对数,居然在离散领域的数论中有着对等物。
在102=100中,2是100的对数。在103=1000中,3是1000的对数。对同样的底数10,某些大于100小于1000的中间数,比如500,其对数就位于2与3之间,准确到五位小数的值为2.69897。
但是,对于给定的模数而言,任意整数都可以准确地表示为某个合适的整数底的乘幂,在这种情况下,其指数或者说对数都是整数。
比如,取模为13,再任选一个底数,譬如2,让我们来看一看一切整数是怎样表示为2的乘幂的。此时有212≡1,21≡2,24≡3,22≡4,29≡5,25≡6,211≡7,23≡8,28≡9,210≡10,27≡11,26≡12。数与指数都没有重复,它们之间存在着一一对应。是否总是如此呢?让我们再用3来作底数试试。这时有31≡3,32≡9,33≡1,34≡3,35≡9,36≡1,37≡3,38≡9,39≡1,310≡3,311≡9,312≡1。虽然指数从1到12,可是对应的整数(剩余)却老是1,3,9。怎样才能解决这个问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
呢?
对于一个给定的模数,要想得到一个“完全剩余系”(即小于这个模数的所有整数),只能选用某些特定的底数才行;这些底数必须是模的任意一个“原根”。所谓质数p的原根g,是指使ge≡1 mod p得以成立的最小指数e必须为p-1。
整数13只有4个原根:2,6,7,11。它们每个数的乘幂,都能形成完全剩余系。
取原根2时的情况,上面已经说过。
取原根6时:
612≡1,65≡2,68≡3,610≡4,69≡5,61≡6,67≡7,63≡8,64≡9,62≡10,611≡11,66≡12。
取原根7时:
712≡1,711≡2,78≡3,710≡4,73≡5,77≡6,71≡7,79≡8,74≡9,72≡10,75≡11,76≡12。
取原根11时:
1112≡1,117≡2,114≡3,112≡4,113≡5,1111≡6,115≡7,119≡8,118≡9,1110≡10,111≡11,116≡12。
把13的4个原根所对应的数(余数)与指数,整理成指数表如下:
数(余数) 原根2 原根6 原根7 原根11
1 12 12 12 12
2 1 5 11 7
3 4 8 8 4
4 2 10 10 2
5 9 9 3 3
6 5 1 7 11
7 11 7 1 5
8 3 3 9 9
9 8 4 4 8
10 10 2 2 10
11 7 11 5 1
12 6 6 6 6
对数的实质就是指数。用对数做乘法,需将所乘各数的对数相加。类似步骤对于指数也行。不过,就质数p而言,根据费马小定理xp-1≡1 mod p,任何数的最大指数是p-1。因而在乘法问题中,如果指数超过p-1,可以去掉p-1的整数倍而结果不受影响。
如,对于质数5,根据费马小定理,24≡1 mod 5,即2的最大指数是4。于是:
213≡213-4≡213-8≡213-12 mod 5。
事实上,213=8192,8192÷5余2;213-4=29=512,512÷5余2;213-8=25=32,32÷5余2;213-12=21=2;2÷5余2。
下面用对数与指数分别求解两个问题,作个有趣的对比。前者选常用对数底10,后者选用模13的原根11。
求解6×8×9=x 求解6×8×9≡x mod 13
log106=0.77815 ind116=11 (ind是指数的缩写)
log108=0.90309 ind118= 9
log109=0.95424 ind119= 8
相加:log10x=2.63548 相加:ind11x=28
对数问题无需解释,反查对数表即得x=432;
根据费马小定理xp-1≡1 mod p,1112≡1 mod 13,从ind11x=28的指数28中,减去12(即p-1)的2倍24,得ind11x=28≡4 mod 12。反查上面的指数表,原根11的指数是4,对应数(余数)是3,所以x≡3 mod 13。即6×8×9≡3 mod 13。
事实上,6×8×9=432,432÷13余3,也就是6×8×9≡3 mod 13。