#3 Multiplicative Order

\(2^1\equiv2\), \(2^2\equiv4\), \(2^3\equiv8\equiv1\pmod7\). Since \(1\) did not appear earlier, the order is \(3\).

\(3,9,27,81,243\) modulo \(11\) give \(3,9,5,4,1\). Therefore \( \operatorname{ord}_{11}(3)=5 \).

Since the order of \(2\) modulo \(7\) is \(3\), reduce the exponent: \(100\equiv1\pmod3\). Hence \(2^{100}\equiv2\pmod7\).

Powers of \(3\) modulo \(10\) are \(3,9,7,1\), then the cycle repeats. Since \(2026\equiv2\pmod4\), the last digit is \(9\).

\(5^2=25\equiv12\equiv-1\pmod{13}\). Hence \(5^4\equiv1\). The order is not \(1\) or \(2\), because \(5\not\equiv1\) and \(5^2\not\equiv1\). Therefore the order is \(4\).

Let \(k=qd+r\), where \(0\le r

If \(d=\operatorname{ord}_m(a)\), then \(a^r\equiv1\) and \(a^s\equiv1\) imply \(d\mid r\) and \(d\mid s\). Therefore \(d\mid\gcd(r,s)\), hence \(a^{\gcd(r,s)}\equiv1\pmod m\).

From \(2^m\equiv1\pmod p\), we get \( \operatorname{ord}_p(2)\mid m \). Since \(p\) is prime and \(2\not\equiv0\pmod p\), the order also divides \(p-1\). Therefore it divides \(\gcd(m,p-1)\).

For \(p=2\), there is no divisibility. If \(p\) is odd, Fermat's little theorem gives \(2^p\equiv2\pmod p\). Then \(2^p+1\equiv3\pmod p\), so \(p\mid3\), hence \(p=3\). Check: \(2^3+1=9\) is divisible by \(3\).

From \(a^2+a+1\equiv0\pmod p\), we get \(a^3-1=(a-1)(a^2+a+1)\equiv0\pmod p\). If \(a\equiv1\pmod p\), then \(3\equiv0\pmod p\), so \(p=3\). If \(a\not\equiv1\), the order of \(a\) is \(3\), hence \(3\mid p-1\), so \(p\equiv1\pmod3\).

Compute \(7^2=49\), \(7^4\equiv49^2=2401\equiv1\pmod{100}\). Since \(100\) is divisible by \(4\), \(7^{100}=(7^4)^{25}\equiv1\pmod{100}\). The last two digits are \(01\).

We have \(5^2=25\not\equiv1\pmod{31}\), while \(5^3=125\equiv1\pmod{31}\). Hence \( \operatorname{ord}_{31}(5)=3 \). Therefore \(5^n\equiv1\pmod{31}\) if and only if \(3\mid n\).

Compute \(2^4=16\equiv-1\pmod{17}\), hence \(2^8\equiv1\). The order of \(2\) modulo \(17\) is \(8\), because the smaller divisors \(1,2,4\) do not give \(1\). Thus \(2^n\equiv-1\) exactly when \(n\equiv4\pmod8\).

From \(p\mid a^n+1\), we get \(a^n\equiv-1\pmod p\). Then \(a^{2n}\equiv1\), so the order divides \(2n\). If the order divided \(n\), then \(a^n\equiv1\pmod p\), contradicting \(a^n\equiv-1\pmod p\), since \(p\) is odd.

The number \(2^{16}+1\) is odd, so \(q\ne2\). From \(2^{16}\equiv-1\pmod q\), we get \(2^{32}\equiv1\). Also \(2^{16}\not\equiv1\), and the order divides \(32\). The only divisor of \(32\) that does not divide \(16\) is \(32\). Thus the order of \(2\) modulo \(q\) is \(32\). Therefore \(32\mid q-1\), so \(q\equiv1\pmod{32}\).

\(3^4+1=82=2\cdot41\). Hence \(p=2\) or \(p=41\). For the method: if \(p\ne2\) divides \(3^4+1\), then \(3^4\equiv-1\), so the order of \(3\) modulo \(p\) is \(8\), and \(8\mid p-1\). Among the divisors of \(82\), this holds only for \(41\).

From the condition \(a^{2^r}\equiv-1\pmod p\). Then \(a^{2^{r+1}}\equiv1\), so the order of \(a\) modulo \(p\) divides \(2^{r+1}\). But the order does not divide \(2^r\), otherwise \(a^{2^r}\equiv1\), not \(-1\). Among the divisors of \(2^{r+1}\), the only one not dividing \(2^r\) is \(2^{r+1}\). Hence the order is \(2^{r+1}\), and it divides \(p-1\).

Let \(q\) be a common prime divisor of \(F_m\) and \(F_n\), \(m

Take \(F_n=2^{2^n}+1\) for \(n\ge k-1\). Every prime divisor \(q\) of \(F_n\) is odd and, by the Fermat-type lemma, satisfies \(q\equiv1\pmod{2^{n+1}}\), hence also \(q\equiv1\pmod{2^k}\). The numbers \(F_n\) are pairwise coprime, so their prime divisors for different \(n\) do not repeat. Therefore infinitely many such primes exist.

Let \(d=\operatorname{ord}_p(a)\). From \(a^6\equiv1\pmod p\), we get \(d\mid6\). The conditions \(p\nmid a^3-1\) and \(p\nmid a^2-1\) mean \(d\nmid3\) and \(d\nmid2\). Among the divisors of \(6\), only \(6\) divides neither \(2\) nor \(3\). Hence \(d=6\). The order modulo a prime divides \(p-1\), so \(6\mid p-1\), meaning \(p\equiv1\pmod6\).