Докажите, что следующие 3 условия эквивалентны:

  1. $%\exists m \geqslant 2, \forall x \in \mathbb{Z}_n : x = x^m$%

  2. $%\exists f \in \mathbb{Z}[t], \forall x \in \mathbb{Z}_n: x = x^2f(x)$%

  3. $%n$% свободен от квадратов, т.е. $%n = p_1...p_r,$% где $%p_i$% простые.

$%1 \rightarrow 2$% очевидно, т.к. можно выбрать $%f(x)$% как $%x^{m-2}$%. Не знаю как разобраться с остальными импликациями

задан 25 Мар '18 1:53

изменен 25 Мар '18 17:56

@Khan: в равенстве $%n=p_1\ldots p_n$% путаница обозначений. Число сомножителей надо обозначить как-то по-другому.

(25 Мар '18 2:26) falcao
10|600 символов нужно символов осталось
2

Докажем 2) => 3). Предположим, что n не свободно от квадратов. Тогда n делится на p^2 для некоторого простого p. Положим x=p. Получится, что p=p^2f(p) (mod n), откуда p=p^2f(p)=0 (mod p^2) -- противоречие.

Теперь докажем 3) => 1. Ввиду малой теоремы Ферма, x^{p-1}=1 (mod p) для любого x не делящегося на простое p. Положим m=(p(1)-1)...(p(r)-1)+1, где n=p(1)...p(r) -- свободное от квадратов число. Для любого i от 1 до r имеет место сравнение x^{m-1}=1 (mod p(i)), если x не делится на p(i). В любом случае, x^m=x (mod p(i)). Поэтому x^m-x делится на каждое p(i), а потому делится и на их произведение, откуда x^m=x (mod n).

ссылка

отвечен 25 Мар '18 2:35

А как это $%x^{m-1}=1 (mod p_i)$% следует из т. Ферма? Мы имеем $%x^{p_i-1}=1 (mod p_i)$%

(25 Мар '18 18:11) Khan

@Khan: основная идея выбора m как раз в том, что m-1 делится на все p(i)-1. Тогда x^{m-1}=x^{(p(i)-1)q(i)}=1^q(i)=1(mod p(i)).

(25 Мар '18 19:09) falcao

@falcao понял, спасибо!

(25 Мар '18 22:16) Khan
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×391
×236
×159
×71

задан
25 Мар '18 1:53

показан
267 раз

обновлен
25 Мар '18 22:16

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru