Question

Show that in any set of \({\bf{n}}{\rm{ }} + {\rm{ }}{\bf{1}}\) positive integers not exceeding \({\bf{2n}}\) there must be two that are relatively prime.

Short answer

Use a by proof contradiction

Step-by-step solution

Definition of Integers

Integers are made up of both positive and negative numbers. Integers, like whole numbers, do not include the fractional portion. Integers, on the other hand, are numbers that can be positive, negative, or zero but not a fraction.

Explanation

So, we have a set of\({\rm{n}} + 1\)numbers. Let’s label them, in increasing order:\({a_1},{a_2}, \ldots {a_{n + 1}}\)suppose all of them are non consecutive, i.e. any two numbers have at least a gap of two. I.e. if\({a_i}\)and\(a\_\left\{ {i + 1} \right\}\)are two numbers, then\(\left| {{a_i} - {a_{i + 1}}} \right| \ge 2\).

But this means that the gap between the smallest and the largest number is \({a_{n + 1}} - {a_1} \ge 2n\) but this is not possible since the minimum number in the sequence is one and the maximum number is\(2{\rm{n}}\). Contradiction.

Solution

Thus, we conclude that there is at least one pair of consecutive integers in the sequence. Let these be\(a\)and\(a + 1\). Now, we claim that these two numbers are relatively prime. Suppose not. Then there is a number\(d > 1\)such that\(d\mid a\)and\(d\mid a + 1\). This implies, by the basic properties of divisibility that\(d|(a + 1) - a \Rightarrow d|1\).

Now, d being a factor of one, is naturally, less than or equal to one. Contradiction.

Hence proved.

Therefore, Use a proof-by-contradiction strategy.