Finite Mathematics 2: Modular Arithmetic, Linear Congruences, Conditional Probability, and Bayes' Rule

Comprehensive vocabulary flashcards covering modular arithmetic, linear congruences, conditional probability, and Bayes' Rule.

Linear Congruence

A congruence equation in one unknown variable of the form $ax \equiv b \pmod m$, where $a$, $b$, and $m$ are integers, $m$ is a positive modulus, and $x$ is the unknown.

Solvability Condition for Linear Congruences

The theorem stating that the linear congruence $ax \equiv b \pmod m$ has a solution if and only if $\gcd(a, m)$ divides $b$ (written as $\gcd(a, m) \mid b$).

Number of Incongruent Solutions

When a linear congruence $ax \equiv b \pmod m$ is solvable, the number of distinct solutions modulo $m$ is exactly $d = \gcd(a, m)$.

Modular Inverse

An integer denoted $a^{-1}$ satisfying $a \cdot a^{-1} \equiv 1 \pmod m$, which exists if and only if $\gcd(a, m) = 1$.

Extended Euclidean Algorithm

An algorithm that expresses the greatest common divisor of two integers as a linear combination of the form $1 = ax + my$ when $\gcd(a, m) = 1$, which serves to determine the modular inverse of $a$ modulo $m$.

Reduction Method (Linear Congruences)

A solution technique used when $d = \gcd(a, m) > 1$ and $d \mid b$, where the coefficient $a$, constant term $b$, and modulus $m$ are each divided by $d$ to form the reduced congruence $\frac{a}{d}x \equiv \frac{b}{d} \pmod{\frac{m}{d}}$.

Incongruent Solution

A solution to a modular congruence that is distinct and not equivalent to any other solution under the modulus $m$, taken from the complete residue set $\{0, 1, 2, \dots, m - 1\}$.

Congruence Modulo $m$

A mathematical relationship where two integers $a$ and $b$ satisfy $a \equiv b \pmod m$ if and only if their difference $(a - b)$ is divisible by $m$ (written $m \mid (a - b)$), or equivalently, when they leave the same remainder upon division by $m$.

Modulo Operation

An operation, written $a \bmod m$, that returns the unique non-negative remainder $r$ when an integer $a$ is divided by a positive integer $m$, where $0 \le r < m$.

Equivalence Class (Remainder Family)

A subset of integers that share the same remainder when divided by a fixed positive integer modulus $m$, behaving identically under modular arithmetic operations.

Reflexive Property of Congruence

The property stating that every integer is congruent to itself modulo $m$, written $a \equiv a \pmod m$, justified because $m \mid (a - a)$ since $a - a = 0$.

Symmetric Property of Congruence

The property stating that if $a \equiv b \pmod m$, then $b \equiv a \pmod m$, justified because if $m \mid (a - b)$, then $m$ also divides the negative $-(a - b) = b - a$.

Transitive Property of Congruence

The property stating that if $a \equiv b \pmod m$ and $b \equiv c \pmod m$, then $a \equiv c \pmod m$, justified because $m \mid ((a - b) + (b - c))$, which equals $m \mid (a - c)$.

Preservation of Congruence

The algebraic principle that modular congruence is preserved under addition ($a + c \equiv b + d \pmod m$), subtraction ($a - c \equiv b - d \pmod m$), and multiplication ($a \cdot c \equiv b \cdot d \pmod m$).

Repeated Squaring

A computational method for evaluating large powers of integers modulo $m$ by breaking down the exponent into powers of 2, squaring the base step-by-step, and reducing modulo $m$ after each multiplication.

Cyclic System

A repeating system whose counts or states return to the initial value after a fixed period or modulus, such as hours on a clock ($\pmod{12}$) or days of the week ($\pmod 7$).

Conditional Probability

The probability that event $A$ occurs given that event $B$ has already occurred, denoted $P(A|B)$ and read as "the probability of $A$ given $B$".

Formula for Conditional Probability (Count Form)

The formula $P(A|B) = \frac{n(A \cap B)}{n(B)}$, which calculates conditional probability by counting the outcomes in the intersection relative to the restricted sample space $B$.

Formula for Conditional Probability (Probability Form)

The ratio $P(A|B) = \frac{P(A \cap B)}{P(B)}$, valid whenever the probability of the conditioning event satisfies $P(B) \neq 0$.

Restricted Sample Space

The subset of outcomes that replaces the universal sample space $S$ in conditional probability calculations when an event $B$ is known to have already occurred.

Independent Events (Conditional Probability Definition)

Two events $A$ and $B$ such that knowing $B$ has occurred provides no information about $A$, defined by the relationship $P(A|B) = P(A)$.

Bayes' Rule

A theorem used to reverse a conditional probability to find the posterior probability of a cause given an observed result: $P(A|E) = \frac{P(A) \cdot P(E|A)}{P(E)}$.

Prior Probability

The initial probability $P(A)$ assigned to a cause or hypothesis before observing any new evidence or experimental outcome.

Likelihood (Bayesian)

The conditional probability $P(E|A)$ of observing an outcome or evidence $E$ given that a specific cause or hypothesis $A$ is true.

Posterior Probability

The updated conditional probability $P(A|E)$ of a hypothesis or cause $A$ occurring given that evidence $E$ has been observed.

Law of Total Probability

The rule used to compute the total probability of evidence $E$ across all mutually exclusive causes, forming the denominator of Bayes' Rule: $P(E) = \sum_{i} P(A_i) \cdot P(E|A_i)$.

Forward Reasoning

The probabilistic process of determining the probability of a result given a known cause, expressed by the likelihood $P(\text{result} \mid \text{cause})$.

Backward Reasoning

The inferential process enabled by Bayes' Rule that deduces which underlying cause produced an observed outcome, expressed by the posterior probability $P(\text{cause} \mid \text{result})$.