0%

Problem 274


Problem 274


Divisibility Multipliers

For each integer p > 1 coprime to 10 there is a positive divisibility multiplier m < p which preserves divisibility by p for the following function on any positive integer, n:

f(n) = (all but the last digit of n) + (the last digit of n) * m

That is, if m is the divisibility multiplier for p, then f(n) is divisible by p if and only if n is divisible by p.

(When n is much larger than p, f(n) will be less than n and repeated application of f provides a multiplicative divisibility test for p.)

For example, the divisibility multiplier for 113 is 34.

f(76275) = 7627 + 5 * 34 = 7797 : 76275 and 7797 are both divisible by 113
f(12345) = 1234 + 5 * 34 = 1404 : 12345 and 1404 are both not divisible by 113

The sum of the divisibility multipliers for the primes that are coprime to 10 and less than 1000 is 39517. What is the sum of the divisibility multipliers for the primes that are coprime to 10 and less than 107?


整除性乘数

对于任意与10互质的正整数p > 1,存在一个正整除性乘数 m < p,能够让任意正整数n在下面这个函数的作用下保持其对p的整除性:

f(n) = (n除最后一位数字之外的部分) + (n的最后一位数字) * m

也就是说,如果m是p的整除性乘数,那么f(n)能被p整除当且仅当n能被p整除。

(当n远大于p时,f(n)将会比n小,重复这个过程提供了快速检验能否被p整除的方法。)

例如,113的整除性乘数是34。

f(76275) = 7627 + 5 * 34 = 7797 : 76275和7797都能被113整除
f(12345) = 1234 + 5 * 34 = 1404 : 12345和1404都不能被112整除

对于所有小于1000且与10互质的素数,其整除性乘数之和是39517。对于所有小于107且与10互质的素数,其整除性乘数之和是多少?