1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .