пользователей: 21231
предметов: 10456
вопросов: 177504
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ


Теорема о наименьшем простом делителе составного числа

Теорема

Наименьший простой делитель составного числа а не превосходит √а.

Доказательство:

Пусть p – наименьший простой делитель числа а.Обозначим: d – дополнительным к p делитель числа а, т.е.a= p*d.

Докажем, что pd, если d – простое число, то pd, поскольку p – наименьший простой делитель числа а. Если же d – составное число, то у него в свою очередь, есть простой делитель. Обозначим его p1. Это число p1, будучи делителем числа d, является также делителем числа а по транзитивности отношения делимости. Значит,pp1, т.к. p – наименьший простой делитель а. В свою очередь, p1d, т.к. d делится на p1. Итак, pd и в случае составного d, поэтому p≤d в любом случае. Посколькуpd, то умножив обе части этого неравенства на p, и воспользовавшись монотонностью умножения, получаем, что

P2p*d.

Но d*p=a, значит, p2a, т.е. p≤√a, а это и требовалось доказать.

На практике чтобы узнать является ли число простым, достаточно проверять на делимость не все простые числа, меньшие этого числа, а все простые числа, меньшие или равные кв.корню этого числа.


26.06.2016; 14:21
хиты: 27
рейтинг:0
Точные науки
математика
модальная логика
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2016. All Rights Reserved. помощь