Fermat's little theorem

Theorem

Fermat's little theorem

T-031Home MU-105Threads structure · number

Statement

Let \( p \) be a prime number and let \( a \in \mathbb{Z} \) be any integer. Then \( a^p \equiv a \pmod{p} \). Equivalently, in the stronger multiplicative form: if additionally \( p \nmid a \) (i.e. \( \gcd(a,p) = 1 \)), then \( a^{p-1} \equiv 1 \pmod{p} \). The two forms are equivalent: the second implies the first upon multiplying by \( a \) (and the case \( p \mid a \) is immediate), and the first implies the second by cancelling the unit \( a \) in \( \mathbb{Z}/p\mathbb{Z} \).

Why it matters

Fermat's little theorem is the first genuinely structural fact one meets about modular arithmetic: it says the multiplicative group \( (\mathbb{Z}/p\mathbb{Z})^\times \) has exponent dividing \( p-1 \), long before one has the vocabulary of groups. It is the engine behind fast modular exponentiation tricks, the computation of modular inverses via \( a^{-1} \equiv a^{p-2} \pmod p \), and the Fermat primality test that underlies practical algorithms such as Miller–Rabin.

Beyond computation, it is the prototype of a family of results — Euler's theorem, Lagrange's theorem on orders of group elements, the Frobenius endomorphism \( x \mapsto x^p \) in characteristic \( p \) — and it sits at the root of public-key cryptography: the correctness of RSA decryption is, at bottom, Fermat's little theorem applied through the Chinese remainder theorem.

Hypotheses

Hypothesis.\( p \) is prime. Drop this and the congruence collapses: take \( n = 4 \), \( a = 2 \); then \( 2^4 = 16 \equiv 0 \pmod 4 \) but \( 2 \not\equiv 0 \pmod 4 \). Likewise \( n = 6 \), \( a = 2 \): \( 2^6 = 64 \equiv 4 \not\equiv 2 \pmod 6 \). Primality is what makes \( \mathbb{Z}/p\mathbb{Z} \) an integral domain, and the proof leans on cancellation, which fails modulo a composite (e.g. \( 2 \cdot 2 \equiv 2 \cdot 0 \pmod 4 \) yet \( 2 \not\equiv 0 \)).

Hypothesis.\( a \in \mathbb{Z} \) arbitrary — for the form \( a^p \equiv a \pmod p \) no condition on \( a \) is needed; the statement is about all residue classes, including \( 0 \). No counterexample exists to drop here, but note the form is genuinely about congruence classes: it holds for negative \( a \) too, e.g. \( (-1)^2 = 1 \equiv -1 \pmod 2 \).

Hypothesis.\( p \nmid a \) for the multiplicative form \( a^{p-1} \equiv 1 \pmod p \). Drop it and the statement is false: \( a = p \) gives \( p^{p-1} \equiv 0 \not\equiv 1 \pmod p \). This is the coprimality condition that makes \( a \) a unit of \( \mathbb{Z}/p\mathbb{Z} \); the class of \( 0 \) has no multiplicative order. The same subtlety recurs in Euler's theorem, where \( \gcd(a,n)=1 \) is likewise essential.

Proof

We prove the multiplicative form \( a^{p-1} \equiv 1 \pmod p \) for \( p \nmid a \), then deduce \( a^p \equiv a \pmod p \) for all \( a \). The only external input is Euclid's lemma: if a prime \( p \) divides a product \( xy \), then \( p \mid x \) or \( p \mid y \).

Fix a prime \( p \) and \( a \in \mathbb{Z} \) with \( p \nmid a \). Set \( S = \{1, 2, \dots, p-1\} \), the nonzero residues modulo \( p \).

Setup: every integer not divisible by \( p \) is congruent modulo \( p \) to exactly one element of \( S \), by the division algorithm. A

For each \( x \in S \), \( ax \not\equiv 0 \pmod p \).

If \( p \mid ax \), Euclid's lemma forces \( p \mid a \) or \( p \mid x \); the first contradicts the hypothesis \( p \nmid a \), the second contradicts \( 1 \le x \le p-1 \lt p \). So the map \( x \mapsto ax \bmod p \) sends \( S \) into \( S \). B

The map \( \varphi : S \to S, \; \varphi(x) = ax \bmod p \) is injective: \( ax \equiv ay \pmod p \implies x \equiv y \pmod p \implies x = y. \)

From \( ax \equiv ay \) we get \( p \mid a(x-y) \); Euclid's lemma and \( p \nmid a \) give \( p \mid x - y \). Since \( x, y \in S \) we have \( |x - y| \le p - 2 \lt p \), so \( x - y = 0 \). This is the cancellation law in the integral domain \( \mathbb{Z}/p\mathbb{Z} \), proved here from first principles. C

\( \varphi \) is a bijection of \( S \), i.e. \( \{ a\cdot 1,\; a\cdot 2,\; \dots,\; a\cdot(p-1) \} \) is, modulo \( p \), a permutation of \( \{1, 2, \dots, p-1\} \).

An injective map from a finite set to itself is surjective (pigeonhole principle). This is the key idea of the proof: multiplication by a unit merely shuffles the nonzero residues. B

\[ \prod_{x=1}^{p-1} (ax) \equiv \prod_{x=1}^{p-1} x \pmod p, \qquad \text{i.e.} \qquad a^{p-1} \, (p-1)! \equiv (p-1)! \pmod p. \]

Multiply the two lists together: since one is a permutation of the other modulo \( p \), and congruence is compatible with multiplication (if \( u \equiv u' \) and \( v \equiv v' \) then \( uv \equiv u'v' \), from the definition of congruence), the products agree modulo \( p \). Factoring out one \( a \) from each of the \( p-1 \) terms on the left gives \( a^{p-1}(p-1)! \). B

\( p \nmid (p-1)! \), hence \( (p-1)! \) may be cancelled: \( a^{p-1} \equiv 1 \pmod p. \)

Each factor \( x \in \{1, \dots, p-1\} \) satisfies \( p \nmid x \); by repeated application of Euclid's lemma, \( p \nmid (p-1)! \). Then from \( p \mid (a^{p-1} - 1)(p-1)! \), Euclid's lemma gives \( p \mid a^{p-1} - 1 \), which is the claim. (Equivalently: \( (p-1)! \) is a unit in \( \mathbb{Z}/p\mathbb{Z} \), and units cancel.) C

For every \( a \in \mathbb{Z} \): \( a^p \equiv a \pmod p. \)

Two cases. If \( p \nmid a \), multiply Step 6 by \( a \) (compatibility of congruence with multiplication). If \( p \mid a \), then \( a \equiv 0 \pmod p \), so \( a^p \equiv 0^p = 0 \equiv a \pmod p \) since congruence respects powers. Both cases give the universal form. \( \blacksquare \) A

Result

\[ p \text{ prime}, \; a \in \mathbb{Z} \implies a^p \equiv a \pmod p; \qquad p \nmid a \implies a^{p-1} \equiv 1 \pmod p. \]

Reading. Raising to the \( p \)-th power does nothing modulo a prime \( p \): every residue class is fixed by \( x \mapsto x^p \). For nonzero residues, the exponent cycle length divides \( p - 1 \), so exponents may be reduced modulo \( p-1 \) when the base is coprime to \( p \).

Scope. Applies to every prime \( p \) (including \( p = 2 \)) and every integer \( a \), positive, negative, or zero. The multiplicative form requires \( \gcd(a,p) = 1 \). The theorem is about the modulus being prime; for composite moduli one must pass to Euler's theorem \( a^{\phi(n)} \equiv 1 \pmod n \) (still requiring \( \gcd(a,n) = 1 \)), and the universal form \( a^n \equiv a \) fails for general composite \( n \).

Corollaries & converses

Modular inverses. If \( p \nmid a \) then \( a^{-1} \equiv a^{p-2} \pmod p \): a closed formula for inverses, since \( a \cdot a^{p-2} = a^{p-1} \equiv 1 \).
Order divides \( p-1 \). The multiplicative order \( d = \mathrm{ord}_p(a) \) of any \( a \) with \( p \nmid a \) divides \( p - 1 \). (Write \( p-1 = qd + r \), \( 0 \le r \lt d \); then \( a^r \equiv 1 \), forcing \( r = 0 \) by minimality of \( d \).)
Exponent reduction. For \( p \nmid a \) and any \( m \equiv n \pmod{p-1} \) with \( m, n \ge 0 \): \( a^m \equiv a^n \pmod p \).
Frobenius is additive. Combined with \( p \mid \binom{p}{k} \) for \( 0 \lt k \lt p \), it yields \( (x+y)^p \equiv x^p + y^p \pmod p \) — the "freshman's dream" is a theorem in characteristic \( p \).
Fermat primality test. If \( a^{n-1} \not\equiv 1 \pmod n \) for some \( a \) with \( \gcd(a,n) = 1 \), then \( n \) is composite — a compositeness certificate requiring no factorisation.
The converse is FALSE. \( a^{n-1} \equiv 1 \pmod n \) for some (or even all coprime) \( a \) does not imply \( n \) prime. Counterexample: \( 341 = 11 \cdot 31 \) satisfies \( 2^{340} \equiv 1 \pmod{341} \) (a Fermat pseudoprime to base 2). Worse, the Carmichael number \( 561 = 3 \cdot 11 \cdot 17 \) satisfies \( a^{561} \equiv a \pmod{561} \) for every integer \( a \).
A true partial converse (Lucas). If \( a^{n-1} \equiv 1 \pmod n \) and \( a^{(n-1)/q} \not\equiv 1 \pmod n \) for every prime \( q \mid n-1 \), then \( n \) is prime.

Fails without

Composite modulus, universal form: \( n = 4, a = 2 \): \( 2^4 = 16 \equiv 0 \pmod 4 \), but \( a = 2 \not\equiv 0 \). Similarly \( n = 6, a = 2 \): \( 2^6 = 64 \equiv 4 \not\equiv 2 \pmod 6 \). The congruence \( a^n \equiv a \pmod n \) is simply false for general composite \( n \).
Composite modulus, multiplicative form: \( n = 8, a = 3 \), \( \gcd(3,8) = 1 \): \( 3^{7} = 2187 = 273 \cdot 8 + 3 \equiv 3 \not\equiv 1 \pmod 8 \). Coprimality alone does not rescue the statement; the correct exponent is Euler's \( \phi(8) = 4 \), and indeed \( 3^4 = 81 \equiv 1 \pmod 8 \).
Dropping \( p \nmid a \) in the multiplicative form: \( a = 10, p = 5 \): \( 10^{4} = 10000 \equiv 0 \not\equiv 1 \pmod 5 \). The zero class has no inverse and no order.

Common errors

Reducing the exponent modulo \( p \) instead of \( p - 1 \). To compute \( 2^{100} \bmod 13 \), students write \( 100 \equiv 9 \pmod{13} \) and evaluate \( 2^9 \). Wrong: exponents live modulo \( p - 1 = 12 \) (when \( p \nmid a \)), so \( 100 \equiv 4 \pmod{12} \) and \( 2^{100} \equiv 2^4 = 16 \equiv 3 \pmod{13} \).
Applying \( a^{p-1} \equiv 1 \) when \( p \mid a \). E.g. claiming \( 15^{4} \equiv 1 \pmod 5 \); in fact \( 15 \equiv 0 \), so \( 15^4 \equiv 0 \). Always check coprimality before using the \( a^{p-1} \) form; the \( a^p \equiv a \) form is the safe universal one.
Using the theorem with a composite modulus. Writing \( a^{n-1} \equiv 1 \pmod n \) for composite \( n \) with \( \gcd(a,n)=1 \). The correct generalisation is Euler: \( a^{\phi(n)} \equiv 1 \pmod n \), and \( \phi(n) \lt n - 1 \) for composite \( n \).
Believing the converse. Concluding \( n \) is prime from \( 2^{n-1} \equiv 1 \pmod n \). Fermat pseudoprimes (341, 561, 645, ...) defeat this; Carmichael numbers defeat it for every base coprime to \( n \).
Confusing "little" with "last". Fermat's little theorem (this page) is elementary and was proved by Euler in 1736; Fermat's Last Theorem (\( x^n + y^n = z^n \) has no positive integer solutions for \( n \ge 3 \)) was proved by Wiles in 1995 and is unrelated in difficulty and technique.
Sign slips with negative bases. E.g. computing \( (-2)^{10} \bmod 11 \) as \( -2^{10} \). Reduce the base first: \( -2 \equiv 9 \pmod{11} \), then apply the theorem to \( 9 \).

Discussion

Fermat stated the result in a letter to Frénicle de Bessy dated 18 October 1640, adding, characteristically, that he would send the proof "were it not too long". No proof of Fermat's survives. Leibniz left an unpublished proof (via the binomial expansion) around 1680, and the first published proof is Euler's of 1736; Euler later recast and generalised it (1763) to composite moduli using his totient function \( \phi \): if \( \gcd(a,n) = 1 \) then \( a^{\phi(n)} \equiv 1 \pmod n \). Fermat's little theorem is the special case \( n = p \), where \( \phi(p) = p - 1 \).

The modern viewpoint absorbs the theorem into group theory: \( (\mathbb{Z}/p\mathbb{Z})^\times \) is a group of order \( p - 1 \), and Lagrange's theorem says the order of any element divides the order of the group, whence \( a^{p-1} = (a^{\mathrm{ord}(a)})^{(p-1)/\mathrm{ord}(a)} \equiv 1 \). The permutation argument given above is exactly the standard proof of the finite-group fact "multiplication by a group element permutes the group", specialised to \( (\mathbb{Z}/p\mathbb{Z})^\times \) — so the elementary proof and the group-theoretic one are the same proof in different clothing. There is also a lovely combinatorial proof: the number of necklaces with \( p \) beads in \( a \) colours, counted up to rotation, is \( (a^p - a)/p \) plus the \( a \) monochrome ones; since this count is an integer, \( p \mid a^p - a \). This "necklace" argument, essentially Burnside counting for the cyclic group \( C_p \), needs \( p \) prime so that every non-monochrome necklace has trivial rotational stabiliser.

The theorem's failure to have a true converse spawned a rich theory. Composites \( n \) with \( a^{n-1} \equiv 1 \pmod n \) are Fermat pseudoprimes to base \( a \); composites that are pseudoprimes to every coprime base are Carmichael numbers, characterised by Korselt's criterion (1899): \( n \) is Carmichael iff \( n \) is squarefree and \( p - 1 \mid n - 1 \) for every prime \( p \mid n \). Alford, Granville and Pomerance proved in 1994 that there are infinitely many Carmichael numbers. This is why practical primality testing strengthens Fermat's test to the Miller–Rabin test, which has no analogue of Carmichael numbers: every odd composite fails Miller–Rabin for at least three quarters of the bases.

In algebraic language the theorem says the Frobenius map \( F : x \mapsto x^p \) is the identity on the prime field \( \mathbb{F}_p \) — equivalently, \( \mathbb{F}_p \) is precisely the fixed field of Frobenius acting on any extension \( \mathbb{F}_{p^n} \), the polynomial \( X^p - X \) splits as \( \prod_{c \in \mathbb{F}_p} (X - c) \), and \( X^{p^n} - X \) is the product of all monic irreducibles over \( \mathbb{F}_p \) of degree dividing \( n \). This identity-on-the-base-field property is the degree-one case of the general fact that \( \mathrm{Gal}(\mathbb{F}_{p^n}/\mathbb{F}_p) \) is cyclic of order \( n \) generated by Frobenius; lifted to number fields, Frobenius elements at unramified primes govern splitting laws, and their equidistribution is the content of the Chebotarev density theorem. Fermat's little theorem is thus the seed of a very large tree. Common misconceptions. (i) It is not "Fermat's Last Theorem". (ii) Euler's theorem does not say \( a^{\phi(n)} \equiv 1 \) for all \( a \) — coprimality is essential, and for non-coprime \( a \) even \( a^{\phi(n)+1} \equiv a \pmod n \) can fail when \( n \) is not squarefree (e.g. \( n = 4, a = 2 \): \( 2^{\phi(4)+1} = 2^3 = 8 \equiv 0 \not\equiv 2 \)). (iii) The exponent \( p - 1 \) is an upper bound structure, not the order of every element: the order of \( a \) can be any divisor of \( p - 1 \), and equals \( p-1 \) exactly when \( a \) is a primitive root.

Worked examples

Example 1. Compute \( 2^{1000} \bmod 13 \).

\( 13 \) is prime and \( 13 \nmid 2 \), so Fermat's little theorem gives \( 2^{12} \equiv 1 \pmod{13} \).

Multiplicative form of the theorem with \( p = 13 \), \( a = 2 \); coprimality is clear since \( 2 \lt 13 \) and \( 13 \) is odd. A

Divide the exponent by \( 12 \): \( 1000 = 12 \cdot 83 + 4 \), so \( 2^{1000} = \left(2^{12}\right)^{83} \cdot 2^4. \)

Division algorithm on the exponent; laws of exponents. This is the "reduce the exponent modulo \( p-1 \)" step — legal only because \( \gcd(2,13) = 1 \). B

\( 2^{1000} \equiv 1^{83} \cdot 2^4 = 16 \equiv 3 \pmod{13}. \)

Substitute \( 2^{12} \equiv 1 \) from Step 1; congruence respects powers and products; finally \( 16 - 13 = 3 \). A

\[ 2^{1000} \equiv 3 \pmod{13} \]

Reading. A 302-digit power collapses to a single-digit computation because exponents work modulo \( p - 1 = 12 \).

Scope. The method computes \( a^N \bmod p \) for any prime \( p \nmid a \) and any \( N \ge 0 \) in \( \mathcal{O}(\log N) \) multiplications at worst, and here in just two.

Example 2. Find \( 7^{-1} \pmod{11} \) using the theorem.

\( 11 \) is prime, \( 11 \nmid 7 \), so \( 7^{10} \equiv 1 \pmod{11} \), hence \( 7 \cdot 7^{9} \equiv 1 \pmod{11} \) and \( 7^{-1} \equiv 7^{9} \pmod{11}. \)

Fermat's little theorem, then peel off one factor of \( 7 \); by definition, \( 7^9 \) is then a multiplicative inverse of \( 7 \) modulo \( 11 \). B

Compute \( 7^9 \bmod 11 \) by repeated squaring: \( 7^2 = 49 \equiv 5, \quad 7^4 \equiv 5^2 = 25 \equiv 3, \quad 7^8 \equiv 3^2 = 9 \pmod{11}. \)

Square-and-reduce at each stage; congruence is compatible with multiplication, so reducing intermediate results is legal. A

\( 7^9 = 7^8 \cdot 7 \equiv 9 \cdot 7 = 63 \equiv 8 \pmod{11}. \) Check: \( 7 \cdot 8 = 56 = 5 \cdot 11 + 1 \equiv 1 \pmod{11}. \)

Binary expansion \( 9 = 8 + 1 \) of the exponent; the final verification confirms the inverse property directly. A

\[ 7^{-1} \equiv 8 \pmod{11} \]

Reading. The theorem converts inversion into exponentiation: \( a^{-1} \equiv a^{p-2} \pmod p \), computable by fast powering with no Euclidean algorithm.

Scope. Works modulo any prime \( p \) for any \( a \) with \( p \nmid a \); modulo a composite \( n \) one must instead use \( a^{\phi(n)-1} \) (requiring \( \gcd(a,n)=1 \)) or the extended Euclidean algorithm.

Problems

Compute \( 3^{100} \bmod 7 \).
Solution

\( 7 \) is prime and \( 7 \nmid 3 \), so \( 3^{6} \equiv 1 \pmod 7 \). Write \( 100 = 6 \cdot 16 + 4 \). Then \[ 3^{100} = \left(3^{6}\right)^{16} \cdot 3^{4} \equiv 1^{16} \cdot 81 \equiv 81 \pmod 7. \] Since \( 81 = 11 \cdot 7 + 4 \), we get \( 3^{100} \equiv 4 \pmod 7 \).
Show that \( 341 \) is a Fermat pseudoprime to base \( 2 \): that is, \( 341 \) is composite yet \( 2^{340} \equiv 1 \pmod{341} \). Conclude that the converse of Fermat's little theorem fails.
Solution

First, \( 341 = 11 \cdot 31 \) is composite. Next observe \( 2^{10} = 1024 = 3 \cdot 341 + 1 \), so \[ 2^{10} \equiv 1 \pmod{341}. \] Therefore \[ 2^{340} = \left(2^{10}\right)^{34} \equiv 1^{34} = 1 \pmod{341}. \] So \( 341 \) passes the Fermat test to base \( 2 \) despite being composite: the condition \( a^{n-1} \equiv 1 \pmod n \) does not certify primality. (For contrast, \( 3^{340} \equiv 56 \not\equiv 1 \pmod{341} \), so base \( 3 \) exposes \( 341 \); Carmichael numbers such as \( 561 \) are not exposed by any coprime base.)
Let \( p \) be prime and \( a, b \in \mathbb{Z} \). Prove that \( p \mid (a+b)^p - a^p - b^p \).
Solution

Apply the universal form of Fermat's little theorem three times: \[ (a+b)^p \equiv a + b \pmod p, \qquad a^p \equiv a \pmod p, \qquad b^p \equiv b \pmod p. \] Subtracting, \[ (a+b)^p - a^p - b^p \equiv (a+b) - a - b = 0 \pmod p, \] which is the claim. (Alternative route: expand by the binomial theorem and use \( p \mid \binom{p}{k} \) for \( 0 \lt k \lt p \), which holds because \( p \) divides the numerator \( p! \) of \( \binom{p}{k} = \frac{p!}{k!(p-k)!} \) but not the denominator, \( p \) being prime and every factor of \( k!(p-k)! \) being \( \lt p \).)
Prove that \( n^{7} \equiv n \pmod{42} \) for every integer \( n \).
Solution

Since \( 42 = 2 \cdot 3 \cdot 7 \) with the three prime factors distinct, it suffices (by the Chinese remainder theorem, or simply because \( 2, 3, 7 \) are pairwise coprime and each divides \( n^7 - n \)) to prove the congruence modulo \( 2 \), \( 3 \) and \( 7 \) separately.

Mod 7: directly, \( n^{7} \equiv n \pmod 7 \) by Fermat's little theorem with \( p = 7 \).

Mod 3: \( n^{3} \equiv n \pmod 3 \) by the theorem, hence \[ n^{7} = \left(n^{3}\right)^{2} \cdot n \equiv n^{2} \cdot n = n^{3} \equiv n \pmod 3. \]

Mod 2: \( n^{2} \equiv n \pmod 2 \) by the theorem (or since \( n^2 \) and \( n \) share parity), hence iterating, \[ n^{7} = \left(n^{2}\right)^{3} \cdot n \equiv n^{3} \cdot n = n^{4} = \left(n^{2}\right)^{2} \equiv n^{2} \equiv n \pmod 2. \]

Each of \( 2, 3, 7 \) divides \( n^{7} - n \); as they are pairwise coprime, their product \( 42 \) divides \( n^{7} - n \). Hence \( n^{7} \equiv n \pmod{42} \) for all \( n \in \mathbb{Z} \).
(a) Let \( p \) be prime, \( p \nmid a \), and let \( d = \mathrm{ord}_p(a) \) be the least positive integer with \( a^{d} \equiv 1 \pmod p \). Prove \( d \mid p - 1 \). (b) Deduce that every prime divisor \( q \) of the Mersenne number \( 2^{p} - 1 \) (with \( p \) prime) satisfies \( q \equiv 1 \pmod p \).
Solution

(a) By Fermat's little theorem, \( a^{p-1} \equiv 1 \pmod p \). Write \( p - 1 = qd + r \) with \( 0 \le r \lt d \) (division algorithm). Then \[ 1 \equiv a^{p-1} = \left(a^{d}\right)^{q} \cdot a^{r} \equiv 1^{q} \cdot a^{r} = a^{r} \pmod p. \] If \( r \gt 0 \) this contradicts the minimality of \( d \); hence \( r = 0 \) and \( d \mid p - 1 \).

(b) Let \( q \) be a prime with \( q \mid 2^{p} - 1 \). Then \( 2^{p} \equiv 1 \pmod q \); note \( q \) is odd, so \( q \nmid 2 \). Let \( d = \mathrm{ord}_q(2) \). A standard fact (proved exactly as in (a), replacing \( p-1 \) by \( p \)): \( 2^{p} \equiv 1 \pmod q \) implies \( d \mid p \). Since \( p \) is prime, \( d = 1 \) or \( d = p \). If \( d = 1 \) then \( 2 \equiv 1 \pmod q \), i.e. \( q \mid 1 \), impossible. So \( d = p \). By part (a) applied modulo \( q \) (with \( a = 2 \)), \( d \mid q - 1 \), i.e. \( p \mid q - 1 \), which says exactly \[ q \equiv 1 \pmod p. \] (Consequence: to test \( 2^{p} - 1 \) for primality one need only trial-divide by primes of the form \( kp + 1 \) — the observation with which Fermat himself factored \( 2^{37} - 1 = 223 \cdot 616318177 \), noting \( 223 = 6 \cdot 37 + 1 \).)