2
$\begingroup$

I've tried to reduce to the case $k=2$, and have also tried to use the Chinese Remainder Theorem. However, it is not possible, since the terms in each equivalent relation are different. Could anyone give me some help?

The entire exercise:

Let $k\geq 2$ and $n_1,n_2, ..., n_k \geq 1$ natural numbers such that

$$ n_2 \mid (2^{n_1}-1)\\ n_3 \mid (2^{n_2}-1)\\ \dots\\ n_k \mid (2^{n_{k-1}}-1)\\ n_1 \mid (2^{n_k}-1). $$

Show that $n_1=n_2=...=n_k=1$.

$\endgroup$
3
  • $\begingroup$ It’s most likely that the last-but-one exponent on $2$ is $n_{k-1}$ and not $n_{k-1}-1$. $\endgroup$ – Jack LeGrüß Jan 17 at 18:49
  • 1
    $\begingroup$ The $k=2$ case is not trivial too. Looks related to Euler's Totient Theorem. $\endgroup$ – cr001 Jan 17 at 18:52
  • $\begingroup$ @JackLeGrüß you're right. Already editted! $\endgroup$ – Anyway142 Jan 17 at 20:07
3
$\begingroup$

The following proof is related to $n$ divides $2^n-1$ $\implies n=1$. First, if any $n_i$ is $1$, the right side of the $i$'th expression becomes $1$, so the corresponding value on the left side must be $1$, with this then extending to all of the rest of the values. Thus, assume none of the $n_i$ values is $1$.

Let $p_i$ be the least prime factor of $n_i$ for $1 \le i \le k$. Now, consider your first expression, i.e.,

$$n_2 \mid (2^{n_1} - 1) \tag{1}\label{eq1A}$$

The multiplicative order of $2$ modulo $p_2$ must divide $n_1$. However, $\operatorname{ord}_2{p_2}$ also divides the Euler's totient function of $p_2$, i.e., $p_2 - 1$, so

$$\operatorname{ord}_2{p_2} \le p_2 - 1 \tag{2}\label{eq2A}$$

Since $2^1 - 1 = 1$, all of the multiplicative orders must be $\gt 1$. Thus, $\operatorname{ord}_2{p_2}$ must have at least one prime factor less than $p_2$. Since $\operatorname{ord}_2{p_2} \mid n_1$, this means

$$p_1 \lt p_2 \tag{3}\label{eq3A}$$

Repeating this with your next expression gives

$$p_2 \lt p_3 \tag{4}\label{eq4A}$$

Combining with \eqref{eq3A}, this then becomes

$$p_1 \lt p_3 \tag{5}\label{eq5A}$$

Continuing this until the second last expression results with

$$p_1 \lt p_k \tag{6}\label{eq6A}$$

However, using the original argument (i.e., that which resulted in \eqref{eq3A}) with your last expression gives

$$p_k \lt p_1 \tag{7}\label{eq7A}$$

This contradicts \eqref{eq6A}, which means the original assumption all of the $n_i$ are not $1$ must be incorrect. Thus, all of the $n_i$ must be $1$.

$\endgroup$
3
$\begingroup$

For all $j \in \lbrace 1, \dotsc, k \rbrace$, we have $2^{n_{j}} -1 \mid 2^{\operatorname{lcm}\left( n_{1}, \dotsc, n_{k} \right)} -1$ since $n_{j} \mid \operatorname{lcm}\left( n_{1}, \dotsc, n_{k} \right)$, and hence $$n_{(j +1) \bmod k} \mid 2^{\operatorname{lcm}\left( n_{1}, \dotsc, n_{k} \right)} -1 \, \text{.}$$ It follows that $$\operatorname{lcm}\left( n_{1}, \dotsc, n_{k} \right) \mid 2^{\operatorname{lcm}\left( n_{1}, \dotsc, n_{k} \right)} -1 \, \text{,}$$ and hence $\operatorname{lcm}\left( n_{1}, \dotsc, n_{k} \right) = 1$ since $n$ does not divide $2^{n} -1$ whenever $n \geq 2$ (see For $n \geq 2$, show that $n \nmid 2^{n}-1$). Therefore, we have $$n_{1} = \dotso = n_{k} = 1 \, \text{.}$$

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.