Fact from number theory Theorem. Let m be prime. For any zE Z such that z≠0, there exists a unique z∈Zmn such that z·x1=1(modm) Example: m=7 123456 145236 o 2001 by Charles E Leiserson Introduction to Algorithms Day 12 L8. 13© 2001 by Charles E. Leiserson Introduction to Algorithms Day 12 L8.13 Fact from number theory Theorem. Let m be prime. For any z ∈ Zm such that z ≠ 0, there exists a unique z–1 ∈ Zm such that z · z–1 ≡ 1 (mod m). Example: m = 7. z z–1 1 2 3 4 5 6 1 4 5 2 3 6