# For which $n$ does $2^n+1$ divide $10^n+1$?

This came up in a discussion of numbers that divide their own binary representation (when interpreted as a decimal). The question I'm asking zooms in on a special case:

For which $$n$$ does $$2^n+1$$ divide $$10^n+1$$?

I computed the remainder after division of $$10^n+1$$ by $$2^n+1$$ for $$1 \leq n \leq 300$$, which led me to suppose that there are no such $$n$$.

• For odd $n$ we can observe that $3 | 2^n + 1$, but - using the "lifting the exponent" lemma - we have $3 \not | 10^n + 1$, since $3 \not | 10 + 1$. EDIT: Or we can just use basic modular arithmetic.... Commented Jun 27, 2017 at 2:19
• I believe I've found a pattern that might be useful in this proof. We have $3|2^n + 1$, but then also $5|2^{4n + 2} + 1$, and $17|2^{8n + 4} + 1$ (because $2^4 \equiv 1 \mod(5)$ and $2^8 \equiv 1 \mod(17))$. In each instance, we can correspondingly see that $3 \not |10^n + 1$, that $5 \not |10^{4n+2} + 1$, and that $17 \not | 10^{8n + 4} + 1$. The pattern between $3, 5, 17...$ is that they are $2^{2^k} + 1$ for $k = 0, 1, 2$. It seems we might be able to get a contradiction proof this way - if I have time, I'll work on it further. Commented Jun 27, 2017 at 2:44
• 10^n+1=(8+2)^n+1=O(8)+2^n+1. 2^n+1 does not divide O(8) because it is odd and O(8) is even. Therefore it does not divide 10^n+1 . Commented Jun 27, 2017 at 3:59
• $10^n+1=(10^n-2^n)+(2^n+1)=2^n(5^n-1)+2^n+1$. Therefore we need to find $n$ which satisfies $2^n+1 | 5^n-1$. Commented Jun 27, 2017 at 4:58
• $n=0$ works ;) . Commented Jun 27, 2017 at 16:49

In comments on the question, Chris has proven all the cases other than $$$8|n. If$$n=8k$,

Assume $2^n+1$ divides $5^n-1$ (that is equivalent to the main question as you can see easily).

Take any prime $p$ that divides $2^{8k}+1$, then $p\neq 2,5$ obviously and

$$\Rightarrow p|2^{16k}-1$$

Assume $2^m||16k$ for some $m\geq4$,

Because $p$ does not divide $2^{8k}-1$,

$$\Rightarrow 2^m|p-1$$

Because $2^{8k}+1$ divides $5^{8k}-1$, $p$ divides $5^{8k}-1$,

$\Rightarrow$ 5 is square in modulo $p$.

$\Rightarrow \left (\dfrac {p}{5} \right ) \left (\dfrac {5}{p} \right )=(-1)^{\frac {p-1}{2} \frac {5-1}{2} }=1$

$\Rightarrow \left (\dfrac {p}{5} \right )=1 \Rightarrow$ $p$ is square in modulo 5.

$\Rightarrow p\equiv 1,-1 \pmod {5}$

$\Rightarrow$ all prime divisors of $2^n+1$ are of the form $5k+1$ or $5k-1$.

$\Rightarrow 2^n+1$ should be $\equiv 1,-1 \pmod {5}$,but $2^n+1=2^{8k}+1\equiv 2 \pmod {5} \Rightarrow \Leftarrow$.

• That's absolutely terrific. Thanks!
– R.P.
Commented Jun 28, 2017 at 0:02
• I don't see how Chris has proven all other cases. I only see that he found a possible pattern which implies a factor of $2^n+1$ must be of the form $2^{2^k}+1$ (which he has not proved as of yet). Can you please add the other cases you're referencing (including proof) to your answer so it is complete? Commented Jun 28, 2017 at 16:36
• What Chris is saying, I think, is that if $2^k$ is the highest power of $2$ dividing $n$, then $2^{2^k}+1$ divides $2^n+1$. (In fact, this is the observation that motivates the definition of the Fermat numbers $2^{2^k}+1$, since it proves no other numbers of the form $2^n+1$ can be prime.) This can be proven in an elementary way, using the following well-known fact: if $m$ is odd, then $a+1$ divides $a^m+1$ (even as polynomials). So writing $n = 2^k m$ with $m$ odd, it follows that $2^{2^k}+1$ divides $2^n+1$.
– R.P.
Commented Jun 28, 2017 at 17:12
• Applying this for $k=0$, it follows that if $n$ is odd, then $2^{2^0}+1=3$ divides $2^n+1$, whereas it's easy to see it doesn't divide $10^n+1$. For $k=1$, it follows that if $n$ is twice an odd number, then $2^{2^1}+1=5$ divides $2^n+1$, whereas it's even easier to see that it doesn't divide $10^n+1$. I haven't thought about the general divisibility of $10^n+1$ by numbers of the form $2^{2^k}+1$, but I'm sure you can do more with this line of argument if you want.
– R.P.
Commented Jun 28, 2017 at 17:16
• I can prove the following to myself.. If n is odd, then $3\mid 2^n +1$ but $3\nmid 5^n -1$. Therefore $n=2 n_1$ for some $n_1$. If $n_1$ is odd, then $5\mid 2^{2 n_1} +1$ but $5\nmid 5^{2 n_1}-1$. Therefore $n=4 n_2$ for some $n_2$. If $n_2$ is odd, then $17\mid 2^{4 n_2} +1$. However, I fail to prove to myself that $17\nmid 5^{4 n_2} -1$. Chris stated it without proof, and I don't see how to prove it. This is the only missing piece of the argument, because it would prove that $n = 8 n_3$ for some $n_3$, and @Merdanov's argument takes over. Commented Jun 28, 2017 at 18:27

Pleased as I am with Merdanov's great answer, I would like to reformulate it, including the bit supplied by Chris, so as to make it a bit more concise and compatible with my way of looking at these things.

First the part done by Chris (actually, he went further, but I am only using what I need):

Assume $2^n+1$ divides $10^n+1$. We prove that $n$ must be a multiple of $4$. Indeed, this was shown by Chris in the comments, since if $n$ were odd, we get $2^n+1 \equiv 0 \pmod{3}$ whereas $10^n+1 \equiv 2 \pmod{3}$, and if $n$ were $2\pmod{4}$ we would have $2^n+1 \equiv 0 \pmod{5}$ whereas $10^n+1 \equiv 1 \pmod{5}$.

As Chris suggested, we could probably go on with this line of reasoning; see the comments on Merdanov's answer for more on this.

So now to Merdanov's answer. I use some (very) basic group theory in my reformulation, which is already implicit in what Merdanov wrote.

First observe that $2^n+1$ must also divide $-(10^n+1)+5^n (2^n+1)$, which equals $5^n-1$. Let $p$ be a prime dividing $2^n+1$, then of course $p \mid 5^n-1$ as well, and $p \neq 2,5$. Since $p$ divides $2^n+1$ but not $2^n-1$, we have that $2n$ is a multiple of the order of $2$ in the cyclic group $C:=(\mathbb{Z}/p\mathbb{Z})^\times$, whereas $n$ is not. Let $2^m$ be the highest power of $2$ dividing $2n$. Then $2^m$ divides the order of $2$ in $C$, hence also divides the order of $C$.

Since $p \mid 5^n-1$, we have that $n$ is a multiple of the order of $5$ in $C$. Hence $2^{m-1}$ is the highest power of $2$ dividing the order of $5$ in $(\mathbb{Z}/p\mathbb{Z})^\times$, which means $5$ is a square in $(\mathbb{Z}/p\mathbb{Z})^\times$. By quadratic reciprocity, $p$ is a square modulo $5$, hence $p \equiv \pm 1 \pmod{5}$. Since $p$ was arbitrary, $2^n+1$ is a product of primes of the form $\pm 1 \pmod{5}$. Since we had already shown that $4 \mid n$, we get $2^n+1\equiv 1+1 \equiv 2 \pmod{5}$, which is a contradiction.

This does suggest that "the numbers worked in our favour". If $10$ hadn't been a multiple of $2$ (if this slight abuse of language is permitted), then we couldn't have played the orders of the two elements of $(\mathbb{Z}/p\mathbb{Z})^\times$ off against each other the way we did. Problems of the type where $a^n-1$ is supposed to divide $b^n+1$ would seem to be even more difficult to accomodate. But that would be a topic for some other time...