Взаимно простые числа
Определение. Натуральные числа а и в называют взаимно простыми, если их наибольший общий делитель равен 1.
Например, НОД (15, 7) = 1 
числа 15 и 7 взаимно простые.
Свойства простых и взаимно простых чисел
1. Если натуральное число больше 1, то оно имеет хотя бы один простой делитель.
2. Наименьший простой делитель р составного числа а не превосходит 
.
Доказательство. а 
р (по условию) а = рq, если q – простое, то р 
q (по условию). Умножим обе части неравенства на р, получим: р2 qр, но qр = а р2 а р . Это значит, что если число а не делится ни на одно простое число не превосходящего , то у него нет простых множителей, меньших этого числа, то есть это число простое.
Например, чтобы установить число 137 простое или составное, нужно найти 
.
11 < < 12. если число 137 не делится на простые числа, меньшие 12, то число 137 – простое. Множество простых чисел, меньших 12 есть числа 2, 3, 5, 7, 11. Число 137 не делится ни на одно из простых чисел, меньших 12. Следовательно, число 137 – простое.
3. Если простое число р делится на некоторое натуральное число n, отличное от 1, то оно совпадает с n.
Дано: n, p 
N, p – простое, р n, n 
1. Доказать: р = n.
Доказательство. Если бы р n, то число р имело бы три делителя: 1 (так как всякое число делится на 1), число n (по условию р n) и р (по свойству симметричности отношения делимости р р) и, следовательно, не было бы простым, что противоречит условию. Таким образом, р = n.
4. Если произведение простых чисел делится на простое число, то, по крайней мере, один из сомножителей равен делителю.
Дано: а, в N 
а – простое, в – простое, р – простое (ав) р. Доказать: а = р 
в = р.
Доказательство. Если (ав) р а р в р.
Пусть а р, то в частном будет более двух различных делителей.
Следовательно, а: р = 1 а = р. Аналогично, в: р = 1 в = р.
5. Если произведение чисел ав делится на с и числа а и с взаимно простые, то в делится на с.
Дано: а, в N ав с, НОД (а, в) = 1. Доказать, что в с.
Доказательство. По признаку делимости произведения ав а ав с (по условию) ав = ОК(а, с) делится на НОК (а, с), равное ас.
Имеем, ав ас ав = асq (по сократимости умножения) в = сq в с.
Признак делимости на составное число вытекает из следующего свойства: Если натуральное число а делится на каждое из взаимно простых чисел в и с, то оно делится на их произведение вс.
Дано: а N, d (в, с) = 1, а в, а с. Доказать, что а (вс).
Доказательство. Из того, что а в а с а = К(в, с), поэтому а делится на К(в, с). Но числа в и с взаимно простые К(в, с) = вс (так как НОК двух взаимно простых чисел равен произведению этих чисел. Итак, а вс.
Признак делимости на составное число
Для того, чтобы натуральное число х делилось на составное число n = вс, где (вс) = 1, необходимо и достаточно, чтобы оно делилось на в и на с.
Действительно, если х n = (вс), то х в х с, так как в и с делители числа (вс).
Обратно, пусть х в х с. Так как (вс) = 1, то по доказанному выше число х (вс).
Признак делимости на 6
Для того, чтобы натуральное число х делилось на 6, необходимо и достаточно, чтобы оно делилось на 2 и на 3.
Признак делимости на 12
Для того, чтобы натуральное число х делилось на 12, необходимо и достаточно, чтобы оно делилось на 3 и на 4.
Признак делимости на 15
Для того, чтобы число х делилось на 15, необходимо и достаточно, чтобы оно делилось на 3 и на 5.
Основная теорема арифметики
Условимся считать два разложения на простые множители одинаковыми, если они отличаются друг от друга только порядком следования множителей.