I am sorry.

May I know why is that diagram there ?

kk108 wrote: May I know why is that diagram there ? .............................

Let $A= \{ a,a+d, \cdots , a+(k-1)d \}$ and $G= \{ b,br, \cdots , br^{l-1} \}$. We must have $\min \{ a,b \}=1$ and $\max \{ a+(k-1)d, br^{l-1} \}=n$. If $n=a+(k-1)d$ then $\gcd ( n,a+(k-2)d)= \gcd (a,d)=a+(k-2)d$ since $a+(k-2)d \in A$. This follows $k=2$, a contradiction since $|A| \ge 3$. Thus, we must have $n=br^{l-1}$. WLOG, we can assume that $r \nmid b$ (otherwise let $b=r^su$). If $b$ is a composite number then $a=1$. Let $h$ be the largest divisor of $b$ ($1<h<b$) then $h^2 \ge b$ and $hr \not\in G$ implying $hr \in A$. But since $\gcd (hr+d,hr)=\gcd (d,hr)=\gcd(d,1+xd)=1$ and $hr+d \mid n=br^{l-1}$ we follow $hr+d \mid \frac{b}{h}$ implying $hr+d \le \frac{b}{h} <hr$, a contradiction. Note that $hr+d$ exists because if $hr=a+(k-1)d$ but $hr^2 \not \in G$ ($hr^2<br^2$ and $r \nmid b$) so $hr^2 \in A$ and $hr^2>hr$, a contradiction. Similar idea if $b$ is a prime. Since $r^2=1+dx$ then $\gcd (r^2,r^2-d)=1$, but $r^2-d \mid br^{l-1}$ so $r^2-d \mid b$, or $r^2-d=1$ or $r^2=1+d$. We do the similar thing with $r=1+dy$ to also get $r=1+d$, a contradiction. Thus, in all cases, we find $b=r^s$ (since we assume $r \nmid b$ earlier to make previous argument easier) and $n=r^{l+s-1}$. It's obvious that $r$ has to be a composite number (otherwise we can't split $D_n$ into $A$ and $G$). This means either $a=1$ or $a$ be the smallest prime divisor of $r$. If $a$ is the smallest prime divisor of $r$ then $b=1,n=r^{l-1}$. Since set $A$ contains all divisors of $r$ (except $1,r$) so if $a \mid d$ then $r$ can only have $a$ as prime divisor or $r=a^h$ with $h \ge 3$ to guarantee $|A| \ge 3$. Hence, $a+d=a^2$ or $d=a(a-1)$ and $a+2d=a^3$ or $a+2a(a-1)=a^3$ or $a=1$, a contradiction. Thus, $a \nmid d$. Let $a_1$ be the second smallest prime divisor of $r$ then $a_1 \in A$. We see that there cannot be any term between $a$ and $a_1$ (otherwise if $a+d \in A, a<a+d<a_1$ then $a \mid a+d$, a contradiction). This follows $a_1=a+d$ is a prime number. Note that $a+ad=a(1+d) \in A$ (since $a+ad<r$) and $1+d<a+d$ implying $1+d=a$. Since $1+d,2d+1$ are two smallest prime divisors of $r$ so either $1+d \mid 1+3d$ or $1+2d \mid 1+3d$. We obtain $d=1,a=2$, which will give $|A| \le 2$, a contradiction. Thus, $a=1$ and $n=r^{l+s-1} \; (s \ge 1)$. Similarly, we find $1+d,1+2d$ are two smallest prime divisors of $r$. Thus, either $1+d \mid 1+3d$ or $1+2d \mid 1+3d$, which both leads to a contradiction. Thus, there doesn't exist any natural number $n$ that satisfies the condition. I'm not sure about this answer, so maybe I'm missing some solutions during the argument. Please check. Thanks.

IMO1991 Q2 Let $ \,n > 6\,$ be an integer and $ \,a_{1},a_{2},\cdots ,a_{k}\,$ be all the natural numbers less than $ n$ and relatively prime to $ n$. If \[ a_{2} - a_{1} = a_{3} - a_{2} = \cdots = a_{k} - a_{k - 1} > 0, \]prove that $ \,n\,$ must be either a prime number or a power of $ \,2$.

adityaguharoy wrote: kk108 wrote: May I know why is that diagram there ? Because it shows the geometric interpretation of what is needed to be proved !! Very nice sqing Really ? I had thought about it but I wasn't sure .

sqing wrote: I am sorry. China Mathematical Olympiad 2017 Q2 I am sorry.

Let split this problem into $2$ main cases: $1.)$ $\underline{1\in A}$ Thus let $A=\{ 1,1+k,...,1+kx\}$, $x\in \mathbb{N}$. From $\gcd (1+kx_1,1+k(x_1+1))=\gcd(1+kx_1,k)=1\ . \ . \ . \ \bigstar$ Now let us split again this into $2$ subcases. $a.)$ $\underline{n\in A}$ $\Longrightarrow 1+kx=n\stackrel{\bigstar\Longrightarrow (n,1+k(x-1))=1}{\Longrightarrow}\text{contradiction}$ ____________________________________________________________________________________________ $b.)$ $\underline{n\in G}$ Let $G=\{ s,\ sq,\ ...,sq^z=n\}\Longrightarrow lcm \left(\prod_{i=1}^{x}(1+k\cdot i)\right)|n=sq^z\ . \ . \ . \ \clubsuit$ If $\underline{s=1}$ then $G=\{ 1,\ q,\ ...,q^z=n\}$.

) If $\underline{s>1}$

). By $\bigstar\Longrightarrow q^t$ and $q^{t-1}$ can't be consecutive elements in $A$, thus (again by $\bigstar$) in $A$ exists some $p\in \mathbb{N}$, such that $(p,q)=1\Longrightarrow p|s\stackrel{\bigstar}{\Longrightarrow} p-k\nmid s\text{ and } p+k\nmid s\Longrightarrow p-k|q\text{ and }p+k|q\stackrel{\text{if }(s,q)=1}{\Longrightarrow} \ . \ . \ . $ every second element in $A$ divides $q^z$ and other every second divides $s$. . . $\bigstar \bigstar$

)(denote it by $v$), thus $sq^{z-2}<v-k< sq^{z-1}< v <sq^z<v+k\stackrel{\bigstar \bigstar \text{ and 2. and 3. inequality}}{\Longrightarrow} v-k=s$, which is contradiction with $1.$ inequality, unless $z<2$, contradiction.

), but as it($\gcd(s,q)$) divides $s$ and $q$, then from $\bigstar$ we get contradiction. Assume that $\gcd(s,q)=q\Longleftrightarrow s=qx\Longrightarrow x\in A\Longrightarrow x+k| n$, which is contradiction with $\bigstar$. _____________________________________________________________________________________________ $2.)$ $\underline{1\in G}$ Thus let $G=\{ 1,q,q^2,...,q^d \}$ $a.)$ $\underline{n\in G}$ $\Longrightarrow G=\{ 1,q,q^2,...,q^d=n \}$

). Thus it has divisor $1<t<q$, which belongs to $A$, let we pick such $t$ that it is smallest possible. Thus $A=\{ t,t+v,...,t+vy\}$, but obviously $c=\frac{n}{t}\in A$, thus since $t$ is smallest divisor($>1$) of $n$, $c$ has to be largest divisor of $n$($<n$), since it must belong to $A$ we have that $A=\{t,t+v,...,t+vy=\frac{q^d}{t}\}$, but as $t|q\Longrightarrow t^d|q^d=n$, thus $t$ divides all elements in $A$( since $\frac{q^b}{t^{b-1}}\notin G)$, thus $t|v\Longrightarrow v=t^l\cdot r$, $t\nmid r\in \mathbb{N}$. Thus $A=\{ t,t(t^{l-1}r+1),...,t(yt^{l-1}r+1)=\frac{q^d}{t}\}$, but as $t^d|n$ we have that it($q^d$) must belong to $A$, thus $l=1$(since otherwise $t|t^{l-1}re+1$...), thus $A=\{ t,t(r+1),...,t(yr+1)=\frac{q^d}{t}\}$, but as $\forall j>1$ and $d>j$ we know that $t^j|q^d=n$, it follows that $t^j\in A$(since it's not power of $q$...)\begin{align*}\Longrightarrow t(rf+1)=t^j=t\cdot t^{j-1}&\stackrel{t^{j-1}\in A\text{ and this equality must follows, since t is smallest divisor of n}}{=}t\cdot t\cdot (r(f-1)+1)\\ &\Longrightarrow rf+1=t(r(f-1)+1)\\ &\stackrel{\gcd(rf+1,r(f-1)+1)=1}{\Longrightarrow}\text{impossible}\end{align*}, which is contradiction if $f>2$, thus $y\leq 2$, and this is contradiction with condition that both sets must have more than $2$ elements. $b.)$ $\underline{n\in A}$ Thus for some \begin{align*}k\in \mathbb{N}, \ n-k\in A& \Longrightarrow n-k|n\\ & \Longleftrightarrow n-k|k\\ & \Longrightarrow k\geq n-k\\ & \Longleftrightarrow 2k\geq n\\ & \Longleftrightarrow n-2k<1\\ & \Longrightarrow |A|\leq 2.\ \blacksquare \end{align*}Thus there are not such numbers EDITED: Mistake pointed out by TacH...

Hmmm , does $D_n$ also included the negative divisors ? Also <mihajlon> wrote: $\gcd (1+kx_1,1+kx_2)=\gcd(1+kx_1,k(x_2-x_1))=1\ . \ . \ . \ \bigstar$ isn't this is false ? , such as $1,4,7,10$ we have $(4,10) \neq 1 $

TacH wrote: Hmmm , does $D_n$ also included the negative divisors ? Also <mihajlon> wrote: $\gcd (1+kx_1,1+kx_2)=\gcd(1+kx_1,k(x_2-x_1))=1\ . \ . \ . \ \bigstar$ isn't this is false ? , such as $1,4,7,10$ we have $(4,10) \neq 1 $ You're completely right, sorry for that trivial mistake...

Let the elements of $A$ be $a_1<a_2<...<a_{k-1}<a_k$. The main idea is to bound $n$ by putting an upper bound on $a_2-a_1$ and thereby a very tight upper bound on $a_k-a_{k-1}$. First we eliminate the case where $n$ is a prime power. This is obvious since there is no A.P. of at least three terms among $1,p,p^2,...$ So let $p<q$ be the two smallest prime factors of $n$ Also, it's straightforward that $n\in G$, since if $n\in A$ the next largest term is at most $\frac{n}2$ and there can be no term after that. Now, among $1,p,q$, we cannot have two of them in $G$ (since if $1,p\in G$ then $n$ is a prime power). Immediately we get $a_2-a_1\le q-1$ Among $\frac{n}p,\frac{n}q$ at most one of them is in $G$, so $a_k-a_{k-1}\ge \frac{n}{q(q+1)}$. Combined we immediately get $n<q^3$. We could directly grind the remaining cases, but it's simpler to improve our estimates: If $1\in G$, then note that $p,q,\frac{n}p,\frac{n}q$ are all in $A$, so we get $n\le pq$, which has less than 6 positive factors. If $q\in G$, then $1,p,\frac{n}q$ are all in $A$, and we get $n<pq(q+1)$, so $n=p^2q, pq^2$ but now $A$ has at least 4 elements, so contradiction. Similar reasoning if $p\in G$

very nice problem

oty wrote: very nice problem

Hey guys please someone check my solution as my solution is a bit different. Let $A=\{a,a+d,\cdots ,a+(k-1)d\}$ and $G=\{b,br,\cdots, br^m\}$ If $n\in A$ $\implies n=a+(k-1)d$ $\implies a+(k-2)d|a+(k-1)d$ $\implies a+(k-2)d|d$ Thus for $k>2$ this is absurd and $k\geq 3$ as per the initial condition. We conclude that $n$ does not belong to $A$ $-(\bigstar)$ Now we have two cases coming up.

Suppose such partition exists for some $n$. Let $d$ be the common difference in $A$. Let $M=\max{A}$ CASE I: $1\in G$. Then let $G=\{1,q,...,q^n\}$ for some $q\in\mathbb N$ and $n\geq 2$. Now if $q$ has two distinct prime factors $p<r$. Then $p,r,p^{n}r^{n-1}\in A$. Hence $M\geq p^nr^{n-1}$, $d|p-r$. Now $M-d\in A$, while $$[M-d,M]\geq \frac{(M-d)M}{d}\geq q^n$$Hence $[M-d,M]\in D_n$ but it is not in $G$. As a result, it is in $A$. From $M=\max{A}$ we have $$M\geq[M-d,M]\geq\frac{(M-d)M}{d}$$Hence $M-d\leq d$ which implies $p^nr^{n-1}\leq 2(p-r)$, contradiction. Now if $n$ has a prime factor $p$ not divisble by $q$, then $pq^n\in A$, so similarly $[M-d,M]\in G$ and $M-d>d$, contradiction. Therefore $n$ must be a prime power, which is obviously impossible. CASE II: $1\in A$ Let $|A|=k$. If $k\geq 4$, then notice that $(kp+1)((k-1)p+1), ((k-1)p+1)((k-2)p+1)\in G$, so $$((k-2)p+1)|kp+1$$which is clearly impossible. If $k=3$, then $A=\{1,k+1,2k+1\}$. Therefore $(k+1)(2k+1)\in G$. If $p|k+1$ for some $1<p<k+1$ then $$p(2k+1),p,(k+1)(2k+1)\in G$$but they obviously can't form a geometric sequence. Hence $k+1$ is a prime, similarly $2k+1$ is a prime. Let $(k+1)(2k+1)x$ be another element in $G$, then $(2k+1)x$ and $(k+1)x$ is also an element, but obviously they can't form a geometric sequence.

No $n$ works. Claim: $|G|\le \max_{j=1}^k (e_j+1)$ Proof: Let $r>1$ be the common ratio of elements in $G$. Suppose $\nu_p(r)\ge 1$, which exists since $r>1$. If $m$ is the smallest element and $M$ is the largest, then $|G|=\frac{\nu_p(M)-\nu_p(m)}{\nu_p(r)}+1\le e_j+1$ where $e_j=\nu_p(n)$. Now we casework on $n$ and $A=D_n\backslash G$. Case 1: $n$ is divisible by one prime only. Let $n=p^r$. I claim there exists no arithmetic sequence of 3 terms in $D_n$. If there were, then say $p^a+p^b=2p^c$. This means $b>c$ but $p^b\ge p\cdot p^c\ge 2p^c$, contradiction. Case 2: $n$ is divisible by two primes, call $p,q$. Let $n=p^aq^b$ for simplicity. We know $(a+1)(b+1)=|D_n|\ge 3+3=6$ Subcase 1: $a,b\ge 2$. This means $|A|\ge \frac 23 |D_n|$. I claim $\max(p,q)$ is divisible by every element of $a$ Let $S$ be the set of numbers dividing $\max(p,q)$ in $D_n$. Then $|A\cap S|/|A| \ge 1+(|S|-|D_n|)/|A|\ge 1-\frac{\frac{b}{b+1}|D_n|-|D_n|}{|A|}=1-\frac{|D_n|}{(b+1)|A|}\ge 1-\frac{1}{(b+1)2/3}\ge \frac 12$ Also, $|A|\ge (a+1)b\ge 6$. Since $\max(p,q)\ge 3$ it follows that if the common difference of $A$ is not divisible by $\max(p,q)$ then $|A\cap S|/|A|\le \frac{|A|+q-1}{q}\le \frac{|A|+2}{3}<\frac{|A|}{2}$, absurd. Subcase 2: $a=1$. We can check $a=1, b=2$ or $b=3$ fails by hand. We casework on $r$, the common ratio of elements in $G$. Subsubcase 1: $\nu_p(r)\ne 0$. This means $|G|=2$, absurd. Subsubcase 2: $\nu_p(r)=0$. This means $A$ either contains all of $\{1,q,q^2,\cdots,q^b\}$ or $\{p, pq, \cdots, pq^b\}$. This means $|A|\ge b+1$ while at most 2 elements in $|A|$ are not multiples of $p$. Since $b\ge 4$, it follows that all elements of $A$ must be divisible by $q$, false. Case 3: $n$ is divisible by at least 3 primes. By our claim, $|G|\le \frac 14 |D_n|$ so $|A|\ge \frac 34 |D_n|$. Let $d$ be the common difference of $A$. Claim: If $p\ge 5$ is a prime and $p\mid n$ then $p\mid d$. Furthermore, all terms in $A$ are divisible by $p$. Proof: Let $S=\{t \text{ such that } p\mid t\mid n\}$. We know $|S|\ge \frac 12 |D_n|$, so it follows $|A\cap S|=|A|+|S|-|A\cup S|\ge |A|-|D_n|+|S|\ge |A|-\frac 12 |D_n| \ge |A|(1-\frac 12 \cdot \frac 43)=\frac 13 |A|$ Note $|A|\ge (e_1+1) ((e_2+1)(e_3+1)-1 )\ge 2\cdot 3=6$ Observe at most $\frac{|A|+p-1}{p}$ terms are divisible by $p$ if $p\nmid d$. Therefore, $\frac{|A|+p-1}{p}\ge \frac{|A|+4}{5} \ge \frac 13 |A|$, so $|A|\le 6$. It readily follows that $p=5$ and $|A|=6$. This means $e_1=e_2=e_3=1, p_1=2, p_2=3, p_3=5$ so $n=30$. We can check by hand that it doesn't work. Therefore, all elements of $A$ are divisible by this prime so all elements not divisible by this prime are in $G$. However, the set of elements not divisible by this prime is $D_{\frac{n}{p^{\nu_p(n)}}}$ and $\frac{n}{p^{\nu_p(n)}}$ divisible by at least 2 primes, call $p_1,p_2$. Note $1\in G$ so $r\in \mathbb{N}$, and it's not possible to have $p_1,p_2$ both in $G$, contradiction.

we claim that no $n$ is possible. Let $A=\{a,a+d,\cdots ,a+kd\}$ and $G=\{b,br,\cdots, br^m\}$. First, n isn't a prime power and $n\in G$ because if $n \in A$ so we have $d$ $\ge$ $\frac n2$ so we have $card(A) < 3$ contradiction. $\implies$ $n=br^m$. consider two cases: 1) $1\in A$: $A=\{1,1+d,\cdots ,1+kd\}$, we have $(1+(k-1)d)(1+kd)|n$ because $gcd(1+(k-1)d,1+kd)=1$ $\implies$ $1+id < \sqrt{n}$ $for: i<k$$\implies$ $\frac{n}{1+id} \in G$ $\implies 1+d|1+2d$ contradiction. 2)$1\in G$: $G=\{1,r,\cdots, r^m\}$ Let $p < q$ be the smallest prime factors of $n$ we have $a=p$ and $q = p+d$ because if $p^2=p+d$ then $ p|d \implies p|q$ and this contradiction. $\implies q= p+d, \frac{n}{p}=p+kd, \frac{n}{q}=p+(k-1)d$ but $p|\frac{n}{p}=p+kd$ and $p|\frac{n}{q}=p+(k-1)d$ $\implies p|1$ contradiction.