5. Взаимно простые числа.

Два целых числа называются взаимно простыми, если их н.о.д. равен 1.

Ясно, что если d есть наибольший общий делитель целых чисел а и b, то и суть целые взаимно простые числа. Действительно, то, что эти числа целые, следует из того, что d — общий делитель для а и b. Если — наибольший общий делитель и а и b делятся на , откуда следует, что иначе не был бы наибольшим общим делителем для а и b.

Предложение 5. Для того чтобы целые числа а и b были взаимно простыми, необходимо и достаточно существование целых чисел таких, что

Предложение 5 можно сформулировать и в других терминах: для того чтобы неопределенное уравнение имело решение в целых числах, необходимо и достаточно, чтобы а и b были взаимно просты.

Доказательство. Пусть а и b взаимно просты. Тогда их н.о.д., равный 1, имеет линейное представление: . Пусть теперь существуют такие, что . Тогда н.о.д. (а, b) делит , а следовательно, и их сумму, равную 1. Но 1 не имеет натуральных делителей, кроме 1, так что равен 1. Предложение доказано полностью.

Предложение 6. Если целые числа взаимно просты с целым числом b, то их произведение тоже взаимно просто с b.

Доказательство. Существуют целые такие, что в силу предложения 5. Перемножая эти равенства, получим после очевидных преобразований

откуда, в силу того же предложения, числа и b взаимно просты, ибо целые числа.

Предложение 7. Если целые числа все взаимно просты с b, то произведение тоже взаимно просто с b.

Доказательство. Применим метод математической индукции. При предложение верно в силу предложения 6. Допустим, что оно верно для произведения множителей, и в этом предположении докажем его для k множителей. Запишем как . Первый множитель взаимно прост с b по условию. Второй взаимно прост с b в силу индуктивного предположения. Следовательно, мы можем применить предложение 6 и заключить, что взаимно просто с b, что и требовалось доказать.

Предложение 8. Если целые числа таковы, что каждое число взаимно просто с каждым числом , то их произведения взаимно просты.

Доказательство. Применив m раз предложение 7 к числам получим, что числа взаимно просты с числом Применяя еще раз предложение 7, получим, что взаимно просто с что и требовалось доказать.

Предложение 9. Если целые числа а и b взаимно просты, то при натуральных k и числа тоже взаимно просты.

Для доказательства достаточно в предложении 8 положить .

Предложение 10. Если произведение двух целых чисел а и b делится на целое число с и первый множитель а взаимно прост с с, то b делится на с.

Доказательство. По условию а и с взаимно просты, так что существуют целые такие, что . Умножив это равенство на b, получим . Первое слагаемое левой части делится на с по условию, второе делится на с тривиальным образом. Следовательно, и их сумма b делится на с, что и требовалось доказать.

Предложение 11. Если целое число а делится на целые взаимно простые числа , то а делится и на их произведение.

Доказательство. Пусть при целом с. По условию а делится на взаимно просто с . Следовательно, согласно предложению 8 число с делится на при целом . Поэтому , что и требовалось доказать.

Установленные предложения очень просты и кажутся почти тривиальными. Тем не менее из них можно вывести некоторые не совсем тривиальные следствия.

Выведем, например, что степень с натуральным показателем дробного рационального положительного числа не может быть целым числом.

Действительно, пусть — дробное рациональное число с целым положительным знаменателем b и с целым числителем а. Без нарушения общности можно считать, что числитель и знаменатель взаимно просты, этого можно добиться за счет сокращения на наибольший общий делитель. Пусть это выполнено. Ясно, что иначе было бы целым. Пусть — натуральное число. Тогда . В силу предложения взаимно просты. Поэтому не может делиться на так что не является целым числом.

Из доказанного следует далее, что если целое положительное число с не является степенью целого числа (при натуральном ), то оно не является степенью дробного рационального числа. Поэтому целое число, ибо иррациональное. Так, числа (пропускаются целые все иррациональны, также иррациональны и числа (пропускаются целые ) и т. д.