Let $k\geq 2$ and $n_1, \dots, n_k \in \mathbf{Z}^+$. If $n_2 | (2^{n_1} -1)$, $n_3 | (2^{n_2} -1)$, $\dots$, $n_k | (2^{n_{k-1}} -1)$, $n_1 | (2^{n_k} -1)$, show that $n_1 = \dots = n_k =1$.
Problem
Source: Turkey TST 1990 - P6
Tags: abstract algebra, induction, number theory proposed, number theory
11.09.2013 18:26
I remembed that it is PEN problem.
11.09.2013 19:19
For each $j \in \mathbb{N}$ , Let $A_0^j = j$ , and $A_{n+1}^j = 2^{A_{n}^j}-1 $ , Note that$ A_i^{A_j^n} = A_{i+j}^{n}$. ( Sorry for such notation it can confused with the exponent). We divide the proof into steps Step 1 : If $m|n$ , we have $2^m -1 | 2^n-1$ , to that we can that $n=mq$ for some $q$ , and then one can factorize or use module arithmetic to see that , from that with the notation above. Note that : one can deduce that $m|n$ implies $A_i^m | A_i^n $ , and $A_i^{m}|A_j^{n}$ implies $A_{s+i}^{m}|A_{s+j}^{n}$ Step 2 : For $n,i \in \mathbb{N}$ , if $n|A_i^{n}$ , then $n=1$. To prove this suppose $n \neq 1 $ , so $n \geq 3 $ and $n$ is odd , so we can factorize $n=p_1 \cdots p_j$ say , where $p_1$ is the least prime in the factorization . Now it follows that $\text{ord}_{p_1}(2) | p_1-1$ , choose the least prime $q_1 |\text{ord}_{p_1}(2)$ , so that $ A_{i-1} \equiv 0 $ $\text{mod}(q_1)$ ( that 's because $A_i^n \equiv 0 $ $\text{mod}(p_1)$ can be written as $2^{A_{i-1}^n} \equiv 1$ $\text{mod}(p_1)$). We note that $q_1$ is not even (if it is even we have a contradiction since $A_{i-1}$ is odd , again we can find $q_2 < q_1 $ , so that $A_{i-2}^n \equiv 0 $ $\text{mod}(q_2)$ , where $q_2$ is not even for the same reasons , completing in that way (inductively) , we can find a prime $q_i < q_1 < p_1$ , such that $q_i | A_0^n = n$ which is absurd Step 3 : According to step one , one can see that $n_2 | (2^{n_1} -1), n_3 | (2^{n_2} -1), \dots, n_k | (2^{n_{k-1}} -1), n_1 | (2^{n_k} -1)$ can be written as \[ n_2|A_1^{n_1}, n_3 |A_1^{n_2}, \dots, n_k |A_1^{n_{k-1}}, n_1 | A_1^{n_k}\] . Note that for $i=1,\dots,k$ we have by step 1 \[ n_i|A_1^{n_{i-1}}|A_2^{n_{i-2}}|\dots|A_{k}^{n_i}\] , but by step 2 $n_i = 1 $
12.09.2013 03:23
I hope this is correct First observe, that if some $n_i=1$ then all $n_i$-s are equal to 1. That's easy induction (in reverse way than usually). Second let's $n_i\ne1$ for all $i$. Take (for particular $k$) the sequence of $n_i$ with smallest sum. Let WLOG $n_1$ is the smallest. Let $a=ord_{n_1}(2)$ (this surely exist, because $n_1|2^{n_k}-1$). Then $a|n_k$ so $a\le n_k$. If $a<n_k$, then we could change $n_k$ with $a$ and get sequence with smaller sum, which is absurd. Then $a=n_k$. But surely $a<n_1$, so $n_k<n_1$, which is absurd because $n_1$ is minimum of our sequence. Therefore we can't have sequence different from $n_i=1$ for all $i$. Q.E.D.
06.11.2018 18:09
One can also argue, similar to a previous post, using the smallest prime divisor; as follows: Clearly, all $n_1,n_2,\dots,n_k$ are odd numbers. In particular, if $n_i=1$ for some $i$, then, $n_{i+1}=1$ since $n_{i+1}\mid 2^{n_i}-1$, and continuing in this way, we deduce that $n_1=n_2=\cdots=n_k=1$. Now, suppose for the sake of contradiction that $n_i>1$ for every $i$. Let $n_k$ be the number which has the smallest smallest prime divisor\footnote{In other words, consider the set of all primes dividing one of $n_i$, take the minimum of that set, and choose $k$ such that the minimum divides $n_k$}. We have, $n_k\mid 2^{n_{k-1}}-1$. Denote this prime by $p$, we get $p\mid 2^{n_{k-1}}-1$. Also by Fermat, we have $p\mid 2^{p-1}-1$. Hence, $p\mid 2^{(n_{k-1},p-1)}-1$. However, since $p$ is the smallest such divisor, we have $(n_{k-1},p-1)=1$, hence, we get $p=1$, a contradiction. Remark: This should be an IMO Longlist problem, as far as I remember.