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

Рассмотрим свойства взаимно простых чисел.

ПРЕДЛОЖЕНИЕ 2.9. Целые числа взаимно простые тогда и только тогда, когда единица представима в виде целочисленной линейной комбинации этих чисел.

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

Обратно: если единица представима в виде целочисленной линейной комбинации чисел то в силу предложения 2.6 единица есть наибольший общий делитель этих чисел. Поэтому числа взаимно простые.

ПРЕДЛОЖЕНИЕ 2.10. Целые числа взаимно простые тогда и только тогда, когда они не имеют общего простого делителя.

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

ТЕОРЕМА 2.11. Если целое число делит произведение двух целых чисел и взаимно простое с одним из сомножителей, то оно делит другой сомножитель.

Доказательство. Пусть числа а и b взаимно простые и а делит . Докажем, что а делит c. Так как числа а и b взаимно простые, то существуют такие целые числа что

Умножив обе части равенства на с, получим . Кроме того, а делит Поэтому а делит , т. е. а делит с.

ПРЕДЛОЖЕНИЕ 2.12. Общий делитель d целых чисел не равных одновременно нулю, тогда и только тогда является их наибольшим общим делителем, когда числа взаимно простые.

Доказательство. Так как, по условию, не все числа равны нулю, то . Если d есть наибольший общий делитель чисел , то согласно теореме 2.5 его можно линейно выразить через

где — целые числа. Разделив обе части равенства на d, получим

Отсюда согласно предложению 2.9 следует, что числа взаимно простые.

Обратно: если числа взаимно простые, то согласно предложению 2.9 существуют такие целые числа что выполняется равенство (2). Умножив обе части этого равенства на d, получим равенство (1). Так как общий делитель d чисел представим в виде линейной комбинации этих чисел, то согласно предложению 2.6 число d есть наибольший делитель чисел