IMO 1991

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$ .

Suppose $G\,$ is a connected graph with $k\,$ edges. Prove that it is possible to label the edges $1,2,\ldots ,k\,$ in such a way that at each vertex which belongs to two or more edges, the greatest common divisor of the integers labeling those edges is equal to 1.Note: Graph-Definition. A graph consists of a set of points, called vertices, together with a set of edges joining certain pairs of distinct vertices. Each pair of vertices $u,v\,$ belongs to at most one edge. The graph $G$ is connected if for each pair of distinct vertices $x,y\,$ there is some sequence of vertices $x = v_{0},v_{1},v_{2},\cdots ,v_{m} = y\,$ such that each pair $v_{i},v_{i + 1}\;(0\leq i < m)\,$ is joined by an edge of $G$ .