Divisibility Multipliers

For each integer $p \gt 1$ coprime to $10$ there is a positive divisibility multiplier $m \lt p$ which preserves divisibility by $p$ for the following function on any positive integer, $n$:
$f(n) = (\text{all but the last digit of }n) + (\text{the last digit of }n) \cdot 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 \cdot 34 = 7797$: $76275$ and $7797$ are both divisible by $113$.$f(12345) = 1234 + 5 \cdot 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 $10^7$?

This problem requires the use of number theory. Let’s look at how to approach this sequentially.

To find the divisibility multiplier `m` for a given prime `p`, we need to notice that we can rewrite `f(n)` as `n mod 10 * m + n div 10` so the divisibility stays the same if `p` divides `n if and only if p` divides `f(n)`. Therefore, the modulus of `p` must be the same in both cases.

To explain this point, let’s use the example where `p = 113` and `m = 34`, if `n = 12345`, then `n mod 10 * m + n div 10` is `5 * 34 + 12345 // 10 = 1404` in Python’s syntax.

Another crucial point is that `p` and `10` are coprime. So, by Euler’s totient theorem, `10^(p-1) ≡ 1 (mod p)`. As a result, `10^(p-1) – 1` is certainly divisible by `p` (since it’s `0 (mod p)`).

This means that `m` should satisfy that `10m ≡ 1 (mod p)`, namely, `m` is the modular multiplicative inverse of `10 mod p`. As for how to calculate it, if we have the Euler’s theorem: `a^(phi(n)) ≡ 1 (mod n)` for integers a, n that are coprime, this means for `p` prime, `a^(p-1) ≡ 1 (mod p)`, and the inverse of a can be computed by `a^(p-2) (mod p)`, `10^(p-2) (mod p)` is the modular inverse of `10` modulo `p`.

We can summarize the algorithm into the following steps:

1. Generate all primes less than `n = 10^7` which are coprime to `10`, using the Sieve of Eratosthenes for instance.
2. For each prime `p`, calculate the divisor multiplier `m` as `pow(10, p-2, p)` in Python.
3. Return the sum of all `m`.

Note: The function `pow(10, p-2, p)` computes `10^(p-2)` modulo `p` in an efficient way.

This is Python’s solution to the problem:

“`
def generate_primes(n):
sieve = [False, False] + [True for _ in range(n-2)]
for x in range(2, int(n ** 0.5) + 1):
if sieve[x]:
for u in range(x*x, n, x):
sieve[u] = False
return {i for i in range(2, n) if sieve[i]}

def solve(n=10**7):
primes = generate_primes(n)
primes = primes – {2, 5} # Remove the numbers that aren’t coprime with 10
return sum(pow(10, p-2, p) for p in primes)

print(solve())
“`
This will give us the sum for the divisibility multipliers of the primes that are coprime with `10` and less than `10^7`.

More Answers: