Subject GRE-Style: Modular Arithmetic

GRE Math Subject · Axiom Academy

EXAMPLE Subject GRE-Style: Modular Arithmetic 3 worked problems on last digits, solving congruences, and Fermat/Euler theorems Key Tools: Fermat's Little Theorem: If is prime and , then . Euler's Theorem: If , then . Question: What is the last digit of ? (A) 1 (B) 3 (C) 7 (D) 9 (E) 49 "Last digit" means we work modulo 10. We need . Since , apply Euler's theorem: Speed Check: You can also just memorize the cycle of last digits of powers of 7: (period 4). Since with remainder 0, the last digit is the 4th in the cycle: 1 . Question: Find the smallest positive satisfying . (A) 2 (B) 5 (C) 7 (D) 8 (E) 10 Method 1 (Fermat): Since 11 is prime, . But that's slow to compute by hand. Method 2 (Inspection): We need . Try: . . . So . GRE Tip: On the exam, testing the answer choices is often faster than computing inverses. Multiply each choice by 7 and reduce mod 11. Fermat's Little Theorem Application (A) 0 (B) 1 (C) 2 (D) 340 (E) Cannot be determined Since , use CRT: compute mod 11 and mod 31 separately. Famous Fact: 341 is the smallest pseudoprime to base 2 -- a composite number satisfying . This shows Fermat's test can be fooled! The GRE loves this example.

This is the written version of the interactive lesson above. See the full GRE Math Subject course.