# Can we construct a multiple of any number by repeating another arbitrary number twice?

Extension of this question: given a desired integer (non-necessarily prime) factor $$f$$, can we solve for some $$n$$ such that any arbitrary $$n$$ digit number repeated twice is a multiple of $$f$$?

Rationale: we can repeat an $$n$$ digit number twice by multiplying it by $$10^n+1$$, and the latter can have interesting factors. If it is true that as $$n$$ goes to infinity, all possible integer factors occur, then it would seem as though we could theoretically choose a factor $$f$$ and solve for $$n$$ so that any number of that length could be repeated twice to produce a multiple of our chosen factor $$f$$.

Is this possible?

• Why are you putting a bounty on this ? What more are you expecting after Robert Israel's answer ? May 18 '19 at 12:33
• I may have misunderstood his answer--it looked like it was a solution for the primes (which is awesome) and that there could remain a solution for non-prime factors (in which case that last part is what I'm seeking so we have a complete answer). Or did it exclude non-prime factors, and thus is the complete answer (if so I missed that last part)?
– bob
May 20 '19 at 14:05
• I want to make sure I understand. Is the question: "Given an integer factor $f$, can you find an integer $n$ such that every $n$-digit number, when repeated, is a multiple of $f$?" May 22 '19 at 1:23
• Yes, that's the question.
– bob
May 22 '19 at 13:13

## You can solve for $$n$$ only when all the prime factors of $$f$$ appear in this list: OEIS sequence A028416

For example,

• 2 doesn't appear in this list. You can't find $$n$$ such that the repetition of each $$n$$-digit number is a multiple of 2. Intuitively, this is because the repetition of a number is even if and only if the original number is a multiple of 2. So a range of numbers won't all have even repetitions.

• 7 does appear in this list. When you use the procedure below, you can solve for $$n$$ to find that all three-digit numbers have repetitions that divide evenly into 7.

Try it out: 100100, 101101, 102102, 103103, 104104, ..., 999999

• 14 = 2*7 doesn't work because one of its prime factors (2) is absent from the list.

• 77 = 7*11 works because both factors are in the list. Using the procedure below, you can solve for $$n$$ to find that all twenty-one digit numbers have repetitions that divide evenly into 7*11.

Try it out: 100000000000000000000100000000000000000000, 100000000000000000001100000000000000000001, 100000000000000000002100000000000000000002, ...

Pick a particular $$n$$. Because repeating is equivalent to multiplying by $$10^n+1$$, you know that the repetition of each $$n$$-digit number is a multiple of $$(10^{n}+1)$$. So, given a desired factor $$f$$, if you can find some $$(10^n+1)$$ which has $$f$$ as a factor, then the repetition of each $$n$$-digit number will have $$f$$ as a factor as well.

If the factor $$f$$ is 2 or 5, then you're out of luck: $$(10^n+1)$$ never has 2 or 5 as a factor, because $$10^n$$ always does. (Note that this failure makes intuitive sense: if you repeat all the numbers in a range, they won't all be even, for example. And you only get a multiple of five when repeating a number if the original number was also a multiple of five.)

If the factor $$f$$ is some prime number (other than 2 or 5), here's what you do.

1. We're looking for $$n$$ such that $$(10^n+1)$$ has $$f$$ as a factor. Equivalently, we want to find $$n$$ such that $$(10^n +1) \equiv 0$$, modulo $$f$$. Equivalently, we want to find $$n$$ such that $$10^n \equiv -1$$, modulo $$f$$.

2. Not every factor $$f$$ has a corresponding $$n$$, though some do. The following test will determine the answer.

3. To find out, consider the powers of 10: $$10^0, 10^1, 10^2, 10^3, \ldots, 10^f$$, modulo $$f$$. We're computing the remainder of $$f+1$$ numbers, but the remainders must all be in the range $$\{0,\ldots,f-1\}$$. By the pigeonhole principle, two of the numbers must have the same remainder. Call the smallest two such numbers $$10^a$$ and $$10^b$$, with the convention that $$a>b$$.

Because $$f$$ isn't a factor of 10, the fact that $$10^a \equiv 10^b$$ modulo $$f$$ implies that $$10^{a-b} \equiv 1$$, modulo $$f$$. This is an important step. Define $$k\equiv a-b$$ for short.

4. Note that the remainders of $$10^1, 10^2, 10^3, \ldots$$ form a cycle of period $$k$$. After all, $$10^0 \equiv 10^k$$, so $$10^1 \equiv 10^{k+1}$$, $$10^{2}\equiv 10^{k+2}$$, and so on.

In particular, the remainder of 1 appears in the cycle when, and only when, the exponent is a multiple of $$k$$.

5. We want to find a remainder of -1 in this cycle. If it exists, then in particular it should appear in the first loop of this cycle, in the remainders of $$10^0, 10^1, 10^2, \ldots, 10^k$$. If it exists, then it is a value of $$n$$ (where $$0\leq n\leq k$$) such that $$10^{n} \equiv -1$$. By squaring both sides, we learn that $$10^{2n} \equiv 1$$. By the previous bullet point, this means that $$2k$$ is a multiple of $$n$$.

But if $$k$$ is between 0 and $$n$$, and $$2k$$ is a multiple of $$n$$, then $$n$$ must be half of $$k$$.

6. Therefore: When $$f$$ is prime (and not a factor of 10), the desired value $$n$$ exists if and only if $$k(f)$$ (as found in step 3) is even. In that case, $$n\equiv k/2$$ has the desired property, as does $$n=k/2 + k$$,$$n=k/2 + 2k$$, $$n=k/2 + 3k$$, and so on, ad infinitum.

Robert's answer lists all the prime numbers $$f$$ where $$k(f)$$ is even (https://oeis.org/A028416). If a prime number is in this list, such an $$n$$ exists. Otherwise no such $$n$$ exists.

If $$f$$ is composite:

1. We can use a test like the one above to find $$k$$. There's a shortcut, though, if we factor $$f$$.
2. Divide $$f$$ into its prime factors $$f_1, \ldots, f_m$$, including multiplicities.
3. If any of those prime factors fail the test above, then $$f$$ fails the test. After all, failing the test means we can't find a range of numbers that are all multiples of $$f_i$$. This makes it impossible to find a range of numbers that are a multiple of $$f = f_1f_2\ldots f_i \ldots f_m$$.
4. On the other hand, if all of the factors pass the test, we get a collection of $$k$$ values $$k_1 \ldots k_m$$ that are all even. We know that all $$(k_i/2 + \square k_i)$$ digit numbers are multiples of $$f_i$$ (where $$\square$$ is any multiple). Or, to put it another way, $$n$$-digit numbers all have $$f_i$$ as a factor when, and only when, $$n$$ is an odd multiple of $$k_i/2$$.

5. So we are looking for a number $$n$$ which is simultaneously an odd multiple of $$k_1/2$$, an odd multiple of $$k_2/2$$, an odd multiple of $$k_3/2$$, and so on. (Interestingly, because odd multiples of a number have the same parity as that number, $$n$$ must have the same parity as $$k_1/2$$, $$k_2/2$$, and so on. Hence all $$k_i/2$$ must have the same parity as one another, or such an $$n$$ won't exist.)

6. If the numbers $$k_i$$ are all coprime, then the Chinese remainder theorem provides a construction for $$n$$.

If the numbers $$k_i/2$$ are all odd, then their product will be an odd multiple of each $$k_i/2$$; hence an acceptable choice for $$n$$.

More generally, I believe all of the $$k_i/2$$ must have 2 as a factor the same number of times. Otherwise, you can't find an odd multiple of all of them, so such an $$n$$ doesn't exist. So suppose there exists an exponent $$z$$ such that each $$k_i/2$$ is the product of $$2^z$$ an odd number $$r_i$$. Then $$n = 2^z r_1r_2r_3\ldots r_m$$ is an odd multiple of each $$k_i/2$$; hence an acceptable choice for $$n$$.

• This now has me wondering whether this can be generalized on the number of repetitions, so instead of 2 repetitions, $t$ repetitions...
– bob
May 23 '19 at 17:21

If $$f$$ is a prime other than $$2$$ and $$5$$, let $$m$$ be the multiplicative order of $$10$$ mod $$f$$, i.e. the least $$k$$ such that $$10^k \equiv 1 \mod f$$. If $$m$$ is even, then $$f$$ divides $$10^n+1$$ if and only if $$n = jm/2$$ for some odd $$j$$; if not, then there is no such $$f$$. The primes $$f$$ for which $$m$$ is even are OEIS sequence A028416.