Divisible Sandwiches

Relevant wiki: Factorization of Quadratics

Let $j=m+1$ and $k=n+1.$ Then the numbers can be expressed as follows:

$\begin{aligned} A &= 10^k+1 \\ B &= 10^j+1 \end{aligned}$

The goal is to make $\frac{B}{A}$ an integer for a given $n.$

$\begin{aligned} \frac{B}{A} &= \frac{10^j+1}{10^k+1} \\ &=10^{j-k}-\frac{10^{j-k}-1}{10^k+1} \end{aligned}$

Suppose that $10^{j-k}-1$ were a difference of squares. Specifically, let

$10^{j-k}-1=10^{2k}-1=(10^k+1)(10^k-1).$

Then $\frac{10^{j-k}-1}{10^k+1}$ would be an integer, and so $\frac{B}{A}$ would be an integer. In order for this to be true,

$\begin{aligned} j-k &= 2k \\ j &= 3k \\ m+1 &= 3(n+1) \\ m &= 3n+2 \end{aligned}$

And so, for any given $A,$ there exists a $B$ such that $A$ divides $B.$ Here are a couple of examples:

$\begin{aligned} \frac{1000001}{101} &= 9901 \\ \\ \frac{1000000001}{1001} &= 999001 \end{aligned}$

Relevant wiki: Factorization of Cubics

$\begin{aligned} A &= 10^{n+1} + 1 \\ B &= 10^{m+1} + 1. \end{aligned}$

Note that

$10^{3n + 3} + 1 = (10^{n+1})^3 + 1^3 = (10^{n+1} + 1)(10^{2(n+1)} - 10^{n+1} + 1).$

Therefore, if $m = 3n + 2,$ then $A|B$ so we conclude that yes , any $A$ has a multiple of this form.

$(10^n + 1) * (10^{2n} - 10^n +1) = 10^{3n} + 1$

It's simple enough to find a value for B given A using the formula above.

This solution is maybe less elegant, or uses heavier tools and concepts than other solutions, but I think it's quite nice as it shows the solution for every counting base $b$ . Moreover, it gives all possible solutions .

Consider working in base $b$ , than the question is: given $n$ , does there exist an integer $m$ (obviously $m>n$ ), s.t. $b^n+1$ divides $b^m+1$ . (The original question is for $b=10$ ).

This can be rewritten as $b^m+1=0\ mod\ (b^n+1)$ and then $b^m=-1\ mod\ (b^n+1)$ .

Now we notice that $gcd(b,b^n+1)=1$ , i.e $b ,\ b^n+1$ are relatively prime. There are numerous ways to show it, for example if $p$ is a prime divisor of $b$ , then $b=0\ mod\ p$ but always $b^n+1=1\ mod\ p$ , so they share no common prime divisors, and are thus relatively prime.

This means that $b$ is a member of $Z^*_{b^n+1}$ , the multiplicative group modulo $b^n+1$ .

By definition we know that $b^n=-1\ mod\ (b^n+1)$ . As $b^{2n}=(-1)^2=1\ mod\ (b^n+1)$ , every odd multiple of n works too:

For a positive integer $k$ , $b^{(2k+1)n}=((b^n)^2)^kb^n=((-1)^2)^k(-1)=1^k(-1)=-1\ mod\ (b^n+1)$ , making it a valid solution.

Thus $m=(2k+1)n$ , for every positive integer k, is a valid solution. In other words, every positive $m=n\ mod\ (2n)$ is a valid solution.

These are the only solutions, as $<b>$ , the subgroup of $Z^*_{b^n+1}$ generated by $b$ , is cyclic, and in a cyclic group there is no more than one element of order 2 - in this case the element $b^n=-1$ .

(More specifically, $<b>$ is isomorphic to $Z_{2n}$ , the additive group modulo $2n$ , via the isomorphism $f(b^k)=k\ mod\ (2n)$ , and $f(-1)=n$ , the only element of order 2).

Thus, every $m>k$ s.t. $m=n\ mod\ (2n)$ is a valid solution, (in other words, $m=(2k+1)n$ , for every positive integer k), and these are the only valid solutions .

▯

Notice something interesting - this solution does not depend on $b$ . Thus, for example, $\frac{1000001}{101}$ equals $9901$ if read in base 10, but if read as a binary number, then it is $\frac{1000001_2}{101_2}=\frac{65_{10}}{5_{10}}=13_{10}=1101_2$ , so it works in base 2, too. If interpreted as base 3, then $\frac{1000001_3}{101_3}=\frac{730_{10}}{10_{10}}=73_{10}=2201_3$ , thus the solution is also valid for base 3, and so on for every $b$ you please.

I think this is quite remarkable.

We all know that a^n + b^n is divisible by a+b if n is odd. For this case, 1000...001 can be written as 10^m +1 and 10^n +1 .Therefore,for every n , choose m=3n,we'll have 10^n+1 dividing (10^n)^3+1 = 10^m+1^3