Существуют ли формулы проверки числа на простоту?

[Decorator]

Здравствуйте! Дорогие форумчане, нужна ваша подсказка - существуют ли формулы проверки числа на простоту?
Мне кажется я нашел формулу, с помощью которой можно проверить числа на простоту. Проверил для всех простых в диапазоне от 1 до 700000. Меня глючит или такое возможно?

[Gordmit]

Формулы-то может и есть, но другой вопрос в том, насколько они полезны.
Самый глупый и тривиальный пример такой формулы:

$\varphi(x)=x-1$, где $\varphi(x)$ - функция Эйлера.

Подставляем $x$; если выполняется равенство - значит $x$ простое, иначе составное. Но только вычислять-то функцию Эйлера от заданного числа придется производя факторизацию числа $x$, так что эта формула по сути ничего нового не даёт.

Напишите Вашу формулу, здешние эксперты посмотрят и оценят, на что способна Ваша формула

[Someone]

http://primes.utm.edu/prove/ - обзор методов проверки простоты числа.

[Decorator]

Выложил на страничку формулы проверки чисел на простоту. Можете заглянуть и проверить

http://primality-proving.narod.ru

[Руст]

Я не понял вашу формулу. Напишите здесь покороче, учитывая, что $F_n=\frac{(1+\sqrt 5 )^n-(1-\sqrt 5)^n}{\sqrt 5}$ числа Фибоначчи. Поэтому не надо делать формулу многоэтажным, заменив числами Фибоначчи.

[Decorator]

А что непонятного? Вместо дроби поставить f(n)? Или оператор MOD не понятен? Просто попробуйте подставить в формулу числа и удостоверитесь в моей правоте...

[Руст]

Decorator писал(а):

А что непонятного? Вместо дроби поставить f(n)? Или оператор MOD не понятен? Просто попробуйте подставить в формулу числа и удостоверитесь в моей правоте...

Перепишу ваши формулы:
(1) n, оканчивающийся на 1 или 9 прост, если $1=F_n-(MOD(\frac{F_n}{n}))*n$
(2) n, окончивающийся на 3 или 7 прост, если $n-1=F_n-(MOD(\frac{F_n}{n}))*n.$
Мне не понятны операторы MOD, судя по формуле это просто деление на цело.
Тогда можно было писать $F_n=(-1)^k(mod \ n)$, где k=0, для окончивающихся на 1 или 9 и 1, для окончивающихся на 3 или 7.
Всё это верно в одну сторону, если n просто то это сравнение выполняется. Это связано с нашей системой счисления 10=2*5, а 5 участвует в определении чисел Фибоначчи. Обратное может и не верно.

[Decorator]

MOD это целая часть всего того, что ограничено скобками перед этим оператором. Я больше терминами Excel владею. Там этот оператор называется "Целое". Но в Mathcad эта штука вроде именуется MOD

[Руст]

Думаю можно найти контрпример, т.е. случай, когда это сравнение выполняется не для простого n, только примеры будут большими. Это наподобии псевдопростых, когда $\phi(n)|n-1$ для оснований золотого сечения. А для простых эти сравнения легко доказываются.

[Decorator]

Обратное тоже верно. Результаты тестов специфичны именно для групп чисел оканчивающихся на 1 и 9 и ,соответственно,на 3 и 7. Для любых непростых чисел оканчивающихся на эти цифры условие не будет соблюдаться.

Добавлено спустя 1 минуту 50 секунд:

Я заставил этот метод работать на поиск простых чисел (наподобии решета Эратосфена). Проверил на диапазоне 50000. И все сошлось. Не одного отброшенного результата.

[Руст]

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

[Decorator]

Я с помощью этой методики нашел все простые числа в диапазоне 50000. и ни одного "псевдочисла" не обнаружилось.

Добавлено спустя 5 минут 36 секунд:

Я делал так. В Visual Basic программировал проверку всех чисел начиная с 3-х с шагом 10 с помощью этой формулы. Все числа которые отвечали условию оказывались простыми. Так же поступал с числами на 1, 9, и 7. В итоге сопоставив массивы полученных чисел получал все простые числа (кроме 2 и 5) в диапазоне 50000

[Руст]

Ваше условие эквивалентно следующему: n прост, если
$lcm_{p|n}(p+(\frac{p}{5}))|n+(\frac{n}{5})$
поэтому обычное псевдопростое, у которого все простые делители 2 или 3 по модулю 5 по вашему тесту так же окажутся простыми.

[Decorator]

Плиз. Дайте мне несколько псевдопростых чисел, желательно из диапазона 50000. Я проверю в Visual Basic.

Добавлено спустя 31 минуту 13 секунд:

Ау! Вы где?

[Руст]

Ваш тест чуть сильнее псевдопростоты, примерно соответствует квазипростоты. Нечётное число n назовём квазипростым по основанию а, если $a^{(n-1)/2}=(\frac{a}{n})=(-1)^{(n-1)(a-1)/4}(\frac{n}{a})$ (последнее для нечётного а).
Простые числа, больше а являются квазипростыми, но существуют квазипростые (больше а)для любого а, не являющиеся простыми. Примерно такая же ситуация в вашем случае. Но я не обязан найти вам контрпример. Ищете сами, я только подскажу как. Ищите n в виде произведения k различных простых чисел, т.е. делайте перебор по различным простым числам $p_1,p_2,...,p_k$, вычисляйте $C=lcm(p_1+(\frac{p_1}{5}),p_2+(\frac{p_2}{5}),...,p_k+(\frac{p_k}{5}))$ и проверяйте $C|(n+(\frac{n}{5}))$. Без компьютера не найти контрпример. Но я уверен в его существовании.