# Find all positive integers m so that for $n=4m (2^m - 1)$, $n | (a^m - 1)$ for all a coprime to n

Find all positive integers m so that for $$n=4m (2^m - 1)$$, $$n | (a^m - 1)$$ for all a coprime to n.

First, we try $$m=1$$. Then $$n=4$$, and clearly it is not true that $$4 | (a-1)$$ for all odd a.
For $$m=2,n=24.$$ Modulo 24, we have $$1^2 \equiv 1, 5^2 \equiv 1, 7^2\equiv 1, 11^2\equiv 1$$, so $$24$$ indeed divides all numbers of the form $$a^2-1$$ where a is coprime to 24.
Write $$m=2^q r$$ where $$r$$ is odd. Then by the CRT (Chinese Remainder Theorem), we just need to verify that $$a^m \equiv 1\mod 2^{q+2}$$ and $$a^m\equiv 1\mod (2^m-1)r$$ for all a coprime to n. Let $$a$$ be coprime to n. Note that a must be odd. Also, the order of a modulo $$2^{q+2}$$ divides $$2^{q+1}$$ by Euler's theorem. We also know that the order divides m by assumption, so the order must be a divisor of $$2^q$$. It would be useful to know when the order of a modulo $$2^{q+2}$$ equals $$2^{q+1}$$ as it could narrow down the possible values of m. Also, the order of a modulo $$(2^m-1)r$$ divides m.

As you've done, have

$$m = 2^{q}r \tag{1}\label{eq1A}$$

with $$r$$ being odd. Regarding your first congruence equation, i.e.,

$$a^{m} \equiv 1 \pmod{2^{q+2}} \tag{2}\label{eq2A}$$

note that $$q = 0$$ doesn't work. For any $$a \equiv 3 \pmod{4}$$ where $$\gcd(a,n) = 1$$, since $$m$$ is odd, then $$a^{m} - 1 \equiv 2\pmod{4}$$, so $$4 \not\mid a^{m} - 1$$.

Next, have

$$s = r(2^m - 1) \tag{3}\label{eq3A}$$

Note that $$a = s + 2$$ is relatively prime to $$n$$ so, since $$s \mid n$$ and $$n \mid a^m - 1$$, we get

$$s \mid (s + 2)^{m} - 1 \;\;\to\;\; s \mid 2^{m} - 1 \;\;\to\;\; r(2^m - 1) \mid 2^{m} - 1 \tag{4}\label{eq4A}$$

Since this means $$r(2^m - 1) \le 2^{m} - 1$$, we must have $$r = 1$$. Thus, from \eqref{eq1A}, this means that

$$m = 2^{q}, \;\; q \ge 1 \;\;\to\;\; n = 2^{q+2}(2^{2^q} - 1) \tag{5}\label{eq5A}$$

Also, your second congruence equation then becomes

$$a^{m} \equiv 1 \pmod{2^{m} - 1} \tag{6}\label{eq6A}$$

Using the Carmichael function, and also the $$p$$-adic valuation, we get for all primes $$p \mid 2^{m} - 1$$, where $$t = \nu_{p}(2^m - 1)$$, that

$$\lambda(p^t) = \varphi(p^t) = p^{t-1}(p - 1) \tag{7}\label{eq7A}$$

must divide $$m$$. However, since \eqref{eq5A} shows that $$m$$ is a power of $$2$$, then $$t = 1$$ and $$p - 1 \mid 2^{q} \;\to\;\; p = 2^{u} + 1, \; u \le q$$. Note this means $$u$$ must be a power of $$2$$, so $$p$$ is a Fermat prime, of which only $$5$$ are currently known. Going through the values of $$q$$, for $$q = 1$$ we get $$m = 2$$ which works as you've already noted. Next, for $$q = 2 \;\to\; m = 4$$, we get $$2^4 - 1 = 3 \times 5$$ which also works, with \eqref{eq2A} being satisfied since, for each integer $$j$$ there's an integer $$k$$ where $$(2j + 1)^2 = 8k + 1 \;\to\; (2j + 1)^4 = 64k^2 + 16k + 1 \equiv 1 \pmod{16}$$. With $$q = 3 \;\to\; m = 8$$, then

$$2^8 - 1 = (2^4 - 1)(2^4 + 1) = 3 \times 5 \times 17 \tag{8}\label{eq8A}$$

However, $$16 \nmid 8$$. Next, with $$q = 4 \;\to\; m = 16$$, we have

$$2^{16} - 1 = (2^8 - 1)(2^8 + 1) = 3 \times 5 \times 17 \times 257 \tag{9}\label{eq9A}$$

In this case, $$256 \nmid 16$$. Thus, we can skip checking $$q = 5 \;\to\; m = 32$$ since $$256 \nmid 32$$. Although we could also skip $$q = 6 \;\to\; m = 64$$, note that

$$2^{64} - 1 = (2^{32} - 1)(2^{32} + 1) = 3 \times 5 \times 17 \times 257 \times 65537 \times 641 \times 6700417 \tag{10}\label{eq10A}$$

In this case, we have that $$641 - 1 = 2^{7}\times 5$$ is not a power of $$2$$ (i.e., it's not a Fermat prime), so this doesn't work. Also, since for any $$q \gt 6$$ we have

$$2^{m} - 1 \equiv (2^{2^6})^{2^{q - 6}} - 1 \equiv 1 - 1 \equiv 0 \pmod{641} \tag{11}\label{eq11A}$$

no larger $$q$$ works either.

In conclusion, the only values of $$m$$ which work are $$2$$ and $$4$$.