Number Theory

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

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

Integer Division Integer division is a division operation that falls under number theory, a branch of math that is concerned with studying the properties of integers. In integer division, both the inputs and the output are integers resulting in being able to find an integer quotient and an integer remainder given two other integers. Divides For 2 integers $x$ and $y$, if there is an integer $k$ such that $y=kx$, then $x$ divides, $y$ is a multiple of $x$, $x$ is a factor/divisor of $y$....