Вопрос по числам Ферма.

[yk2ru]

Как известно, тест на простоту чисел Ферма такой: $}3^{(F_n-1)/2}+1}\mod{F_n} = 0$.
Посчитал в Aribas (арифметический интерпретатор) остатки $}A^{(F_n-1)/2}}\mod{F_n}$ для чисел $A$ вида $2^n-1$ и $2^n+1$. Получилось вот что (код и результат):

n := 4; p2 := 2**(2**n) div 2;
p := p2*2 + 1;
writeln("p = ", p);
k := 1; l := 0;
for i := 1 to 2**n+1 do
m := (k-1)**p2 mod p;
if (m > p2) then
dec(m, p);
end;
writeln("2^",l,"-1 m = ", k-1, " ", m);
m := (k+1)**p2 mod p;
if (m > p2) then
dec(m, p);
end;
writeln("2^",l,"+1 m = ", k+1, " ", m);
k := k * 2; inc(l);
end.
p = 65537
2^0-1 m = 0 0
2^0+1 m = 2 1
2^1-1 m = 1 1
2^1+1 m = 3 -1
2^2-1 m = 3 -1
2^2+1 m = 5 -1
2^3-1 m = 7 -1
2^3+1 m = 9 1
2^4-1 m = 15 1
2^4+1 m = 17 1
2^5-1 m = 31 -1
2^5+1 m = 33 1
2^6-1 m = 63 -1
2^6+1 m = 65 -1
2^7-1 m = 127 -1
2^7+1 m = 129 1
2^8-1 m = 255 1
2^8+1 m = 257 1
2^9-1 m = 511 1
2^9+1 m = 513 -1
2^10-1 m = 1023 -1
2^10+1 m = 1025 -1
2^11-1 m = 2047 1
2^11+1 m = 2049 -1
2^12-1 m = 4095 1
2^12+1 m = 4097 1
2^13-1 m = 8191 1
2^13+1 m = 8193 -1
2^14-1 m = 16383 -1
2^14+1 m = 16385 -1
2^15-1 m = 32767 -1
2^15+1 m = 32769 1
2^16-1 m = 65535 1
2^16+1 m = 65537 0

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

[nnosipov]

Это закономерность, которая справедлива для всех чисел Ферма, т.е. не только для простых. Очевидно вытекает из свойств символа Якоби.

[yk2ru]

А как для случая простых чисел Ферма определить, где в результатах будет $1$, а где $-1$? Без возведения в степень возможно ли? Известно например, что для $5$ результат равен $-1$, если простое число Ферма оканчивается на $7$.

[nnosipov]

yk2ru в сообщении #490695 писал(а):

А как для случая простых чисел Ферма определить ...

Последнее известное простое число Ферма --- это 65537. В общем случае нужно вычислять символ Якоби $\left(\frac{2^k+1}{F_n}\right)$ при произвольном $k$, и простой формулы для него на первый взгляд не видно. Можно, конечно, поэксплуатировать квадратичный закон взаимности (именно таким образом и находится формула для $\left(\frac{5}{F_n}\right)$), но успех не гарантирован.

[yk2ru]

nnosipov в сообщении #490681 писал(а):

Это закономерность, которая справедлива для всех чисел Ферма, т.е. не только для простых. Очевидно вытекает из свойств символа Якоби.

Вот для числа $5$ это как раз не верно.

p = 5
2^0-1 m = 0 0
2^0+1 m = 2 -1
2^1-1 m = 1 1
2^1+1 m = 3 -1
2^2-1 m = 3 -1
2^2+1 m = 5 0

А для чисел $17$ и $257$ верно.

[nnosipov]

yk2ru в сообщении #490714 писал(а):

Вот для числа $5$ это как раз не верно.

Ваша правда. Но это единственное исключение. Вот точная формулировка утверждения: при $n>1$ и $k=0,1,\dots,2^n$ имеем

$$ \left(\frac{2^k+1}{2^{2^n}+1}\right)=\left(\frac{2^{2^n-k}-1}{2^{2^n}+1}\right). $$

[yk2ru]

Если продолжить числа несколько дальше, по которым вычислялись остатки, то получим:

p = 257
2^0-1 m = 0 0
2^0+1 m = 2 1
2^1-1 m = 1 1
2^1+1 m = 3 -1
2^2-1 m = 3 -1
2^2+1 m = 5 -1
2^3-1 m = 7 -1
2^3+1 m = 9 1
2^4-1 m = 15 1
2^4+1 m = 17 1
2^5-1 m = 31 1
2^5+1 m = 33 -1
2^6-1 m = 63 -1
2^6+1 m = 65 -1
2^7-1 m = 127 -1
2^7+1 m = 129 1
2^8-1 m = 255 1
2^8+1 m = 257 0
2^9-1 m = 511 -1
2^9+1 m = 513 1
2^10-1 m = 1023 -1
2^10+1 m = 1025 -1
2^11-1 m = 2047 1
2^11+1 m = 2049 -1
2^12-1 m = 4095 1
2^12+1 m = 4097 1
2^13-1 m = 8191 -1
2^13+1 m = 8193 1
2^14-1 m = 16383 -1
2^14+1 m = 16385 -1
2^15-1 m = 32767 1
2^15+1 m = 32769 -1
2^16-1 m = 65535 0

Тут $2^n=8$. Верно ли для ненулевого остатка $M_k=(2^k-1)^{(F_n-1)/2}\mod F_n$ при чётном $k>2^n$ и ненулевом $M_{k-2^n}$, что $M_k=M_{k-2^n}$.
Видно, что $M_{10}=M_2$, $M_{12}=M_4$ и $M_{14}=M_6$ для приведённых выше результатов.

[nnosipov]

yk2ru в сообщении #490864 писал(а):

Верно ли для ненулевого остатка $M_k=(2^k-1)^{(F_n-1)/2}\mod F_n$ при чётном $k>2^n$ и ненулевом $M_{k-2^n}$, что $M_k=M_{k-2^n}$.

При $n \geqslant 5$ мне не удалось найти ни один случай совпадения этих остатков.

[yk2ru]

nnosipov в сообщении #490878 писал(а):

При мне не удалось найти ни один случай совпадения этих остатков.

Наверное, тут уже важно условие на простоту числа Ферма $F_n$.
При этом можно записать, что $M_{2k}=M_k P_k$, где $P_k=(2^k+1)^{(F_n-1)/2}\mod F_n$, а сами остатки представлены числами $-1, 0, 1$.