Основная теорема арифметики




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

Определение. Натуральные числа а и в называют взаимно простыми, если их наибольший общий делитель равен 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.

Основная теорема арифметики

Условимся считать два разложения на простые множители одинаковыми, если они отличаются друг от друга только порядком следования множителей.



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-08-26 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: