Maths Olympiad Prep

Library / /9 of 19

Number theory Difficulty 6.3 National olympiad Find the answer

Find the smallest positive integer nn such that the 7373 fractions 19n+21,20n+22,21n+23,...,91n+93\frac{19}{n+21}, \frac{20}{n+22},\frac{21}{n+23},...,\frac{91}{n+93} are all irreducible.

A number or a short expression. Spacing and $ signs are ignored.

Solution

To solve this problem, we need to find the smallest positive integer n n such that all 73 fractions of the form kn+k+20\frac{k}{n+k+20} for k=19,20,,91 k = 19, 20, \ldots, 91 are irreducible. A fraction ab\frac{a}{b} is irreducible if and only if gcd(a,b)=1\gcd(a, b) = 1.

For the fractions kn+k+20\frac{k}{n+k+20} to be irreducible, we need:

gcd(k,n+k+20)=1 \gcd(k, n+k+20) = 1

Simplifying the statement gcd(k,n+k+20)\gcd(k, n+k+20), we observe that:

gcd(k,n+k+20)=gcd(k,n+20) \gcd(k, n+k+20) = \gcd(k, n+20)

Using the Euclidean Algorithm, we understand this stems from the fact that if gcd(a,b)=gcd(a,bqa)\gcd(a, b) = \gcd(a, b - qa) for any integer q q.

Given the fraction range, each k k increments by 1 starting from 19. Therefore, we require:

gcd(k,n+20)=1fork=19,20,,91 \gcd(k, n+20) = 1 \quad \text{for} \quad k = 19, 20, \ldots, 91

Notice that this results in 73 simultaneous conditions, corresponding to each value of k k .

The common task here is discerning n n such that n+20 n+20 is coprime to each k{19,20,,91} k \in \{19, 20, \ldots, 91\}.

We observe that for each k k , the main requirement is that n+20 n + 20 needs to avoid any prime factors present within the sequence {19,20,,91}\{19, 20, \ldots, 91\}.

The numbers k=19,20,21,,91 k = 19, 20, 21, \ldots, 91 encompass several prime numbers such as 19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89. Each n+20 n + 20 must ensure it is not divisible by any of these prime numbers. The simplest way is to let n+20 n + 20 exceed the largest of these numbers, for clear coprime status.

The largest prime in this list is 89. Thus, n+20 n + 20 should be at least no less than 89, giving room for searching the smallest n n .

Therefore, the minimum feasible n+20 n + 20 which satisfies all coprime conditions can be tested progressively upwards from 90, knowing large enough clear routes.

Finally, solving for the smallest feasible n n :

n+20=115n=95 n + 20 = 115 \quad \Rightarrow \quad n = 95 .

Thus, the smallest positive integer n n that meets the condition of being coprime across the entire defined range is:

95 \boxed{95}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.