Päevaülesanne

Juhuslik

Harjutuskomplekt

Balti Tee 1990 · Ülesanne 14

Arvuteooria

Do there exist 1990 relatively prime numbers such that all possible sums of two or more of these numbers are composite numbers?

Muuda valikut

Kui oled valmis

Ülevaatematerjal muutub kättesaadavaks järgmise päevaülesannete komplektiga.

Ülevaade

Teemad

SÜT ja VÜK · Jaguvus ja tegurdamine

Lahendused

Lahendus

Solution:

Such numbers do exist. Let M=1990!M = 1990! and consider the sequence of numbers 1+M,1+2M,1+3M,…1 + M, 1 + 2M, 1 + 3M, \ldots For any natural number 2≤k≤19902 \leq k \leq 1990, any sum of exactly kk of these numbers (not necessarily different) is divisible by kk, and hence is a composite number. It remains to show that we can choose 19901990 numbers a1,…,a1990a_{1}, \ldots, a_{1990} from this sequence which are relatively prime. Indeed, let a1=1+Ma_{1} = 1 + M, a2=1+2Ma_{2} = 1 + 2M and for a1,…,ana_{1}, \ldots, a_{n} already chosen take an+1=1+a1⋯an⋅Ma_{n+1} = 1 + a_{1} \cdots a_{n} \cdot M.