Прочитайте, как обстоят дела у сайта Дневников и как вы можете помочь!
×
01:24 

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

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

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

Комментарии
2012-12-08 в 12:14 

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

2012-12-08 в 13:14 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Я в теории чисел не силён... но вот такая мысль возникла...
В условии столько двоек... может её надо решать в двоичной системе счисления?...

2012-12-08 в 15:15 

Да тут все несложно. Во-первых, 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.

   

Не решается алгебра/высшая математика?.. ПОМОЖЕМ!

главная