Проверка работы формул - решение задачи

Задача №1

Найдите все пары `(n,p)` такие, что `n` принимает натуральные значения, `p` - простое число, `n<=2p` и выполнена делимость:

`n^(p-1)|(p-1)^n+1`.

Рассуждения:

1. Лобовое решение очень длинное/ничего не дает.

2. В силу ограничения `n<=2p` имеет смысл рассмотреть значения `n=p; 2p`.

3. `n=1` дает тривиальные решения `(n,p)=(1,p)` для любых простых `p`.

4. `p=2` дает пару решений `(2,2)`.

5. При `p>=3` получаем, что `(p-1)^n+1` нечетно, поэтому `n` нечетно. Тогда если `(n,p)>1`, достаточно рассмотреть только один случай `n=p`.

6. В каком то виде хочется использовать малую теорему Ферма. После пункта `5` получаем `(n,p)=1`, а значит `n^(p-1)-=1` `mod` `p`. Но это ничего не дает.

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

8. Мы скажем, что `q` является минимальным простым делителем `n` и попробуем поработать с `q`.

Решение:

1. `(p-1)^n+1 vdots n vdots q => (p-1)^n+1 vdots q`.

С другой стороны, `(p-1,q)=1 => (p-1)^(q-1)-1 vdots q` по малой теореме Ферма.

Мы знаем, что `(a^t-1,a^s-1)=a^((t,s))-1`. В частности, если `a^t-1 vdots q, a^s-1 vdots q => a^((t,s))-1 vdots q`.

Применить лемму мешает `+1` в первой делимости.

Избавимся от проблемы таким образом:

`(p-1)^n+1 vdots q => (p-1)^(2n)-1 vdots q`.

Значит, `(p-1)^((2n,q-1))-1 vdots q`.

Но, `(2n,q-1)=2`, поскольку `q` нечетно и `q` является делителем `n`.

Итак, `(p-1)^2-1 vdots q => p(p-2) vdots q => p vdots q` или `p-2 vdots q`.

2. Можно упростить решение применением другой леммы.

`(n,q-1)=1 => EE` целые `a,b` такие, что `an+b(q-1)=1`.

Тогда, `(p-1)=(p-1)^(an+b(q-1))=(p-1)^(an)*(p-1)^(b(q-1))-=(-1)^a*(1)^b` `mod` `q`.

`(p-1)^n-= -1` `mod` `q` по условию, второй остаток следует из малой теоремы Ферма.

`a` нечетно, поскольку `q-1` четно и `an+b(q-1)=1`.

Значит, `p-1-= -1` `mod` `q => p vdots q => p=q`.

`n<2p`, поэтому если `q` наименьший простой делитель `n => n=p`.

Заметим, что минимальность `q` не потребовалась.

Далее используем биномиальное разложение и получаем решение `(n,p)=(3,3)`. Это будет пункт `3`, который вы реализуете самостоятельно.

Ответ: `(n,p)=(1,p), (2,2), (3,3)`.