Проверка работы формул - решение задачи
Задача №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)`.
Комментарии
COOL
ең жаксы көмек болды.