Соответствия, сравнения, количества

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

Доказательство. Обозначим через множество исходных чисел, через — множество без а через — наибольший общий делитель чисел из Наибольший общий делитель любых чисел и равен наибольшему общему делителю всех чисел то есть следовательно, попарно взаимно просты.

Если все они не равны обозначим через наибольший простой делитель В силу попарной взаимной простоты чисел числа попарно различны, и можно считать, что Тогда Так как то делится на что противоречит трёхзначности

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