0
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Why are you putting a bounty on this ? What more are you expecting after Robert Israel's answer ? $\endgroup$ May 18 '19 at 12:33
  • $\begingroup$ 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)? $\endgroup$
    – bob
    May 20 '19 at 14:05
  • $\begingroup$ 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$?" $\endgroup$
    – user326210
    May 22 '19 at 1:23
  • $\begingroup$ Yes, that's the question. $\endgroup$
    – bob
    May 22 '19 at 13:13
1
+50
$\begingroup$

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

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.