2的多少次方末尾六位数为553344

2的多少次方末尾六位数为553344

设2^n的后六位为553344.
先看2的方幂的个位数字, 易见其以周期4循环:
2, 4, 8, 6, 2, 4, 8, 6,...
由2^n的个位为4, 可知n除以4余2, 可设n = 4m-2, m为整数.
可求得(2^4)^m = 2^(4m) = 2^n·2^2的后六位为213376.
再看2^4的方幂的后两位数字, 易见其以周期5循环:
16, 56, 96, 36, 76, 16, 56, 96,...
由(2^4)^m后两位为76, 可设m = 5k, k为整数.
(2^20)^k的后六位为213376.
2^20后三位为576, 易见其方幂的后三位以周期5循环:
576, 776, 976, 176, 376, 576, 776, 976,...
由(2^20)^k的后三位为376, 可设k = 5p, p为整数.
(2^100)^p的后六位为213376.
2^100后四位为5376, 易见其方幂后四位以周期5循环:
5376, 1376, 7376, 3376, 9376, 5376, 1376, 7376,...
由(2^100)^p的后四位为3376, 可设p = 5q-1, q为整数.
可求得(2^500)^q = (2^100)^p·2^100的后六位为309376.
2^500后五位为89376, 易见其方幂后五位以周期5循环:
89376, 69376, 49376, 29376, 09376, 89376, 69376, 49376,...
由(2^500)^q的后五位为09376, 可设q = 5r, r为整数.
(2^2500)^r的后六位为309376.
2^2500的后六位为509376, 其方幂后六位以周期5循环:
509376, 909376, 309376, 709376, 109376, 509376, 909376, 309376,...
由(2^2500)^r的后六位为309376, 可设r = 5s-2, s为整数.
n = 4m-2 = 4(5k)-2 = 20(5p)-2 = 100(5q-1)-2 = 500(5r)-102 = 2500(5s-2)-102 = 12500s-5102.
由以上的计算, 2^n的后六位为553344当且仅当n可表示为12500s-5102.
取s = 1, 可得最小的n = 7398.
最后解释一下, 上面所有计算至多只需计算最后六位, 因此手算还是较为可行的.
有时只需要不到六位, 例如计算2^100方幂的后四位循环就只需计算四位.
此外, 以后四位循环为例, 其后三位其实是不变的, 而千位上是其实等差数列, 只需计算两项.
而计算2^2500的后六位不需要乘2500次, 可以由2^500的后六位5次方得到.
2^500后六位可由2^100的后六位5次方得到, 进一步化到2^20 = 1048576.
所以整个计算量还是可接受的.