Разделы 
Дополнительно
Задача по математике - 1685
2019-01-20 
Докажите, что из произвольного множества трехзначных чисел, включающего не менее четырех чисел, взаимно простых в совокупности, можно выбрать четыре числа, также взаимно простых в совокупности.
Решение:
Лемма. Из любого множества, состоящего не менее, чем из пяти трехзначных чисел, взаимно простых в совокупности, можно удалить одно число так, что оставшиеся также будут взаимно просты в совокупности.
Доказательство. Обозначим через $M = {a_1, \cdots, a_k}$ множество исходных чисел, через $M_i$ - множество $M$ без $a_i$, а через $A_i$ - наибольший общий делитель чисел из $M_i, i = 1, \cdots, к$. Наибольший общий делитель любых чисел $A_i$ и $A_j, i = j$, равен наибольшему общему делителю всех чисел $a_1, \cdots, a_k$, т. е. 1, следовательно $A_1, \cdots, A_k$ попарно взаимно просты. Если все они не равны 1, обозначим через $p_i$ наибольший простой делитель $A_i$. В силу попарной взаимной простоты чисел $A_i$, числа $p_i$ попарно различны, и можно считать, что $p_1 < \cdots < p_k$ и $A_1 \geq 2, A_2 \geq 3, A_3 \geq 5, A_4 \geq 7, A_5 \geq 11$.
Так как $a_1 \in M_2, M_3, M_4, M_5$, то $a_1$ делится на $A_2A_3A_4A_5 \geq 3 \cdot 5 \cdot 7 \cdot 11 = 3003$. Противоречие с тем, что $a_1$ трехзначно. Следовательно, одно из чисел $A_i$ равно 1, и числа в соответствующем множестве $M_i$ взаимно просты в совокупности.
Применяя лемму, из исходного множества можно последовательно удалить все числа, кроме четырех, взаимно простых в совокупности.
Докажите, что из произвольного множества трехзначных чисел, включающего не менее четырех чисел, взаимно простых в совокупности, можно выбрать четыре числа, также взаимно простых в совокупности.
Решение:
Лемма. Из любого множества, состоящего не менее, чем из пяти трехзначных чисел, взаимно простых в совокупности, можно удалить одно число так, что оставшиеся также будут взаимно просты в совокупности.
Доказательство. Обозначим через $M = {a_1, \cdots, a_k}$ множество исходных чисел, через $M_i$ - множество $M$ без $a_i$, а через $A_i$ - наибольший общий делитель чисел из $M_i, i = 1, \cdots, к$. Наибольший общий делитель любых чисел $A_i$ и $A_j, i = j$, равен наибольшему общему делителю всех чисел $a_1, \cdots, a_k$, т. е. 1, следовательно $A_1, \cdots, A_k$ попарно взаимно просты. Если все они не равны 1, обозначим через $p_i$ наибольший простой делитель $A_i$. В силу попарной взаимной простоты чисел $A_i$, числа $p_i$ попарно различны, и можно считать, что $p_1 < \cdots < p_k$ и $A_1 \geq 2, A_2 \geq 3, A_3 \geq 5, A_4 \geq 7, A_5 \geq 11$.
Так как $a_1 \in M_2, M_3, M_4, M_5$, то $a_1$ делится на $A_2A_3A_4A_5 \geq 3 \cdot 5 \cdot 7 \cdot 11 = 3003$. Противоречие с тем, что $a_1$ трехзначно. Следовательно, одно из чисел $A_i$ равно 1, и числа в соответствующем множестве $M_i$ взаимно просты в совокупности.
Применяя лемму, из исходного множества можно последовательно удалить все числа, кроме четырех, взаимно простых в совокупности.
