春节趣味数论问题(张云勇/中国联通研究院) 求1234567891011...2018被693除的余数. 解方法一 因为693 = 11*9*7, 被9除的余数为2019*1009被9除的余数, 即3, 主要求被11除的余数, 被7除的余数, 继而求被99除的余数, 被63除的余数, 最终求被693除的余数 第一步, 求1234567891011...2018被11除的余数 计算奇数位(个位起)与偶数位的数字差. 1. 2000~2018:2000, 2001, 2002, ...., 2018. 显然, 偶位: 2*19+ 1*9 = 47; 奇位: 1 + 2 + .... + 9 + 1 + 2 + ....+ 8 = 45 + 36 = 81, 奇数比偶数多34. 2. 1000~1999共1000个数. 个位0~9各占1/10,即100个0, 100个1, ........., 100个9; 十位0~9各占1/10,同上; 百位0~9各占1/10,同上; 而千位全是1. 奇数位比偶数位多: (1 + 2 +3 + 4 + 5 + 6 + 7 + 8 + 9)*100 -1000*1 = 4500 - 1000 = 3500. 3. 三位的 (900个, 每两个一组, 共450组) 100, 101; 102, 103; ........ 198, 199; 200, 201; ........ 998, 999. 一二列与四五列完全相同, 奇偶互换, 相互抵消, 差别就在3、6列: 每组中, 奇数位比偶数位多1, 所以奇数位比偶数位多450. 4. 两位 这90个数, 奇位0~9的数字各出现9次, 偶位1~9各出现10次, 所以偶位数字多: 1 + 2 + ... + 9 = 45. 5. 一位: 123456789, 前面看成0, 则是0123456789 ,两个一组, 5组, 每组奇位多1, 奇位多: 1*5=5. 总的来看: 奇位比偶位多: (34 +3500 + 450 - 45 + 5) = 3944, 3944÷11=358……6. 求1234567891011...2018被11除的余数为6. 方法二 a = 1234567891011...2018一共6965位数. 10^4 =1(mod11), b = 123456789...99*10^6776 =1+ 23+ 45 + 67 + 89 + 10 + 11 + ... + 99 = 4(mod11), c = 100101...999*10^4076 = (999– 998 +997 – 996 + … + 101 - 100)*100 = 450*100= 10(mod11), d = 10001001...2018= (1000 + 1001 + ... 2018) = 1509*1019= 3(mod11). 所以, 1234567891011...20172018被11除的余数为 4 + 10 + 3 = 6(mod11). 第二步, 1234567891011....2018被99除的余数. 解被9除的余数为2019*1009被9除的余数, 即3, 等效于12, 21,30, 39; 1234567891011...2018被11除的余数为6, 等效于17, 28, 39, 50, 61. 所以被99除的余数为39(孙子定理). 第三步, 求a = 1234567891011...2018被7除的余数. 解a一共6965位数 10^3 +1 = 10^6 - 1 = 10^12 - 1(mod7), 30303= 300030003 = 0(mod7), b = 123456789*10^6956 = (123 - 456 +789)*10^2 = 2(mod7), c = 101112...99*10^6776 = (101112+ 131415 + … + 979899)*10^2 =30*101112*100= 2(mod7), d = 100101012...999*10^4076 = (999– 998 +997 - 996 +… + 101 - 100)*100 = 450*100= 4(mod7), e = 10001001...20172018 = 10001001+ 100210031004 + ... + 201620172018 = 10001001+ 100210031004*339 = 0(mod7). 所以, 1234567891011...20172018被7除的余数为 2 + 2 + 4 + 0 = 1(mod7). 第四步, 求1234567891011...2018被63除的余数. 被9除的余数为2019*1009被9除的余数, 即3, 等效于12, 21,30, 39, 48, 57, 66; 1234567891011...2018被7除的余数为1, 等效于1, 8, 15, 22, 29, 36, 43, 50, 57, 64, 71. 所以被63除的余数为57(孙子定理). 第五步, 1234567891011....2018被693除的余数. 被99除的余数为39, 等效于39, 138, 237, 336, 435, 534, 633. 所以被63除的余数为57, 等效于57, 120, 183, 246, 309, 372, 435. 所以, 1234567891011....2018被693除的余数为435 (孙子定理). 【附】关于头条号“许兴华数学”: |
|