littletush wrote: Given an integer $n\ge 2$. Prove that there only exist a finite number of n-tuples of positive integers $(a_1,a_2,\ldots,a_n)$ which simultaneously satisfy the following three conditions: (1)$a_1>a_2>\ldots>a_n$; (2)$\gcd (a_1,a_2,\ldots,a_n)=1$; (3)$a_1=\sum_{i=1}^{n}\gcd (a_1,a_{i+1})$,where $a_{n+1}=a_1$. If $a_1=(a_1,a_2)+....+(a_1,a_1)$, then $(a_1,a_2)=....=(a_1,a_n)=0$ which is not acceptable, or am I mistaken somewhere??

@goodar2006 What do you mean? I'm confused. But anyways, seems a bit easy, I feel like I'm doing something wrong, so somebody should check it. First of all, there are only finitely many solutions of $b_i$ such that $\frac{1}{b_1} + \frac{1}{b_2} + ... + \frac{1}{b_n} = 1$ (an easy bound of $(2n)^n$ exists) OK, now suppose the problem is false for $n+1$. Remark that if we "strip off" all prime divisors of the $a_i$ for $i > 1$ such that the prime doesn't divide $a_1$ and then relax the inequalities to be $a_1 \ge a_2 \ge ... \ge a_{n+1}$ then it doesn't change the finiteness/infiniteness of the number of solutions (only divides the number of solutions by at most $n! \cdot n^n$) Now remark that after stripping off the excessive prime divisors we can make an injective relationship of a solution $(a_1, a_2, ... , a_{n+1})$ with a solution $(b_1, b_2, ..., b_n)$. Hence it follows the number of solutions is finite so we're done. EDIT : Nevermind I've found the flaw ignore this I know an easy fix though which I may or may not post later on. EDIT2 : Aha littletush changed the problem statement so this is totally wrong.

There is a mistake in my typing ,I've corrected it.

Let $ d_i = gcd(a_i,a_{i+1}) $ , because $ a_1 > a_2 > ... > a_n $ , we have $ a_1 - d_1 \geq a_2 ~,~ a_2 - d_2 \geq a_3 ~,~ ... ~,~a_i - d_i \geq a_{i+1} $ for $ i = 1,2,...,n-1 $ Putting them into the equation , we get this : $ d_1 + d_2 + ... d_n = a_1 \geq d_1 + a_2 \geq d_1 + d_2 + a_3 \geq ... \geq d_1 + ... + d_{n-1} + a_n $ so we have $ d_n \geq a_n $ but since $ d_n = gcd(a_1,a_n) \leq a_n $ , the equality holds . ie $ a_i - d_i = a_{i+1} $

simplependulum wrote: Let $ d_i = gcd(a_i,a_{i+1}) $ , because $ a_1 > a_2 > ... > a_n $ , we have $ a_1 - d_1 \geq a_2 ~,~ a_2 - d_2 \geq a_3 ~,~ ... ~,~a_i - d_i \geq a_{i+1} $ for $ i = 1,2,...,n-1 $ Putting them into the equation , we get this : $ d_1 + d_2 + ... d_n = a_1 \geq d_1 + a_2 \geq d_1 + d_2 + a_3 \geq ... \geq d_1 + ... + d_{n-1} + a_n $ so we have $ d_n \geq a_n $ but since $ d_n = gcd(a_1,a_n) \leq a_n $ , the equality holds . ie $ a_i - d_i = a_{i+1} $ Once we get the equality, $a_i=a_{i+1}+gcd(a_i,a_{i+1})$ for all $1\le i \le n-1$ and $a_n|a_1$ we can rewrite it as $a_i=\frac{r_i}{r_i+1}a_{i+1}$ for some positive integer $r_i$ Note that $gcd(a_2,a_3,...a_n)=1$ because $gcd(a_1,a_2,a_3,...a_n)=1$ and $a_n|a_1$ Then we apply induction to $n$. Assume $n-1$ is true, we have two cases. Case1: $a_2$ is not divisible by $a_n$, let $a_2=\frac{p}{q}a_n$, where $gcd(p,q)=1$ and $q$ is not equal to 1. Since $a_1=\frac{r_1}{r_1+1}a_{2}$ and $a_n|a_1$, that means $(\frac{p}{q})(\frac{r_1}{r_1+1})$ is an integer. When $a_2$ is fixed, it has only a limited number of $r_1$ satisfies the condition. Combined with limited solution in $n-1$, it is limited number of $(a_1,a_2,....a_n)$. Case2: $a_2$ is divisible by $a_n$, by induction assumption, we also have limited case of $(a_2,a_3,...,a_n)$ here and combined with the fact that limited number of $r_i$ satisfies the condition, it is limited number of $(a_1,a_2,....a_n)$ The proof is complete. ...when $n=2$, it is easy...

Aluminum wrote: Case1: $a_2$ is not divisible by $a_n$, let $a_2=\frac{p}{q}a_n$, where $gcd(p,q)=1$ and $q$ is not equal to 1. Since $a_1=\frac{r_1}{r_1+1}a_{2}$ and $a_n|a_1$, that means $(\frac{p}{q})(\frac{r_1}{r_1+1})$ is an integer. When $a_2$ is fixed, it has only a limited number of $r_1$ satisfies the condition. Combined with limited solution in $n-1$, it is limited number of $(a_1,a_2,....a_n)$. It seems not correct. How you apply the induction step in this case?

Nazar_Serdyuk wrote: Aluminum wrote: Case1: $a_2$ is not divisible by $a_n$, let $a_2=\frac{p}{q}a_n$, where $gcd(p,q)=1$ and $q$ is not equal to 1. Since $a_1=\frac{r_1}{r_1+1}a_{2}$ and $a_n|a_1$, that means $(\frac{p}{q})(\frac{r_1}{r_1+1})$ is an integer. When $a_2$ is fixed, it has only a limited number of $r_1$ satisfies the condition. Combined with limited solution in $n-1$, it is limited number of $(a_1,a_2,....a_n)$. It seems not correct. How you apply the induction step in this case? You are right. There is a flaw in the induction step. I found that we can solve the problem without using induction. (I hope so~) First we shall prove a lemma. Lemma: There are only finite number of $(n-1)$-tuples of positive integers $(r_1,r_2,...,r_{n-1})$ such that $(1+\frac{1}{r_1})(1+\frac{1}{r_2})...(1+\frac{1}{r_{n-1}})$ is an integer. Proof of lemma: We know that $(1+\frac{1}{r_1})(1+\frac{1}{r_2})...(1+\frac{1}{r_{n-1}})$ is bounded, (i.e. less than or equal to $2^{n-1}$). Assume $(1+\frac{1}{r_1})(1+\frac{1}{r_2})...(1+\frac{1}{r_{n-1}})=k$, where $k$ is a positive integer. Then there exists a $i$ such that $1+\frac{1}{r_i} \geq \sqrt[n-1]{k}$. In order words, $r_i$ is bounded by $\frac{1}{\sqrt[n-1]{k}-1}$. Take $r_i=1,2,...,[\frac{1}{\sqrt[n-1]{k}-1}]$ respectively, and $(1+\frac{1}{r_1})...(1+\frac{1}{r_{i-1}})(1+\frac{1}{r_{i+1}})...(1+\frac{1}{r_{n-1}})=\frac{k}{1+\frac{1}{r_{i}}}$. Repeating the process $n-2$ times, as $k$ is finite, we know that there are only finite number of $(n-1)$-tuples of positive integers $r_1,r_2,...,r_{n-1}$ such that $(1+\frac{1}{r_1})(1+\frac{1}{r_2})...(1+\frac{1}{r_{n-1}})$ is an integer. Back to the problem, we know that for $1\leq i \leq n-1$, we have $a_i-a_{i+1}|a_{i+1}$ and $a_n|a_1$. Therefore we can express $a_i=a_{i+1}(1+\frac{1}{r_i})$. Multiplying this $n-1$ equations, we get $\frac{a_1}{a_n}=(1+\frac{1}{r_1})(1+\frac{1}{r_2})...(1+\frac{1}{r_{n-1}})$. By the lemma, there are only finite number of $r_1,r_2,...,r_{n-1}$ satisfy the equation. Then we shall prove that for fixed $(r_1,r_2,...,r_{n-1})$, there are only finite number of $a_n$ which satisfy all 3 conditions. Let $p_1,p_2,...p_m$ be all the prime factors of $r_1r_2...r_{n-1}$, then $a_n$ must be in the form of $p_1^{b_1}p_2^{b_2}...p_m^{b_m}$, because if $a_n$ has a prime factor $q$, which is not the same as $p_i$, then $gcd(a_1,a_2,...,a_n)$ must be a multiple of $q$, contradiction! Let $r_1r_2...r_{n-1}=p_1^{c_1}p_2^{c_2}...p_m^{c_m}$, then we must have $b_i \leq c_i$ for all $1\leq i \leq m$. It is because if not, assume $b_j>c_j$ for some $j$, then $gcd(a_1,a_2,...,a_n)$ must be a multiple of $p_j$. Contradiction arises! As a result there are at most $(c_1+1)(c_2+1)...(c_m+1)$ choices of $a_n$. By counting the permutation of $(r_1,r_2,....r_{n-1})$, we know there are at most $(c_1+1)(c_2+1)...(c_m+1)(n-1)!$ choices of $(a_n,r_1,r_2,...,r_n)$. Notice that $(c_1+1)(c_2+1)...(c_m+1)(n-1)!$ is a finite and fixed number once we know what $r_1,r_2,...,r_n$ are. In conclusion, combining with the lemma, we know that there are only finite number of $n$-tuples satisfy all 3 conditions.

Solved with Janhavi Kulkarni Claim: $\gcd(a_i,a_{i-1}) = a_{i-1}-a_i$ $ \forall i=2,3,\dots , n$ \begin{align*} &\gcd(a_1,a_2) \leq a_1-a_2 \\ &\gcd(a_2,a_3) \leq a_2-a_3 \\ & \vdots \\ &\gcd(a_n,a_1) \leq a_n \\ \end{align*}Adding all the inequalities, we get that \begin{align*} a_1 & = \gcd(a_1,a_2)+\gcd(a_2,a_3)+\dots+\gcd(a_n,a_1) \\ &\leq a_1 -a_2 +a_2 - a_3 + \dots + a_{n-1}-a_n+a_n \\ &= a_1 \\ \end{align*}$\implies \gcd(a_i,a_{i-1}) = a_{i-1}-a_i \forall i=2,3,\dots , n$ and $a_n \mid a_1$ Define $d_i = \frac{a_{i}}{\gcd(a_i,a_i-1)} \forall i=2,3,\dots,n$ $\implies (1+\frac{1}{d_i}) = \frac{a_{i-1}}{a_i}$ As $a_n \mid a_1 \implies P = \prod_{i=2}^{n} (1+\frac{1}{d_i}) \in \mathbb{N}$ Lemma: For a finite $n \in \mathbb{N}$, only finitely many tuples ($d_2,d_3,\dots, d_n$) of positive integers satisfying the above condition exist Note that for any fixed $x \in \mathbb{R^+}$, for a sufficiently small $\epsilon >0$, $(x,x+\epsilon) \cap \mathbb{N} = \phi$ Ignoring reference to the problem, assume WLOG $d_2<d_3<\dots<d_n$ If $d_2$ is unbounded, then the product $P$ gets arbitrarily close to $1$ but is strictly greater than $1$ Hence it cannot be an integer $\implies d_2$ is bounded If there are infinitely many tuples at least one of the $d_i$ is unbounded. Let $r$ be the least such $i$ So the product $P' = \prod_{i=r}^{n} (1+\frac{1}{d_i})$ can get arbitrarily close to $1$ but strictly greater than $1$ For any choice of $d_2,d_3,\dots,d_{r-1}$, if $S = \prod_{i=2}^{r-1} (1+\frac{1}{d_i})$ then we can make $P'$ sufficiently close to $1$ such that $(S,S \times P) \cap \mathbb{N} = \phi$ Thus, only finitely many tuples exist for every finite $n \in \mathbb{N}$ $\forall i=1,2,3,\dots,n-1$ $ \frac{a_i}{a_n} = \prod_{r=i+1}^{n} (1+\frac{1}{d_r}) \implies a_n \mid a_i(d_nd_{n-1}\dots d_{i+1})$ So, if $c = d_2d_3\dots d_n$ then $a_n \mid a_i \times c$ $ \forall i=1,2,\dots,n-1$ \underline{Claim: } $a_n \mid c$ FTSOC, let $\exists$ prime $p$ such that $v_p(a_n) > v_p(c) \geq 0$ $\implies v_p (a_i) > 0$ $\forall i=1,2,\dots,n-1$ $\implies p\mid \gcd(a_1,a_2,\dots,a_n)=1$ Contradiction! Thus, $a_n \mid c$ $\implies a_n$ can only take finitely many values. Thus, only finite such sequences exist!