# Understand the problem

them which are relatively prime. Show that one can find four integers a, b, c, d among them such that

gcd(a, b) = gcd(b, c) = gcd(c, d) = gcd(d, a) = 1.

##### Source of the problem

##### Topic

##### Difficulty Level

8/10

##### Suggested Book

# Start with hints

**The clue: Consider the numbers as points in a graph, and some edges between the points based on their gcd.**Let us consider a graph G with 91 vertices (91 distinct numbers) and connect each pair of these vertices. which corresponds to co-prime pairs implies at least 456 edges i.e. e \( \geq\) 456. Here e = number of edges. Now getting four number a,b, c, d such that gcd (a, b) = gcd (b, c) = gcd(c,d) = gcd (d,a) = 1 implies existence at a cycle of length 4.

So, the sum of all such vertex pairs corresponding to a vertex over all the vertex set \( \leq\) the total number of vertex pairs. \( \sum_{i=1}^{91} ({d_i}\choose{2}) \leq {{91}\choose{2}} \rightarrow \) \( \sum_{i=1}^{91} ({d_i}^2 – d_i)\leq 91.90 \rightarrow \) \( \sum_{i=1}^{91} {d_i}^2 \leq 2e + {{91}\choose{2}}\) -> (1) as \( \sum_{i=1}^{91} d_i = 2e \).

We will try to find a lower bound on \( \sum_{i=1}^{91} {d_i}^2 \) w.r.t e.

By RMS – AM inequality, \( \sum_{i=1}^{91} {d_i}^2 \geq \frac{( \sum_{i=1}^{91} {d_i})^2 }{91} = \frac{4e^2}{91} \) -> (2) Using (1) and (2), we get \( \frac{2e^2}{91} – e \leq 91.45 \) From here, by solving we get \( e \leq 91×5 =455\). This gives the contradiction.

# Watch video

# Connected Program at Cheenta

#### Math Olympiad Program

Math Olympiad is the greatest and most challenging academic contest for school students. Brilliant school students from over 100 countries participate in it every year. Cheenta works with small groups of gifted students through an intense training program. It is a deeply personalized journey toward intellectual prowess and technical sophistication.