返回题库

循环移位乘以 4

Cyclic 4

专题
Brainteaser / 脑筋急转弯
难度
L6

题目详情

求最小的正整数,它的末位数字是 4,且把末位数字移动到首位(例如 1234→4123)会使该数变为原来的 4 倍。

What is the smallest positive integer that ends with the digit 44 such that moving its last digit to the first position (i.e. 1234 => 4123) multiplies the original integer by exactly 44?

解析

设原数为 N=10k+4N=10k+4,其中 kkmm 位(即 0k<10m0\le k<10^m)。移位后得到

N=410m+k.N'=4\cdot 10^m+k.

题意为 N=4NN'=4N

410m+k=4(10k+4)=40k+164(10m4)=39k.4\cdot 10^m+k=4(10k+4)=40k+16 \Rightarrow 4(10^m-4)=39k.

gcd(4,39)=1\gcd(4,39)=1,需 39(10m4)39\mid (10^m-4)。计算模 39:

10110, 10222, 10325, 10416, 1054(mod39).10^1\equiv 10,\ 10^2\equiv 22,\ 10^3\equiv 25,\ 10^4\equiv 16,\ 10^5\equiv 4\pmod{39}.

故最小 m=5m=5

于是

k=4(1054)39=42564=10256,k=\frac{4(10^5-4)}{39}=4\cdot 2564=10256,

所以

N=10k+4=102564.N=10k+4=102564.

验证:410256=4×102564410256=4\times 102564

答案为 102564\boxed{102564}