Простые множители. Теория чисел

Простые множители. Теория чисел

-Дай пожалуйста простой карандаш
- На, возьми
- Эй, но ты мне дал красный карандаш!
- А что, красный карандаш для тебя уже сложный?
Положительное целое число
Разложение числа на простые множители
Простые множители заданного числа

В данном материале мы рассмотрим одну из самых старых математических задач - разложение определенного целого числа на более простые сомножители.

Решение этой задачи неразывно связано с понятием простые числа

Простое число - это число котрое может быть разделено нацело только или единицей или самим собой.

Например все числа 2, 3, 5, 7, 11,13, 17, 19, 23 и так далее являются простыми.

Число  111 например составное ( не простое) так как его можно получить умножив 37 на 3, а вот 113 - число простое, так как его кроме как на 113 разделить невозможно.

Алгоритмы  расчета простых чисел достаточно многообразны и мы рассматривать их не будем. Кому любыпытно, а это на самом деле красивая и не до конца иследованная область, тот сможет найти соответствующую литературу.

Мы же расскажем лишь о некоторых свойствах простых чисел:

1. Самое первое свойство открыл еще Евклид и оно гласит что простых чисел бесчисленное множество. И это доказывается элементарно: взяв все(!) простые числа от 2-х и до какого то максмально известного Ф, перемножим их и прибавим единицу. Окажется, что полученное число не делится  ни на одно из простых чисел,а следовательно само является простым и больше значения Ф.

Это легко увидеть на примерах 2*3+1=7 - простое, 2*3*5+1=31 простое, 2*3*5*7=211 простое  ну и так далее

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

в пределах 3,  и 2*3  есть простое число 5, в пределах 10 и 10*2 есть простые числа 11,13,17,19 и далее

3. Все простые числа (выше 5-ти) могут быть выражены в виде формулы k6\pm1

31=6*5+1;47=6*8-1,2111231(простое число)=351872*6-1

Необходимость этого условия не обеспечивает её достаточность, то есть не каждое число удовлетворяющее указанной выше формуле является простым числом

Например 49=8*6+1 формуле удовлетворяет, но простым числом не является 49=7*7

4. Любое простое число P выше пяти и возведенное в квадрат минус единица, без остатка делятся на 24

(p^2-1)mod24=0

5. Простое число(выше 5-ти) произвольной длины может оканчиваться только на числа 1,3,7 или 9.  

Это легко доказывается, так как если бы оканчивалась на четную цифру то это число делилось бы на 2, если бы оканчивалось бы на 5 то число делилось бы без остатка на пять.

Есть еще множество свойств , но все они уже не так просты как вышеназванные.

Примечательны усилия ученых найти универсальную формулу  для расчета произвольного простого числа

Великий Эйлер вывел x^2+x+41, где при х от 0 до 39 получается простое число.

Еще один многочлен, дающих простые числа   x^2-79x+1601=p, при х от нуля до 79

Правда, в последней формуле эти числа могут повторятся.

Интересна идея найти  арифметическую прогрессию которая содержала бы  наибольшую цепочку простых чисел.

например прогрессия с разностью  6 : 5 11 17 23 29

Одна из самых больших цепочек  состоит из 12 последовательных элементов и имеет вид

p=23143+30030x

где х принимает значения от нуля до 11 включительно.

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

Бот позволяет высчитывать простые сомножители числа, имеющих длину не более 19 символов.

Синтаксис для пользователей XMPP клиентов

sim число

где число- положительное целое число, длиной менее 19 символов.

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

Удачных расчетов!

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