Let $k\geq 2$,$n_1,n_2,\cdots ,n_k\in \mathbb{N}_+$,satisfied $n_2|2^{n_1}-1,n_3|2^{n_2}-1,\cdots ,n_k|2^{n_{k-1}}-1,n_1|2^{n_k}-1$. Prove:$n_ 1=n_ 2=\cdots=n_k=1$.
Problem
Source:
Tags: number theory, algebra
02.02.2017 10:06
Well known lemma : $2^n\equiv1\pmod n$ then $n=1$. Proof : If $n>1$ then there exists the smallest prime factor $p$ of $n$. Then $2^{(n,p-1)}=2^1\equiv1\pmod p$ so contradiction. Now remind that $a^n-1|a^m-1$ is equivalent to $n|m$. So $n_2|2^{n_1}-1|2^{lcm(n_1,n_2,\ldots ,n_k)}-1$, $\ldots$, $n_1|2^{n_k}-1|2^{lcm(n_1, n_2,\ldots ,n_k)}-1$ So $lcm(n_1,n_2,\ldots ,n_k)|2^{lcm(n_1,n_2,\ldots ,n_k)}-1$. By the lemma, the conclusion follows.
29.06.2020 22:29
$ n_{i}\leq 2^{n_{i-1}}\Rightarrow \sum_{1}^{k}a_{i}\leq \sum_{1}^{k}2^{a_{i}}-k,\sum_{1}^{k}2^{a_{i}}\geq 2k\Rightarrow \sum_{1}^{k}a_{i}\leq k\Rightarrow a_{i}=1$ is this right or i have somewhere a wrong logic?
30.06.2020 00:12
I think something is wrong...on my solution.Can anyone help me?
30.06.2020 04:42
lwwwww wrote: Let $k\geq 2$,$n_1,n_2,\cdots ,n_k\in \mathbb{N}_+$,satisfied $n_2|2^{n_1}-1,n_3|2^{n_2}-1,\cdots ,n_k|2^{n_{k-1}}-1,n_1|2^{n_k}-1$. Prove:$n_ 1=n_ 2=\cdots=n_k=1$. https://artofproblemsolving.com/community/c6h2125150p15557416
27.01.2021 22:39
24.12.2021 22:52
$$A=[n_1,n_2,\ldots ,n_k]$$$$A|2^A-1$$$$A=1$$$$n_ 1=n_ 2=\cdots=n_k=1$$
16.04.2022 20:39
Same question as 1990 Turkey Tst P6.
21.09.2024 04:07
Slightly different looking solution, I hope this works. First, say there exists some $n_i=1$. Then, $n_{i+1}\mid 2^{n_i}-1=1$ so $n+{i+1}=1$. By induction it follows that $n_j =1$ for all $i\le j \le k$. Thus, in what follows we assume that $n_j >1$ for all $1\le j \le k$. Clearly, none of $n_j$ are even, since $2\nmid 2^r-1$ for all positive integers $r$. Further, we consider the smallest prime $p$ which is a factor of one of $n_1,n_2,\dots , n_k$. Say $p\mid n_i$. Then, $p\mid n_i \mid 2^{n_{i-1}}-1$. Thus, $\text{ord}_p(2) \mid n_{i-1}$. Further by Fermat's Little Theorem, $\text{ord}_p(2) \mid p-1$. Now, if $\text{ord}_p(2)=1$ we have $2\equiv 1 \pmod{p}$ which is a clear contradiction for all primes $p>2$. Thus, $\text{ord}_p(2) >1$. Then, there exists a prime factor $q\mid \text{ord}_p(2)$. We have $q\mid \text{ord}_p(2) \mid p-1$ so $q\le p-1 <p$. But also since $q\mid \text{ord}_p(2) \mid n_i$, this means $q$ is a smaller prime factor of $n_i$ than $p$ which is a clear contradiction. Thus, this is a clear contradiction and we have no solutions where $n_j >1$ for all $1\le j \le k$ as desired.