Math

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)✅

Multiplicative Inverse Modulo The multiplicative inverse of $x \mod y$ is a number $n ∈ Z+$ such that $xn\mod y=1$ Finding the Multiplicative Inverse Modulo: Given $x$ & $y$, to find the multiplicative inverse, $n$ of $x mod y$ you must find: $$xn \mod y = 1$$ $$or$$ $$xn ≡ 1 (mod\ y)$$ Substitute values of n to find congruence: x * A1 ≡ B1 !≡ 1 (mod 33) x * A2 ≡ B2 !...

Finding the ones digit of large exponents There is a trick to finding the ones place digit of a large exponentiated number. This trick involves finding the values of the small powers to find a pattern. Steps to finding the ones digit: Let A = n^x Find n^1, n^2, n^3, n^4,...,n^y Such that the values begin to repeat themselves in a pattern. Note: The ones digit of n^1 = the ones digit of n^y Use modulo arithmetic to find the remainder z z = x%y Ones digit of n^x = The ones digit n^z Example: Find Ones digit of 3^902 x = 902 3^1 = 3 | 3 3^2 = 9 | 9 3^3 = 27 | 7 3^4 = 81 | 1 Ones digit 3^4 = Ones digit 3^1 y = 4 z = 902 % 4 = 2 The ones digit of 3^902 = The ones digit 3^2 Ones digit = 9 Finding the first digits of large exponents There is a trick to finding the first few digits of a large exponentiated number....

Greatest Common Divisor GCD The largest number $n ∈ Z+$ that is a factor of both nonzero $x$ & $y$ such that both $n | x$ & $n | y$ are true. Relatively Prime Two numbers $x$ and $y$ are said to be relatively prime if and only if their GCD is 1. In other terms: $$∄ n ∈ Z+ > 1$$ where both $n | x$ and $n | y$ are true....

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$....

Recurrence Relations Definition Recurrence Relation Rule 1 An equation that expresses the value of $An$ in terms of at least one previous term in a sequence. Recurrence Relation Rule 2 Initial conditions must be specified to determine the value of the first term in the sequence. Example: $An = A(n-1)+ 2* A(n-2)$ for $n>= 2$ where $A0=2, A1=5$ Arithmetic Sequences Given a sequence $A0, A1, A2, A3, …$, there may be an arithmetic sequence $An$ that satisfies the recurrence relation....

Prime & Composite Relationship: If $p ∈ Z+$ and $p > 1$, then $p$ is either prime or composite. Prime Numbers: If $p ∈ Z+$ and $p > 1$, then $p$ is prime if the the only factors of p are $1$ & $p$. Composite Numbers: If $p ∈ Z+$ and $p > 1$, then $p$ is composite if $p$ if $∃ a ∈ Z+$ such that $a | p$ & $1 < a < p$....