#12 Ферма, Эйлер и циклы степеней

Имеем \(2,4,3,1\), затем цикл повторяется с периодом \(4\). Так как \(17\equiv1\pmod4\), получаем \(2^{17}\equiv2\pmod5\).

Цикл последних цифр: \(3,9,7,1\). Поскольку \(25\equiv1\pmod4\), последняя цифра равна \(3\).

\(4^2=16\equiv2\pmod7\), \(4^3\equiv8\equiv1\pmod7\). Значит, \(4^{12}=(4^3)^4\equiv1\pmod7\).

Число \(7\) простое и \(7\nmid3\). По малой теореме Ферма \(3^6\equiv1\pmod7\). Поэтому \(7\mid3^6-1\).

\(\gcd(2,8)=2\ne1\), поэтому теорема Эйлера неприменима. Но \(2^3=8\equiv0\pmod8\), значит, любая степень \(2^n\) при \(n\ge3\) делится на \(8\). Следовательно, \(2^{10}\equiv0\pmod8\).

Так как \(11\) простое, \(5^{10}\equiv1\pmod{11}\). \(2026\equiv6\pmod{10}\), значит, \(5^{2026}\equiv5^6\). \(5^2\equiv3\), \(5^4\equiv9\), поэтому \(5^6\equiv9\cdot3=27\equiv5\pmod{11}\).

По Ферма \(2^{12}\equiv1\pmod{13}\). Так как \(100\equiv4\pmod{12}\), имеем \(2^{100}\equiv2^4=16\equiv3\pmod{13}\).

\(7^2=49\equiv4\pmod9\), \(7^3\equiv4\cdot7=28\equiv1\pmod9\). Так как \(50\equiv2\pmod3\), получаем \(7^{50}\equiv7^2\equiv4\pmod9\).

\(\gcd(3,100)=1\), \(\varphi(100)=40\). По теореме Эйлера \(3^{40}\equiv1\pmod{100}\). Значит, последние две цифры равны \(01\).

\(11\equiv-1\pmod{12}\). Показатель \(2025\) нечетен, поэтому \(11^{2025}\equiv(-1)^{2025}\equiv-1\equiv11\pmod{12}\).

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

Из предыдущей задачи \(\operatorname{ord}_7(3)=6\). Поэтому \(3^n\equiv1\pmod7\) тогда и только тогда, когда \(6\mid n\). Ответ: все положительные кратные \(6\).

Так как \(2026\equiv2\pmod4\), имеем \(2^{2026}\equiv2^2\equiv4\pmod5\) и \(3^{2026}\equiv3^2\equiv9\equiv4\pmod5\). Сумма дает \(4+4=8\equiv3\pmod5\).

Так как \(13\) простое и \(13\nmid5\), имеем \(5^{12}\equiv1\pmod{13}\). Тогда \(5^{12k}=(5^{12})^k\equiv1^k\equiv1\pmod{13}\). Значит, \(13\mid5^{12k}-1\).

\(9^1\equiv9\), \(9^2\equiv81\), \(9^3\equiv29\), \(9^4\equiv61\), \(9^5\equiv49\), \(9^6\equiv41\), \(9^7\equiv69\), \(9^8\equiv21\), \(9^9\equiv89\), \(9^{10}\equiv1\pmod{100}\). Так как \(2026\equiv6\pmod{10}\), получаем \(9^{2026}\equiv9^6\equiv41\pmod{100}\). Последние две цифры: \(41\).

По модулю \(4\): \(3^{2026}\equiv1\), так как показатель четный. По модулю \(7\): \(3^6\equiv1\), а \(2026\equiv4\pmod6\), значит, \(3^{2026}\equiv3^4=81\equiv4\pmod7\). Нужно число, которое равно \(1\) по модулю \(4\) и \(4\) по модулю \(7\). Это \(25\). Ответ: \(25\).

Если \(p\mid a\), то \(a^p-a\equiv0-0\equiv0\pmod p\). Если \(p\nmid a\), то по Ферма \(a^{p-1}\equiv1\pmod p\). Умножая на \(a\), получаем \(a^p\equiv a\pmod p\). В обоих случаях \(p\mid a^p-a\).

По Ферма \(a^{p-1}\equiv1\pmod p\). Но \(a\cdot a^{p-2}=a^{p-1}\). Следовательно, \(a\cdot a^{p-2}\equiv1\pmod p\), то есть \(a^{p-2}\) - обратный элемент.

Прямой счет: \(7\cdot2=14\equiv1\pmod{13}\). Значит, обратный элемент к \(7\) равен \(2\). Это согласуется с Ферма: \(7^{11}\) тоже должно быть обратным к \(7\).

\(2^5=32\equiv1\pmod{31}\). Так как \(1000\) делится на \(5\), имеем \(2^{1000}=(2^5)^{200}\equiv1\pmod{31}\).

При \(p=2\): \(2^2+1=5\), не делится на \(2\). Пусть \(p\) нечетное простое. По Ферма в форме \(a^p\equiv a\pmod p\) имеем \(2^p\equiv2\pmod p\). Тогда \(2^p+1\equiv3\pmod p\). Чтобы \(p\mid2^p+1\), нужно \(p\mid3\), то есть \(p=3\). Проверка: \(2^3+1=9\), делится на \(3\). Ответ: \(p=3\).

Имеем \(a^2\equiv-1\pmod p\). Тогда \(a^4\equiv1\pmod p\), но \(a^2\not\equiv1\pmod p\), так как это означало бы \(-1\equiv1\pmod p\), то есть \(p=2\). Значит, порядок \(a\) по модулю \(p\) равен \(4\). Порядок делит \(p-1\), поэтому \(4\mid p-1\), то есть \(p\equiv1\pmod4\).

По Ферма \(3^p\equiv3\pmod p\) для любого простого \(p\). Поэтому \(3^p+2\equiv5\pmod p\). Если \(p\mid3^p+2\), то \(p\mid5\), значит, \(p=5\). Проверка: \(3^5+2=243+2=245\), делится на \(5\). Ответ: \(p=5\).

Из условия \(2^{2^n}\equiv-1\pmod p\). Возводя в квадрат, получаем \(2^{2^{n+1}}\equiv1\pmod p\). Значит, порядок \(2\) по модулю \(p\) делит \(2^{n+1}\). Но порядок не делит \(2^n\), потому что \(2^{2^n}\equiv-1\not\equiv1\pmod p\). Так как делители \(2^{n+1}\) являются степенями двойки, порядок равен \(2^{n+1}\). Порядок элемента по модулю простого \(p\) делит \(p-1\), следовательно, \(2^{n+1}\mid p-1\). Значит, \(p\equiv1\pmod{2^{n+1}}\).