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

Определение.

Взаимно-простые числа — это натуральные числа, наибольший общий делитель (НОД) которых равен единице.

То есть, если НОД (a; b)=1, то числа a и b — взаимно-простые.

Примеры.

1) 4 и 21.

Делители числа 4: 1; 2; 4.

Делители числа 21: 1; 3; 7; 21.

Их единственный, а значит, и наибольший, общий делитель равен 1:

НОД (4; 21) = 1. Значит, 4 и 21 — взаимно-простые числа.

2) 6 и 35.

Делители 6: 1; 2; 3; 6.

Делители 35: 1; 5; 7; 35.

НОД (6; 35) = 1. Следовательно, числа 6 и 35 являются взаимно-простыми.

3) 27 и 33.

Делители 27: 1; 3; 9; 27.

Делители 33: 1; 3; 11; 33.

НОД (27; 33) = 3. Так как НОД (27; 33) ≠ 1, то 27 и 33 не являются взаимно-простыми числами.

 

Можно ли по внешнему виду определить, являются ли числа взаимно-простыми или нет? В некоторых случаях, можно.

Например, если оба числа чётные, то у них есть общий делитель 2, следовательно, два чётных числа не могут быть взаимно-простыми.

Если запись одного числа оканчивается на 5, а другого — на 5 или на 0, то оба числа делятся на 5, а значит, их НОД не единица, и эти числа не взаимно-простые.

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

В остальных случаях наибольший общий делитель составных чисел находят, разложив эти числа на простые множители, используя признаки делимости. Если при разложении оказывается, что единственный общий делитель равен 1, то эти числа являются взаимно-простыми.