Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Все просто получается и без мультипликативных полугрупп 25.04.02 08:30 Число просмотров: 2883
Автор: Pm Статус: Незарегистрированный пользователь
|
Равенство a^x0 mod p + a^x1 mod p = p невозможно.
a^q mod p = 1 по требованию ГОСТа. Берем любое число k (0<k<q).
r=a^k mod p. Справедливо следующее равенство: r^q mod p = 1, так как
r^q mod p = (a^k - pn)^q mod p = a^(kq) mod p = 1.
Доказательство будем вести от противного.
Пусть существуют числа x0, x1 (0 < x0, x1 <q) такие, что
a^x0 mod p + a^x1 mod p = p. a^x0 mod p = y0, тогда
a^x1 mod p = p-y0. Для y0 и p-y0 должны выполняться равенства (см. свойство выше) y0^q mod p = 1 и (p-y0)^q mod p =1, что невозможно, так как
(p-y0)^q mod p = - y0^q mod p = -1. Противоречие.
Не надо выдвигать непроверенные предположения в статьях. Все "доказательства" великой теоремы Ферма в редакциях журналов выбрасывались сразу же в корзину.
Да, как выяснилось, r' может равняться 1. Например, при p=31, q=5, a=2, k=4.
|
|
|