#4 Теоремы Вильсона, Ферма и Эйлера в задачах

По Ферма \(2^{10}\equiv1\pmod{11}\). Так как \(2026\equiv6\pmod{10}\), получаем \(2^{2026}\equiv2^6=64\equiv9\pmod{11}\).

Так как \(\gcd(2,9)=1\), по Эйлеру \(2^6\equiv1\pmod9\). Поскольку \(100\equiv4\pmod6\), имеем \(2^{100}\equiv2^4=16\equiv7\pmod9\).

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

Так как \(11\) простое, \(10!\equiv-1\equiv10\pmod{11}\).

Используем формулу: \(\varphi(45)=45(1-1/3)(1-1/5)=45\cdot2/3\cdot4/5=24\).

Если \(p\mid a\), то \(a^p-a\) делится на \(p\). Если \(p\nmid a\), то \(a^{p-1}\equiv1\pmod p\), и после умножения на \(a\) получаем \(a^p\equiv a\pmod p\).

По Ферма \(7^{12}\equiv1\pmod{13}\). Так как \(100\equiv4\pmod{12}\), получаем \(7^{100}\equiv7^4\). \(7^2=49\equiv10\), значит \(7^4\equiv100\equiv9\pmod{13}\).

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

По Вильсону \(10!\equiv-1\pmod{11}\). Но \(10!=10\cdot9\cdot8!\equiv(-1)(-2)8!\equiv2\cdot8!\). Значит, \(2\cdot8!\equiv10\), откуда \(8!\equiv5\pmod{11}\).

По Вильсону \((p-1)!\equiv-1\pmod p\). Но \((p-1)!\equiv(p-1)(p-2)!\equiv-(p-2)!\pmod p\). Значит, \(-(p-2)!\equiv-1\), откуда \((p-2)!\equiv1\pmod p\).

Имеем \((p-1)!=(p-1)(p-2)(p-3)!\equiv(-1)(-2)(p-3)!\equiv2(p-3)!\pmod p\). По Вильсону это равно \(-1\). Значит, \(2(p-3)!\equiv-1\), откуда \((p-3)!\equiv -2^{-1}\pmod p\). Так как \(2^{-1}\equiv (p+1)/2\), получаем \((p-3)!\equiv (p-1)/2\pmod p\).

Заметим, что \(7^4\equiv1\pmod{100}\). Так как \(222\equiv2\pmod4\), получаем \(7^{222}\equiv7^2=49\pmod{100}\).

По форме Ферма \(a^p\equiv a\pmod p\). Умножая на \(a\), получаем \(a^{p+1}\equiv a^2\pmod p\). Значит, \(p\mid a^{p+1}-a^2\).

Так как \(8!\) содержит множители \(3\) и \(6\), произведение делится на \(9\). Поэтому \(8!\equiv0\pmod9\), а не \(-1\). Противоречия нет: теорема Вильсона утверждает сравнение \((p-1)!\equiv-1\pmod p\) для простого \(p\), а \(9\) составное.

По теореме Эйлера \(a^{\varphi(n)}\equiv1\pmod n\). Но \(a\cdot a^{\varphi(n)-1}=a^{\varphi(n)}\). Значит, \(a^{\varphi(n)-1}\) действительно является обратным элементом.

При \(p=2\) число \(2^{p-1}+1=3\) не делится на \(2\). Если \(p\) нечётно, то по Ферма \(2^{p-1}\equiv1\pmod p\). Тогда \(2^{p-1}+1\equiv2\pmod p\), что не равно \(0\). Ответ: таких простых нет.

В множестве \(1,2,\ldots,p-1\) каждый остаток имеет обратный. Остатки, равные своим обратным, удовлетворяют \(x^2\equiv1\pmod p\), значит \(x\equiv1\) или \(x\equiv-1\pmod p\). Все остальные остатки разбиваются на пары \(x,x^{-1}\), произведение каждой пары равно \(1\). Поэтому \((p-1)!\equiv1\cdot(-1)\equiv-1\pmod p\).

Самобратные элементы удовлетворяют \(x^2\equiv1\pmod p\), то есть это \(1\) и \(-1\). Произведение всех ненулевых остатков равно \((p-1)!\equiv-1\pmod p\). Если убрать множители \(1\) и \(-1\), то оставшееся произведение равно \((-1)/(1\cdot(-1))\equiv1\pmod p\).

\(\gcd(11,72)=1\), \(\varphi(72)=72(1-1/2)(1-1/3)=24\). Поэтому \(11^{24}\equiv1\pmod{72}\). Так как \(2026\equiv10\pmod{24}\), нужно найти \(11^{10}\pmod{72}\). \(11^2=121\equiv49\), \(11^4\equiv49^2=2401\equiv25\), \(11^8\equiv25^2=625\equiv49\). Тогда \(11^{10}=11^8\cdot11^2\equiv49\cdot49=2401\equiv25\pmod{72}\).

Пусть \(n\) составное. Если \(n=4\), то \(3!=6\equiv2\pmod4\), не \(-1\). Пусть теперь \(n\ne4\). Запишем \(n=ab\), где \(1