#3 Мультипликативный порядок

\(2^1\equiv2\), \(2^2\equiv4\), \(2^3\equiv8\equiv1\pmod7\). Раньше \(1\) не появлялась, поэтому порядок равен \(3\).

\(3,9,27,81,243\) по модулю \(11\) дают \(3,9,5,4,1\). Поэтому \( \operatorname{ord}_{11}(3)=5 \).

Так как порядок \(2\) по модулю \(7\) равен \(3\), уменьшаем показатель: \(100\equiv1\pmod3\). Поэтому \(2^{100}\equiv2\pmod7\).

Степени \(3\) по модулю \(10\): \(3,9,7,1\), затем цикл повторяется. Так как \(2026\equiv2\pmod4\), последняя цифра равна \(9\).

\(5^2=25\equiv12\equiv-1\pmod{13}\). Тогда \(5^4\equiv1\). Порядок не равен \(1\) или \(2\), потому что \(5\not\equiv1\) и \(5^2\not\equiv1\). Значит, порядок равен \(4\).

Пусть \(k=qd+r\), где \(0\le r

Если \(d=\operatorname{ord}_m(a)\), то из \(a^r\equiv1\) и \(a^s\equiv1\) следует \(d\mid r\) и \(d\mid s\). Поэтому \(d\mid\gcd(r,s)\), а значит \(a^{\gcd(r,s)}\equiv1\pmod m\).

Из \(2^m\equiv1\pmod p\) следует \( \operatorname{ord}_p(2)\mid m \). Так как \(p\) простое и \(2\not\equiv0\pmod p\), порядок также делит \(p-1\). Следовательно, он делит \(\gcd(m,p-1)\).

При \(p=2\) делимости нет. Если \(p\) нечётно, то по малой теореме Ферма \(2^p\equiv2\pmod p\). Тогда \(2^p+1\equiv3\pmod p\), значит \(p\mid3\), откуда \(p=3\). Проверка: \(2^3+1=9\) делится на \(3\).

Из \(a^2+a+1\equiv0\pmod p\) получаем \(a^3-1=(a-1)(a^2+a+1)\equiv0\pmod p\). Если \(a\equiv1\pmod p\), то \(3\equiv0\pmod p\), значит \(p=3\). Если \(a\not\equiv1\), то порядок \(a\) равен \(3\), поэтому \(3\mid p-1\), то есть \(p\equiv1\pmod3\).

Вычислим \(7^2=49\), \(7^4\equiv49^2=2401\equiv1\pmod{100}\). Так как \(100\) делится на \(4\), получаем \(7^{100}=(7^4)^{25}\equiv1\pmod{100}\). Последние две цифры - \(01\).

Имеем \(5^2=25\not\equiv1\pmod{31}\), а \(5^3=125\equiv1\pmod{31}\). Значит, \( \operatorname{ord}_{31}(5)=3 \). Поэтому \(5^n\equiv1\pmod{31}\) тогда и только тогда, когда \(3\mid n\).

Вычислим: \(2^4=16\equiv-1\pmod{17}\), значит \(2^8\equiv1\). Порядок \(2\) по модулю \(17\) равен \(8\), потому что меньшие делители \(1,2,4\) не дают \(1\). Тогда \(2^n\equiv-1\) ровно тогда, когда \(n\equiv4\pmod8\).

Из \(p\mid a^n+1\) следует \(a^n\equiv-1\pmod p\). Тогда \(a^{2n}\equiv1\), поэтому порядок делит \(2n\). Если бы порядок делил \(n\), то было бы \(a^n\equiv1\pmod p\), что противоречит \(a^n\equiv-1\pmod p\), так как \(p\) нечётно.

Число \(2^{16}+1\) нечётно, значит \(q\ne2\). Из \(2^{16}\equiv-1\pmod q\) получаем \(2^{32}\equiv1\). При этом \(2^{16}\not\equiv1\), а порядок делит \(32\). Единственный делитель \(32\), который не делит \(16\), равен \(32\). Значит, порядок \(2\) по модулю \(q\) равен \(32\). Поэтому \(32\mid q-1\), то есть \(q\equiv1\pmod{32}\).

\(3^4+1=82=2\cdot41\). Значит, возможны \(p=2\) и \(p=41\). Для понимания метода: если \(p\ne2\) делит \(3^4+1\), то \(3^4\equiv-1\), значит порядок \(3\) по модулю \(p\) равен \(8\), и потому \(8\mid p-1\). Из делителей \(82\) это выполняется только для \(41\).

Из условия \(a^{2^r}\equiv-1\pmod p\). Тогда \(a^{2^{r+1}}\equiv1\), значит порядок \(a\) по модулю \(p\) делит \(2^{r+1}\). Но порядок не делит \(2^r\), потому что тогда \(a^{2^r}\equiv1\), а не \(-1\). Среди делителей \(2^{r+1}\) единственный, который не делит \(2^r\), равен \(2^{r+1}\). Значит, порядок равен \(2^{r+1}\), и он делит \(p-1\).

Пусть \(q\) - общий простой делитель \(F_m\) и \(F_n\), \(m

Возьмём \(F_n=2^{2^n}+1\) для \(n\ge k-1\). Любой простой делитель \(q\) числа \(F_n\) нечётен и по ферматовой лемме удовлетворяет \(q\equiv1\pmod{2^{n+1}}\), значит тем более \(q\equiv1\pmod{2^k}\). Числа \(F_n\) попарно взаимно просты, поэтому их простые делители при разных \(n\) не повторяются. Следовательно, таких простых бесконечно много.

Пусть \(d=\operatorname{ord}_p(a)\). Из \(a^6\equiv1\pmod p\) следует \(d\mid6\). Условия \(p\nmid a^3-1\) и \(p\nmid a^2-1\) означают, что \(d\nmid3\) и \(d\nmid2\). Среди делителей \(6\) только \(6\) не делит ни \(2\), ни \(3\). Значит, \(d=6\). Порядок по простому модулю делит \(p-1\), поэтому \(6\mid p-1\), то есть \(p\equiv1\pmod6\).