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

Sunday, July 8, 2012

Please email your solutions to puzzles@cotpi.com.

### 3 comments

### Credit

This puzzle is based on:

- Hobson, Nick. "Solution to puzzle 83: Divisibility." Nick's Mathematical Miscellany. 31 Aug. 2004. 8 July 2012 <http://www.qbyte.org/puzzles/p083s.html>.

## 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

\begin{equation} \label{divisibility} 2^n \equiv 1 \pmod{p}. \end{equation}

From Fermat's little theorem, we know that

\begin{equation} \label{fermat} 2^{p - 1} \equiv 1 \pmod{p}. \end{equation}

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\).