## Divisibility of the largest n-bit integer

What are the possible positive integer values of $$n$$ such that the largest $$n$$-bit integer is a multiple of $$n$$?

[SOLVED]

#### Rino Raj solved this puzzle:

The largest $$n$$-bit integer is $$2^n - 1$$, so we must find $$n$$ such that $$n \mid (2^n - 1)$$. We have $$n = 1$$ as a trivial solution.

Now let $$n \gt 1$$. Since $$2^n - 1$$, $$n$$ cannot be even. Let $$p$$ be the smallest prime that divides $$n$$ such that$$2^n \equiv 1 \pmod{n}$$. This implies that

$$\label{divisibility} 2^n \equiv 1 \pmod{p}.$$

From Fermat's little theorem, we know that

$$\label{fermat} 2^{p - 1} \equiv 1 \pmod{p}.$$

Now let $$k$$ be the smallest positive integer such that $$2^k \equiv 1 \pmod{p}$$. Clearly $$k \gt 1$$. As a consequence of Lagrange's theorem, \eqref{divisibility} and \eqref{fermat}, we have $$k \mid n$$ and $$k \mid (p - 1) \lt p$$. This contradicts our assumption that $$p$$ is the smallest prime that divides $$n$$. Hence there is no solution other than $$n = 1$$.

#### Tim Ophelders solved this puzzle:

The largest $$n$$-bit integer is $$2^n - 1$$. This is a multiple of $$n$$ iff $$2^n \equiv 1 \pmod{n}$$. $$\DeclareMathOperator{\ord}{ord}$$

Note that $$1$$ is a solution for $$n$$ because $$2^1 - 1 \equiv 1 \pmod{1}$$. To show that no solutions exist for $$n \gt 1$$, let $$p$$ be the smallest prime factor of $$n$$ such that $$2^n \equiv 1 \pmod{n}$$. Then $$2^n \equiv 1 \pmod{p}$$. Let $$q = \ord_p(2)$$, the multiplicative order of $$2$$ modulo $$p$$. We know that $$2^k \equiv 1 \pmod{p}$$ only if $$k$$ is a multiple of $$q$$, so $$q$$ divides $$n$$. Since $$2^{p-1} \equiv 1 \pmod{p}$$ by Fermat's little theorem and $$2^1 = 2 \not\equiv 1 \pmod{p}$$, therefore $$1 \lt q \lt p$$. This is a contradiction to our assumption that $$p$$ is the smallest prime factor of $$n$$. The only solution is therefore $$n=1$$.

#### quasi solved this puzzle:

There are no such values of n other than $$n = 1$$.

Assume otherwise. Let $$n$$ be the least positive integer greater than $$1$$ such that $$2^n \equiv 1 \pmod{n}$$. Since $$n \mid (2^n -1)$$, $$n$$ must be odd. Also, $$n$$ can't be prime, otherwise, by Fermat's little theorem, $$2^n = 2 \pmod{n}$$, contradiction. Thus, $$n$$ is odd and composite.

Let $$p$$ be the least prime factor of $$n$$ and let $$e$$ be the exponent of $$p$$ in the prime factorization of $$n$$. Let $$m = p^e$$, and let $$t = \varphi(m) = p^{e - 1} (p - 1)$$. Then $$2^n \equiv 1 \pmod{n} \implies 2^n \equiv 1 \pmod{m}$$. By Euler's theorem, we have $$2^t \equiv 1 \pmod{m}$$. It follows that $$2^s = 1 \pmod{m}$$ where $$s = \gcd(n, t)$$.

We can't have $$s = 1$$ otherwise $$2 \equiv 1 \pmod{m}$$ which yields $$p \mid 1$$, contradiction. Thus, $$s \gt 1$$. Then

\begin{align*} s &= \gcd(n, t) \\ &= \gcd(n, p^{e - 1}(p - 1)) \\ &= gcd(n, p^{e -1}) \\ &= p^{e - 1}. \end{align*}

Note that in the above reduction, we used the fact that $$p$$ was the least prime factor of $$n$$, and hence $$p - 1$$ must be relatively prime to $$n$$.

Since $$s > 1$$, we must have $$e > 1$$. Also $$s = p^{e - 1} \lt p^e \leq n$$. Thus, $$1 \lt s \lt n$$.

Finally, since $$s \mid m$$, $$2^s \equiv 1 \pmod{n} \implies 2^s \equiv 1 \pmod{s}$$, contrary to the minimality of $$n$$.

### Credit

This puzzle is based on: