Найти все нат-е X, удолетворяющие сравнению.

[moscow5]

Найти все нат-е X, удолетворяющие сравнению $3^x=1(\mod{100})$
Решил я его фактически перебором. То есть рассмотрел два младших разряда числа $3^x$, где x=0,1,2...
И смотрим те значения, где младшие разряды равны 01 (то есть $3^x-1$ будет делиться на 100). Повторяется это с периодом равным 20. То есть $x=20n$, где n=1,2,3...
Но преподавателю это решение пришлось не по душе и он попросил решить это задание не перебором.

[Joker_vD]

Ха, а как еще порядок элемента в группе искать? Считаете $\varphi(100)$, раскладываете на множители и возводите тройку в эти степени.

[apriv]

Joker_vD в сообщении #679360 писал(а):

Ха, а как еще порядок элемента в группе искать? Считаете $\varphi(100)$, раскладываете на множители и возводите тройку в эти степени.

Ужас-то какой, зачем $\varphi(100)$? Достаточно $\varphi(25)$ и $\varphi(4)$. Ну и возвести тройку после этого достаточно в десятую и в четвёртую степень, и не по модулю 100, а по модулю 25.

[Joker_vD]

В четвертую-то зачем?

[apriv]

Из рассмотрения $\varphi(25)$ и $\varphi(4)$ видно, что порядок тройки является делителем числа 20. Любой собственный делитель числа 20 является делителем либо десятки, либо четверки.

[moscow5]

$\varphi(25)=20$
$\varphi(4)=2$
И после этого я не понял, зачем и почему надо возводить 3 в степени 10 и 4 по модулю 25?
$3^{10}\mod{25}=24$
$3^4\mod{25}=6$
Что из этого следует?

[moscow5]

Тему апать можно?

[Cash]

А все остальное вам понятно? Можете изложить решение до непонятного вам момента?

-- Вс фев 03, 2013 21:51:00 --

Проверка нужна, чтобы убедиться, что порядок элемента группы не может быть меньше.

[moscow5]

Сначала разложили 100 на множители $5^2 и 2^2$, потом нашли от каждого множителя функцию Эйлера. А дальше мне не понятно.

[ИСН]

Ну Вы про малую теорему Ферма слышали когда-нибудь, например?

[moscow5]

Слышал, но как ее можно использовать здесь я не понимаю.

[Cash]

То есть похоже ничего не поняли.
Вам знакомы понятия: группа, циклическая подгруппа, порядок группы, порядок элемента группы, кольцо вычетов?
Знаете какую-нибудь теорему, связывающую порядок группы с порядком элемента группы?
А как, ничего не вычисляя, указать такой $x$, что $3^x = 1 \pmod {100}$?

[ИСН]

...и выгрузил весь самосвал ребёнку на голову. Зачем? Можно знать и применять теорему Ферма, ничего не зная о группах.

-- Вс, 2013-02-03, 23:21 --

moscow5, так освежите знания. О чём эта теорема? что она утверждает?

[moscow5]

Теорема Ферма говорит о том, что если p - простое, а - целое и а не делится на p, то $a^{p-1}=1(modp)$

Но ведь в нашем случае p - не простое.

[ИСН]

Это частный случай. Есть более общее утверждение, которое годится не только для простых p. Но только там показатель степени выглядит иначе.