Остаток от деления

[wpoms.]

Пусть `m = (4^p - 1)/3`, где `p` простое число большее, чем `3`. Докажите, что `2^(m-1)` при делении на `m` имеет остаток равный `1`.

@темы: Теория чисел

Comments

[Alidoro]

Похоже на теорему Ферма. Но число m, что очевидно, составное. Может быть, как нибудь приспособить одно из доказательств теоремы ферма для решения этой задачи?

[All_ex]

Я в теории чисел не силён... но вот такая мысль возникла...
В условии столько двоек... может её надо решать в двоичной системе счисления?...

[kostyaknop]

Да тут все несложно. Во-первых, m-1 = (4^p-4)/3. По м.т.ф. 4^(p-1)-1 делится на p, Числа 3, 4 и p взаимно просты. Значит, m-1 делится на p. Причем m-1 четно, поэтому делится на 2p.
Теперь шаг второй. Поскольку m-1=2kp, то 2^{m-1} = 2^2kp = 4^kp. Число 4^p сравнимо с 1 по модулю 3m=(4^p-1), а значит, и с 1 по модулю m. Ну а тогда и 4^kp тоже сравнимо с 1.