Modulo

You can use modular exponentiation to calculate the remainder of a number raised to a power. The trick to finding large exponentials is to break them down into smaller ones. Example: Given that $M^2 ≡ 51 (mod 59)$, what is $M^{12} (mod 59)$? M^12 = M^(4+8) M^12 = M^4 * M^8 M^12 = (M^2)^2 * (M^2)^3✅ M^2 ≡ 51 (mod 59) M^4 ≡ (M^2)^2 ≡ (51)^2 (mod 59) M^4 ≡ 2601 (mod 59) M^4 ≡ 5 (mod 59)✅ M^4 ≡ 5 (mod 59) M^8 ≡ (M^4)^2 ≡ (5)^2 (mod 59) M^8 ≡ 25 (mod 59)✅ M^12 = M^4 * M^8 M^12 ≡ [(5 mod 59) * (25 mod 59)] M^12 ≡ 5*25 (mod 59) M^12 ≡ 125 (mod 59) M^12 ≡ 7 (mod 59)✅

Congruence Modulo n Congruence Modulo N Let $n ∈ Z+ > 1$. Let $(x, y) ∈ Z$. Then x is congruent to y modulo n if $x \text{%} n = y \text{%} n$. This congruence is denoted as: $$x≡y(mod n)$$ Example: x mod n = y mod n x = 20, y = 10, n = 5 20 % 5 = 10 % 5 0 = 0 20 ≡ 10(mod 5) Alternate Congruence Characterization Let $n ∈ Z > 1$....