#12 Fermat, Euler and Power Cycles

We get \(2,4,3,1\), then the cycle repeats with period \(4\). Since \(17\equiv1\pmod4\), \(2^{17}\equiv2\pmod5\).

The cycle of last digits is \(3,9,7,1\). Since \(25\equiv1\pmod4\), the last digit is \(3\).

\(4^2=16\equiv2\pmod7\), \(4^3\equiv8\equiv1\pmod7\). Hence \(4^{12}=(4^3)^4\equiv1\pmod7\).

The number \(7\) is prime and \(7\nmid3\). By Fermat's little theorem, \(3^6\equiv1\pmod7\). Therefore \(7\mid3^6-1\).

\(\gcd(2,8)=2\ne1\), so Euler's theorem cannot be used. But \(2^3=8\equiv0\pmod8\), so every \(2^n\) with \(n\ge3\) is divisible by \(8\). Hence \(2^{10}\equiv0\pmod8\).

Since \(11\) is prime, \(5^{10}\equiv1\pmod{11}\). Also \(2026\equiv6\pmod{10}\), so \(5^{2026}\equiv5^6\). Now \(5^2\equiv3\), \(5^4\equiv9\), hence \(5^6\equiv9\cdot3=27\equiv5\pmod{11}\).

By Fermat, \(2^{12}\equiv1\pmod{13}\). Since \(100\equiv4\pmod{12}\), \(2^{100}\equiv2^4=16\equiv3\pmod{13}\).

\(7^2=49\equiv4\pmod9\), \(7^3\equiv4\cdot7=28\equiv1\pmod9\). Since \(50\equiv2\pmod3\), \(7^{50}\equiv7^2\equiv4\pmod9\).

\(\gcd(3,100)=1\), and \(\varphi(100)=40\). By Euler's theorem, \(3^{40}\equiv1\pmod{100}\). Thus the last two digits are \(01\).

\(11\equiv-1\pmod{12}\). The exponent \(2025\) is odd, so \(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\). Since \(1\) did not appear earlier, the order is \(6\).

From the previous problem, \(\operatorname{ord}_7(3)=6\). Therefore \(3^n\equiv1\pmod7\) if and only if \(6\mid n\). The answer is all positive multiples of \(6\).

Since \(2026\equiv2\pmod4\), \(2^{2026}\equiv2^2\equiv4\pmod5\) and \(3^{2026}\equiv3^2\equiv9\equiv4\pmod5\). The sum is \(4+4=8\equiv3\pmod5\).

Since \(13\) is prime and \(13\nmid5\), \(5^{12}\equiv1\pmod{13}\). Then \(5^{12k}=(5^{12})^k\equiv1^k\equiv1\pmod{13}\). Hence \(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}\). Since \(2026\equiv6\pmod{10}\), \(9^{2026}\equiv9^6\equiv41\pmod{100}\). The last two digits are \(41\).

Modulo \(4\), \(3^{2026}\equiv1\), since the exponent is even. Modulo \(7\), \(3^6\equiv1\), and \(2026\equiv4\pmod6\), so \(3^{2026}\equiv3^4=81\equiv4\pmod7\). We need a number congruent to \(1\) modulo \(4\) and to \(4\) modulo \(7\). It is \(25\). The answer is \(25\).

If \(p\mid a\), then \(a^p-a\equiv0-0\equiv0\pmod p\). If \(p\nmid a\), Fermat gives \(a^{p-1}\equiv1\pmod p\). Multiplying by \(a\), \(a^p\equiv a\pmod p\). In both cases, \(p\mid a^p-a\).

By Fermat, \(a^{p-1}\equiv1\pmod p\). But \(a\cdot a^{p-2}=a^{p-1}\). Therefore \(a\cdot a^{p-2}\equiv1\pmod p\), so \(a^{p-2}\) is the inverse.

Direct computation: \(7\cdot2=14\equiv1\pmod{13}\). Hence the inverse of \(7\) is \(2\). This agrees with Fermat: \(7^{11}\) must also be an inverse of \(7\).

\(2^5=32\equiv1\pmod{31}\). Since \(1000\) is divisible by \(5\), \(2^{1000}=(2^5)^{200}\equiv1\pmod{31}\).

For \(p=2\), \(2^2+1=5\), not divisible by \(2\). Let \(p\) be an odd prime. By Fermat in the form \(a^p\equiv a\pmod p\), \(2^p\equiv2\pmod p\). Then \(2^p+1\equiv3\pmod p\). For \(p\mid2^p+1\), we need \(p\mid3\), so \(p=3\). Check: \(2^3+1=9\), divisible by \(3\). The answer is \(p=3\).

We have \(a^2\equiv-1\pmod p\). Then \(a^4\equiv1\pmod p\), but \(a^2\not\equiv1\pmod p\), since that would give \(-1\equiv1\pmod p\), hence \(p=2\). Thus the order of \(a\) modulo \(p\) is \(4\). The order divides \(p-1\), so \(4\mid p-1\), i.e. \(p\equiv1\pmod4\).

By Fermat, \(3^p\equiv3\pmod p\) for every prime \(p\). Hence \(3^p+2\equiv5\pmod p\). If \(p\mid3^p+2\), then \(p\mid5\), so \(p=5\). Check: \(3^5+2=243+2=245\), divisible by \(5\). The answer is \(p=5\).

From the condition, \(2^{2^n}\equiv-1\pmod p\). Squaring gives \(2^{2^{n+1}}\equiv1\pmod p\). Thus the order of \(2\) modulo \(p\) divides \(2^{n+1}\). But it does not divide \(2^n\), because \(2^{2^n}\equiv-1\not\equiv1\pmod p\). Since all divisors of \(2^{n+1}\) are powers of two, the order is \(2^{n+1}\). The order of an element modulo prime \(p\) divides \(p-1\), hence \(2^{n+1}\mid p-1\). Therefore \(p\equiv1\pmod{2^{n+1}}\).