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

Question

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?

Answer 1

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$.

Answer 2

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.