Дано нечётное простое p и натуральное k такое,что p^p-1\vdots pk+1. Докажите,что k-чётное.
Пытался решать взяв простой делитель q числа pk+1 и выходит что p^p\equiv 1\pmod q Дальше по МТФ и показатель,но так не получилось доказать что к-чётное.Также пытался от обратного что к-нечётное,но не получилось решить задачу.
1 лайк
Задача относительно известная, можно поискать на AoPS) Вот мое решение.
Если p^p - 1 делиться на степень простого q^k, то либо p либо 1 должен быть показателем q. Если показатель p, то q - 1 делиться на p; если же показатель 1, то p - 1 делиться на q, более того по лемме LTE p - 1 будет делиться на полную степень q^k.
Разложим число pk + 1 на простые делители и разобьём их на соответствующие два множества (те которые имеют показателем 1 и те что имеют им p.). Тогда произведение простых делителей первого множества будет делить p - 1, т.е. будет меньше p, а все простые делители второго множества будут по модулю p давать 1. Так как у нас pk + 1 тоже по модулю p дает 1, то произведение простых делителей первого множества равно 1 по модулю p, но так как это число меньше p, то оно в точности равно 1.
То есть оказывается, что все делители pk + 1 попадают во второе множество, то есть они вида pt + 1. Они не должны делиться на 2, поэтому t - будут четными, то есть каждое простое по отдельности дает 1 по модулю 2p, тогда и произведение должно быть также. Поэтому k - четное.
7 лайков