Условия про НОД и НОК

Пусть — элементарные симметрические многочлены и Воспользуемся формулой Ньютона

Докажем, что Предположим, что существуют такие взаимно простые в совокупности , что отличен от Докажем, что тогда имеют общий делитель, больший 1. В самом деле, из формул Ньютона следует, что при разложении через моном, не содержащий и с точностью до знака имеет вид Поэтому если делит и делит то делит

При отличном от у чисел есть общий делитель, больший 1. Пусть — простой множитель, входящий в этот делитель. Тогда делит откуда (без ограничения общности) делит a. Но тогда делит и делит т.е. (без ограничения общности) делит Наконец, из того, что делит получаем, что делит Значит, но по условию — противоречие.

Итак, Набор реализует набор — набор — Для возьмем простое число и положим Тогда и не делит откуда