Mathematics

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

RSA Algorithm Rivest-Shamir-Aldeman Algorithm an asymmetric cryptography algorithm utilizes public and private generated from large prime numbers used to encrypt and decrypt data. The public key consists of two numbers where one number is a multiplication of two prime numbers. The private key is also derived from the same two prime numbers meaning if the public key primes are compromised, then so is the private key. Φ Φ(Phi) counts the number of numbers that are less than or equal to n and only share the factor of 1 with n Geeks for Geeks example: Geek For Geeks: RSA Algorithm Cryptography...

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