gen-define-fermat-s-little-theorem-and-give-one-short-worked-exa-0e9f

Define Fermat's little theorem and give one short worked example.

# Fermat's Little Theorem ## Definition If **p** is a prime number and **a** is any integer not divisible by p, then: $$a^{p-1} \equiv 1 \pmod{p}$$ **Alternative form:** For any integer a and prime p: $$a^p \equiv a \pmod{p}$$ ## Worked Example **Find the remainder when 7^222 is divided by 11.** **Solution:** - p = 11 (prime) and a = 7 (not divisible by 11) - By Fermat's Little Theorem: $7^{10} \equiv 1 \pmod{11}$ Now we rewrite the exponent: - $222 = 10 \times 22 + 2$ Therefore: $$7^{222} = 7^{10 \times 22 + 2} = (7^{10})^{22} \cdot 7^2 \equiv 1^{22} \cdot 49 \equiv 49 \pmod{11}$$ Since $49 = 4 \times 11 + 5$: $$7^{222} \equiv 5 \pmod{11}$$ **Answer:** The remainder is **5**.