Пары близнецов

Но я могу еще, я же сказал, что это легко :)

Тест на простоту числа p (на этот раз неважно, на что оканчивается):

1) 2^(p-1) mod p = 1,
2) G(p) mod p = 0,
где G(1) = 0, G(2) = 2, G(3) = 3, G(n)=G(n-2)+G(n-3).

Интересно, а за это что-нибудь дают?

Контр-пример должен быть одновременно псевдопростым Ферма и Перрина.

Как-то хитро у Вас все...
Вот я тоже придумал, по рабоче-крестьянски: b(1) = 0, b(2) = 6, b(n)=b(n-1) + 2b(n-2). Это как-нибудь соответствует тому, что Вы написали?

У меня было одинаковое доказательство. Правда, последовательность, которую я привел, это просто позор, потому что матрица
0 1
2 1
диагонализируется.

Но тем не менее.
Рассмотрим ориентированный граф с петлями и кратными ребрами. Утверждение: если p простое, то число циклов с выделенной вершиной длины p сравнимо с числом петель по модулю p. Это очевидно: у цикла можно выделить вершину p способами за исключением циклов, проходящих по одной петле.

При некоторых условиях на граф (думаю, сильной связности хватит) это число выражается рекуррентно. Вот и вся наука.

Для Перрена (Cardin->Карден, Perrin->Перрен?) граф будет иметь вид двух циклов с одной общей вершиной, один длины 2, другой длины 3.
Для Люка (той, что я привел) граф имеет три вершины, соединенных друг с другом туда-сюда. МТФ тоже тут: для основания a надо взять одну вершину и a петель.

Кому охота, может интерпретировать эти графы как конечные автоматы; если так сделать, то будет видно, что число Перрена - это число способов уложить "двушки" и "трешки" на закольцованной полоске, а число Люка - число правильных раскрасок цикла в три цвета.

Я все к чему - все это комбинаторика, ИМХО, но числовики все больше любят какие-то жуткие формулы ;)

А между прочим, находя некоторые простые числа разными тестами на псевдопростоту, мы с большой вероятностью находим простые числа. Отдельная проблема, что имея тест на простоту, мы не найдем простого числа, потому что замучаемся. Повторю: никакой тест на простоту не применим для поиска простых чисел.

Сообщение от 18.10 было для maxal'а, у которого были сложные формулы и он утверждал, что доказательства для последовательностей Люка и Перрена разные. У меня доказательства были одинаковые, теперь я даже понимаю, какое отношение это имеет к характеристическим многочленам.

А именно, рассмотрим квадратную матрицу A по модулю p. Утверждение:
det (A-xE) = det(A^p-xE) (mod p) при всех x = 0,1,...,p-1, где E - единичная матрица. То есть характеристический многочлен не меняется при возведении матрицы в степень p. Отсюда следует все, что говорил я и что говорил maxal.

Нет-нет, под поиском я имею в виду другую задачу, например, найти какое-нибудь простое число между 15e100 и 16e100. Решать эту задачу методом перебора (тем более по построенной таблице квадратов до 1e200 ;) ) - это издевательство над здравым смыслом.

Цитата

Что именно следует? Как отсюда увидеть, в чем же особенность последовательностей Люка и Перрена? Ведь далеко не каждая рекуррентная последовательность обладает тем свойством, что каждое простое p делит элемент с номером p.

Последовательность b(1) = 0, b(2) = 2, b(3)=3, b(n)=b(n-2) + b(n-3) - это след матрицы
0 1 0
0 0 1
1 1 0
в степени n. Последовательность b(1) = 0, b(2) = 6, b(n)=b(n-1) + 2b(n-2) - это след матрицы
0 1 1
1 0 1
1 1 0
в степени n. В страшные формулы я пока особо не вглядывался, но про Перрена там вроде бы все в том же духе, а про Люка не уверен. Дайте еще последовательность, я постараюсь придумать матрицу :)

След
0 1 0 0
0 0 1 0
0 0 0 1
1 7 -3 0
в степени n.

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