#4 Wilson, Fermat and Euler in Problems

By Fermat, \(2^{10}\equiv1\pmod{11}\). Since \(2026\equiv6\pmod{10}\), we get \(2^{2026}\equiv2^6=64\equiv9\pmod{11}\).

Since \(\gcd(2,9)=1\), Euler gives \(2^6\equiv1\pmod9\). Since \(100\equiv4\pmod6\), \(2^{100}\equiv2^4=16\equiv7\pmod9\).

Directly, \(7\cdot2=14\equiv1\pmod{13}\). Thus the inverse is \(2\). This agrees with Fermat: \(7^{12}\equiv1\), so \(7^{11}\) is also an inverse.

Since \(11\) is prime, \(10!\equiv-1\equiv10\pmod{11}\).

Use the formula: \(\varphi(45)=45(1-1/3)(1-1/5)=45\cdot2/3\cdot4/5=24\).

If \(p\mid a\), then \(a^p-a\) is divisible by \(p\). If \(p\nmid a\), Fermat gives \(a^{p-1}\equiv1\pmod p\), and multiplying by \(a\) gives \(a^p\equiv a\pmod p\).

By Fermat, \(7^{12}\equiv1\pmod{13}\). Since \(100\equiv4\pmod{12}\), \(7^{100}\equiv7^4\). Now \(7^2=49\equiv10\), so \(7^4\equiv100\equiv9\pmod{13}\).

\(\gcd(3,100)=1\), \(\varphi(100)=40\). Euler gives \(3^{40}\equiv1\pmod{100}\), hence \(3^{80}\equiv1\pmod{100}\). The last two digits are \(01\).

By Wilson, \(10!\equiv-1\pmod{11}\). But \(10!=10\cdot9\cdot8!\equiv(-1)(-2)8!\equiv2\cdot8!\). Hence \(2\cdot8!\equiv10\), so \(8!\equiv5\pmod{11}\).

By Wilson, \((p-1)!\equiv-1\pmod p\). But \((p-1)!\equiv(p-1)(p-2)!\equiv-(p-2)!\pmod p\). Hence \(-(p-2)!\equiv-1\), so \((p-2)!\equiv1\pmod p\).

We have \((p-1)!=(p-1)(p-2)(p-3)!\equiv(-1)(-2)(p-3)!\equiv2(p-3)!\pmod p\). By Wilson this equals \(-1\). Hence \(2(p-3)!\equiv-1\), so \((p-3)!\equiv -2^{-1}\pmod p\). Since \(2^{-1}\equiv (p+1)/2\), we get \((p-3)!\equiv (p-1)/2\pmod p\).

Notice that \(7^4\equiv1\pmod{100}\). Since \(222\equiv2\pmod4\), we get \(7^{222}\equiv7^2=49\pmod{100}\).

By Fermat's form, \(a^p\equiv a\pmod p\). Multiplying by \(a\), we get \(a^{p+1}\equiv a^2\pmod p\). Hence \(p\mid a^{p+1}-a^2\).

Since \(8!\) contains factors \(3\) and \(6\), the product is divisible by \(9\). Thus \(8!\equiv0\pmod9\), not \(-1\). There is no contradiction: Wilson's theorem states \((p-1)!\equiv-1\pmod p\) for prime \(p\), while \(9\) is composite.

Euler's theorem gives \(a^{\varphi(n)}\equiv1\pmod n\). But \(a\cdot a^{\varphi(n)-1}=a^{\varphi(n)}\). Hence \(a^{\varphi(n)-1}\) is indeed the inverse.

For \(p=2\), \(2^{p-1}+1=3\) is not divisible by \(2\). If \(p\) is odd, Fermat gives \(2^{p-1}\equiv1\pmod p\). Then \(2^{p-1}+1\equiv2\pmod p\), not \(0\). Answer: there are no such primes.

In the set \(1,2,\ldots,p-1\), every residue has an inverse. Residues equal to their own inverses satisfy \(x^2\equiv1\pmod p\), hence \(x\equiv1\) or \(x\equiv-1\pmod p\). All other residues pair as \(x,x^{-1}\), and each pair has product \(1\). Therefore \((p-1)!\equiv1\cdot(-1)\equiv-1\pmod p\).

The self-inverse elements satisfy \(x^2\equiv1\pmod p\), so they are \(1\) and \(-1\). The product of all nonzero residues is \((p-1)!\equiv-1\pmod p\). Removing the factors \(1\) and \(-1\), the remaining product is \((-1)/(1\cdot(-1))\equiv1\pmod p\).

\(\gcd(11,72)=1\), \(\varphi(72)=72(1-1/2)(1-1/3)=24\). Thus \(11^{24}\equiv1\pmod{72}\). Since \(2026\equiv10\pmod{24}\), we need \(11^{10}\pmod{72}\). Now \(11^2=121\equiv49\), \(11^4\equiv49^2=2401\equiv25\), \(11^8\equiv25^2=625\equiv49\). Hence \(11^{10}=11^8\cdot11^2\equiv49\cdot49=2401\equiv25\pmod{72}\).

Suppose \(n\) is composite. If \(n=4\), then \(3!=6\equiv2\pmod4\), not \(-1\). Now let \(n\ne4\). Write \(n=ab\), where \(1