A brief note on Fermat, Euler and Wilson . Read it before a test. Try each question at the end before you open its answer.
The three theorems Fermat: a p ≡ a ( m o d p ) a^p \equiv a \pmod p a p ≡ a ( mod p ) for a prime p p p ; a p − 1 ≡ 1 a^{p-1} \equiv 1 a p − 1 ≡ 1 when p ∤ a p \nmid a p ∤ a . Euler: a φ ( n ) ≡ 1 ( m o d n ) a^{\varphi(n)} \equiv 1 \pmod n a φ ( n ) ≡ 1 ( mod n ) when gcd ( a , n ) = 1 \gcd(a, n) = 1 g cd( a , n ) = 1 . Wilson: ( p − 1 ) ! ≡ − 1 ( m o d p ) (p - 1)! \equiv -1 \pmod p ( p − 1 )! ≡ − 1 ( mod p ) exactly when p p p is prime. The totient Prime power: φ ( p k ) = p k − 1 ( p − 1 ) \varphi(p^k) = p^{k-1}(p - 1) φ ( p k ) = p k − 1 ( p − 1 ) . Product: φ ( m n ) = φ ( m ) φ ( n ) \varphi(mn) = \varphi(m)\varphi(n) φ ( mn ) = φ ( m ) φ ( n ) when gcd ( m , n ) = 1 \gcd(m, n) = 1 g cd( m , n ) = 1 . Formula: φ ( n ) = n ∏ ( 1 − 1 p ) \varphi(n) = n\prod(1 - \frac{1}{p}) φ ( n ) = n ∏ ( 1 − p 1 ) over the primes p ∣ n p \mid n p ∣ n . Divisor sum: ∑ d ∣ n φ ( d ) = n \sum_{d \mid n}\varphi(d) = n ∑ d ∣ n φ ( d ) = n . Orders Order: the least k ≥ 1 k \ge 1 k ≥ 1 with a k ≡ 1 ( m o d n ) a^k \equiv 1 \pmod n a k ≡ 1 ( mod n ) . Divides: a m ≡ 1 a^m \equiv 1 a m ≡ 1 exactly when the order divides m m m ; so the order divides φ ( n ) \varphi(n) φ ( n ) . Decimals: the period of 1 p \frac{1}{p} p 1 is the order of 10 10 10 modulo p p p . Minus one: x 2 ≡ − 1 ( m o d p ) x^2 \equiv -1 \pmod p x 2 ≡ − 1 ( mod p ) is solvable for p = 2 p = 2 p = 2 and for p ≡ 1 ( m o d 4 ) p \equiv 1 \pmod 4 p ≡ 1 ( mod 4 ) only. A worked example Find 5 123 5^{123} 5 123 modulo 36 36 36 .
Euler. φ ( 36 ) = 12 \varphi(36) = 12 φ ( 36 ) = 12 , and gcd ( 5 , 36 ) = 1 \gcd(5, 36) = 1 g cd( 5 , 36 ) = 1 . Cut. 123 = 12 × 10 + 3 123 = 12 \times 10 + 3 123 = 12 × 10 + 3 , so 5 123 ≡ 5 3 = 125 5^{123} \equiv 5^3 = 125 5 123 ≡ 5 3 = 125 . Reduce. 125 = 3 × 36 + 17 125 = 3 \times 36 + 17 125 = 3 × 36 + 17 , so the remainder is 17 17 17 . Practice with new numbers
A program to try The program checks each theorem on one small case.
Read it first. Then run it. Does each line print what the theorem predicts?
1. Change p, n = 11, 20 to p, n = 12, 21. Which line breaks, and why?
Mistakes to avoid Reducing an exponent modulo p p p instead of p − 1 p - 1 p − 1 . Using Euler when gcd ( a , n ) > 1 \gcd(a, n) > 1 g cd( a , n ) > 1 . Using Wilson or Fermat for a composite modulus. Losing a sign when peeling factors near p p p : p − 1 ≡ − 1 p - 1 \equiv -1 p − 1 ≡ − 1 , p − 2 ≡ − 2 p - 2 \equiv -2 p − 2 ≡ − 2 . Check yourself Find φ ( 84 ) \varphi(84) φ ( 84 ) . Stuck? Show a hint Show the answerFind the remainder of 4 51 4^{51} 4 51 on division by 7 7 7 . Stuck? Show a hint Show the answerFind 18 ! 18! 18 ! modulo 19 19 19 . Stuck? Show a hint Show the answerWhat is the order of 3 3 3 modulo 7 7 7 ? Stuck? Show a hint Show the answerSources David M. Burton, Elementary Number Theory , Chapters 5 and 7.