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
IndoMathXdZ
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$.
62861
31.05.2019 18:04
(a) Let $P = \{3, 5, 7, 11, 13, 17, 19, 23, 29, 31\}$. Since $2019 > 2^{10}$, there are two among the given numbers, say $a$ and $b$, such that $a \pmod{p}$ and $b \pmod{p}$ have the same parity for all $p \in P$. It easily follows that $p \nmid a+b$ for all $p \in P$.
(b) No: consider $2^{11} = 2048$ numbers selected as follows: let $Q = \{3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37\}$, and for any choice $\varepsilon_q \in \{\pm 1\}$ for all $q \in Q$, select an $a$ satisfying $a \equiv \varepsilon_q \pmod{q}$ for all eleven $q$. Then all pairwise sums of these 2048 numbers have prime divisors at most 37.