теория чисел на бесконечность

[rightways]

а) Найдите все натуральные числа $n$ для которых $2n^2|a^n-1$ выполняется для всех натуральных $a$ взаимно простых с $n$. (Турецкая национальная олимпиада 2016)

б) Найдите все натуральные числа $n$ для которых $n|a^n-1$ выполняется для всех натуральных $a$ взаимно простых с $n$.

[rightways]

Такое чувство, что есть решение из двух строк

[worm2]

Думаю, не всё так просто.
По задаче а) есть решения 2, 6, 42.
Я тут одним глазком подглядел (A014117), что есть ещё 1806, а больше нету.

[Sonic86]

Задача а) по большому счету - это простое упражнение на применение функции Кармайкла: https://en.wikipedia.org/wiki/Carmichael_function . Формула для ее вычисления имеется и несложная. С ее помощью задача преобразуется в такую:
Найти все $n: \lambda (2n^2)|n$. Далее несложно доказывается, что все решения свободны от квадратов (ограничение на показатель $k$ будет $2k-1\leqslant k$) образуют ЧУМ по отношению делимости (т.е. не случайно $2|6|42|1806$.):
Пусть $\lambda (2n^2)|n$, возьмем $p: p \nmid n$, $p>\text{наибольший простой делитель}(n)$. Тогда
$\lambda (2n^2p^2)|np$
$\lambda (2n^2p^2)=\operatorname{lcm} (\lambda(2n^2),p(p-1))=p\operatorname{lcm} (\lambda(2n^2),p-1)|np \Leftrightarrow $
$\operatorname{lcm} (\lambda(2n^2),p-1) | n \Leftrightarrow$
1) $\lambda(2n^2) | n$ - индукционный переход
2) $p-1 | n $ - ограничение сверху на $p$, дающее конечность перебора.
Остается позаниматься перебором, и получить $p=2;3;7;43$, дальше цепь обрывается и все.

С задачей б), похоже, аналогичная история, но в ней нет ограничения на показатели степеней простых и число решений явно бесконечно (например, $n=2^k$). Далее лезут все простые Ферма - их список мы уже явно не знаем......
Т.е. пусть множество $S$ таково, что $(\forall k)2^k \in S$ и если $a\in S, p-1|a, p>\text{наибольший простой делитель}(a)$, то $(\forall k)ap^k\in S$. Тогда $S$ - это ответ к задаче

(данные)

Вот, например, код их вывода:

gp > for(n=3,10^3,if(Mod(n,znstar(n)[2][1])==0,print(n"   "factor(n))))

А вот какие они бывают:
4 Mat([2, 2])
6 [2, 1; 3, 1]
8 Mat([2, 3])
12 [2, 2; 3, 1]
16 Mat([2, 4])
18 [2, 1; 3, 2]
20 [2, 2; 5, 1]
24 [2, 3; 3, 1]
32 Mat([2, 5])
36 [2, 2; 3, 2]
40 [2, 3; 5, 1]
42 [2, 1; 3, 1; 7, 1]
48 [2, 4; 3, 1]
54 [2, 1; 3, 3]
60 [2, 2; 3, 1; 5, 1]
64 Mat([2, 6])
72 [2, 3; 3, 2]
80 [2, 4; 5, 1]
84 [2, 2; 3, 1; 7, 1]
96 [2, 5; 3, 1]
100 [2, 2; 5, 2]
108 [2, 2; 3, 3]
120 [2, 3; 3, 1; 5, 1]
126 [2, 1; 3, 2; 7, 1]
128 Mat([2, 7])
144 [2, 4; 3, 2]
156 [2, 2; 3, 1; 13, 1]
160 [2, 5; 5, 1]
162 [2, 1; 3, 4]
168 [2, 3; 3, 1; 7, 1]
180 [2, 2; 3, 2; 5, 1]
192 [2, 6; 3, 1]
200 [2, 3; 5, 2]
216 [2, 3; 3, 3]
220 [2, 2; 5, 1; 11, 1]
240 [2, 4; 3, 1; 5, 1]
252 [2, 2; 3, 2; 7, 1]
256 Mat([2, 8])
272 [2, 4; 17, 1]
288 [2, 5; 3, 2]
294 [2, 1; 3, 1; 7, 2]
300 [2, 2; 3, 1; 5, 2]
312 [2, 3; 3, 1; 13, 1]
320 [2, 6; 5, 1]
324 [2, 2; 3, 4]
336 [2, 4; 3, 1; 7, 1]
342 [2, 1; 3, 2; 19, 1]
360 [2, 3; 3, 2; 5, 1]
378 [2, 1; 3, 3; 7, 1]
384 [2, 7; 3, 1]
400 [2, 4; 5, 2]
420 [2, 2; 3, 1; 5, 1; 7, 1]
432 [2, 4; 3, 3]
440 [2, 3; 5, 1; 11, 1]
468 [2, 2; 3, 2; 13, 1]
480 [2, 5; 3, 1; 5, 1]
486 [2, 1; 3, 5]
500 [2, 2; 5, 3]
504 [2, 3; 3, 2; 7, 1]
512 Mat([2, 9])
540 [2, 2; 3, 3; 5, 1]
544 [2, 5; 17, 1]
576 [2, 6; 3, 2]
588 [2, 2; 3, 1; 7, 2]
600 [2, 3; 3, 1; 5, 2]
624 [2, 4; 3, 1; 13, 1]
640 [2, 7; 5, 1]
648 [2, 3; 3, 4]
660 [2, 2; 3, 1; 5, 1; 11, 1]
672 [2, 5; 3, 1; 7, 1]
684 [2, 2; 3, 2; 19, 1]
720 [2, 4; 3, 2; 5, 1]
756 [2, 2; 3, 3; 7, 1]
768 [2, 8; 3, 1]
780 [2, 2; 3, 1; 5, 1; 13, 1]
800 [2, 5; 5, 2]
816 [2, 4; 3, 1; 17, 1]
840 [2, 3; 3, 1; 5, 1; 7, 1]
864 [2, 5; 3, 3]
880 [2, 4; 5, 1; 11, 1]
882 [2, 1; 3, 2; 7, 2]
900 [2, 2; 3, 2; 5, 2]
936 [2, 3; 3, 2; 13, 1]
960 [2, 6; 3, 1; 5, 1]
972 [2, 2; 3, 5]
1000 [2, 3; 5, 3]