Олимпиадная задача по теории чисел: выбор взаимно простых трёхзначных чисел, 8–10 класс

  Лемма. Из любого множества, состоящего не менее чем из пяти трёхзначных чисел, взаимно простых в совокупности, можно удалить одно число так, что оставшиеся также будут взаимно просты в совокупности.

  Доказательство. Обозначим через  M = {a₁, ..., a_k}  множество исходных чисел, через M_i – множество M без a_i, а через A_i – наибольший общий делитель чисел из M_i. Наибольший общий делитель любых чисел A_i и A_j,  i ≠ j,  равен наибольшему общему делителю всех чисел a₁, ..., a_k, то есть 1, следовательно, A₁, ..., A_k попарно взаимно просты.

  Если все они не равны 1, обозначим через p_i наибольший простой делитель A_i. В силу попарной взаимной простоты чисел A_i, числа p_i попарно различны, и можно считать, что  p₁ < ... < p_k.  Тогда A₁ ≥ 2,  A₂ ≥ 3,  A₃ ≥ 5,  A₄ ≥ 7,  A₅ ≥ 11.  Так как  a₁ ∈ M₂ ∩ M₃ ∩ M₄ ∩ M₅,  то a₁ делится на

A₂A₃A₄A₅ ≥ 3·5·7·11 = 3003,  что противоречит трёхзначности a₁.

  Следовательно, одно из чисел A_i равно 1, и числа в соответствующем множестве M_i взаимно просты в совокупности.

  Применяя лемму, из исходного множества можно последовательно удалить все числа, кроме четырёх, взаимно простых в совокупности.

Ответ задачи отсутствует