a) Given $2019$ different integers wich have no odd prime divisor less than $37$, prove there exists two of these numbers such that their sum has no odd prime divisor less than $37$. b)Does the result hold if we change $37$ to $38$ ?
Problem
Source: 2019 Serbia TST Day 1 P1
Tags: number theory
31.05.2019 18:03
a) Notice that there are only 10 odd primes less than 37 : $\{3, 5, 7, 11, 13, 17, 19, 23, 29, 31 \}$. Notice that $2^{10} = 1024 < 2019$. Thus, there exists residues $a$ and $b$ modulo $p$ such that $p \nmid a + b$ dor every odd prime $p < 37$. b) No. Consider the following construction: Each number has residue either 1 or -1 modulo $3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37$. Assign each of the 2019 integers with vector: $(v_1, v_2, v_3, \dots, v_{11})$, where $v_i \in \{-1,1\}$. Construct 2019 vectors with distinct possible of arrangement $(v_1, v_2, \dots, v_{11})$. This is possible as the total number of distinct possible vector is $2^{11} = 2048 > 2019$. Note : Each $v_i$ represents the number being $v_i$ modulo $p_i$.
31.05.2019 18:04