Waterloo MATH135 - Algebra for Honours Mathematics Flashcards

Question 1

Implication and Contrapositive

Accepted Answer

An implication is a conditional statement of the form $P \implies Q$. Its **contrapositive** is $
eg Q \implies 
eg P$. An implication is logically equivalent to its contrapositive ($P \implies Q \equiv 
eg Q \implies 
eg P$).

Question 2

Proof by Contradiction

Accepted Answer

To prove a statement $P$ by contradiction, assume its negation $
eg P$ is true. Through valid logical steps, derive a logical contradiction (e.g., $R \land 
eg R$). Conclude that $P$ must be true.

Question 3

Principle of Mathematical Induction (PMI)

Accepted Answer

To prove a statement $P(n)$ is true for all integers $n \ge a$:
1. **Base Case:** Show $P(a)$ is true.
2. **Inductive Step:** Assume $P(k)$ is true for an arbitrary integer $k \ge a$ (Inductive Hypothesis), then prove $P(k+1)$ is true.

Question 4

Principle of Strong Induction

Accepted Answer

To prove $P(n)$ is true for all $n \ge a$:
1. **Base Case:** Prove $P(a)$ (and any required additional base cases) is true.
2. **Inductive Step:** Assume $P(i)$ is true for all integers $a \le i \le k$ (Inductive Hypothesis), then prove $P(k+1)$ is true.

Question 5

Divisibility Definition ($a \mid b$)

Accepted Answer

For $a, b \in \mathbb{Z}$ with $a 
eq 0$, $a$ divides $b$ (written $a \mid b$) if there exists an integer $c$ such that $b = ac$. If no such integer exists, $a 
mid b$.

Question 6

Divisibility Bounds Theorem (DBT)

Accepted Answer

If $a, b \in \mathbb{Z}$ such that $a \mid b$ and $b 
eq 0$, then $|a| \le |b|$.

Question 7

Division Algorithm

Accepted Answer

For any integer $a$ and positive integer $b$, there exist unique integers $q$ (quotient) and $r$ (remainder) such that:
$a = bq + r$ where $0 \le r < b$.

Question 8

Greatest Common Divisor (GCD)

Accepted Answer

The greatest common divisor of $a, b \in \mathbb{Z}$ (not both zero), written $\gcd(a, b)$, is the unique positive integer $d$ satisfying:
1. $d \mid a$ and $d \mid b$
2. For any $c \in \mathbb{Z}$, if $c \mid a$ and $c \mid b$, then $c \le d$ (or $c \mid d$).

Question 9

Euclidean Algorithm

Accepted Answer

An efficient algorithm to compute $\gcd(a, b)$ using repeated division:
$\gcd(a, b) = \gcd(b, r)$, where $a = bq + r$ with $0 \le r < b$.
Repeat until the remainder is $0$; the last non-zero remainder is $\gcd(a, b)$.

Question 10

Bézout's Identity / Extended Euclidean Algorithm (EEA)

Accepted Answer

For any $a, b \in \mathbb{Z}$ (not both zero), there exist integers $x$ and $y$ such that:
$\gcd(a, b) = ax + by$.
The integers $x$ and $y$ are called Bézout coefficients and can be calculated using the Extended Euclidean Algorithm.

Question 11

Coprime / Relatively Prime

Accepted Answer

Two integers $a$ and $b$ are **coprime** if $\gcd(a, b) = 1$.
By Bézout's Identity, $a$ and $b$ are coprime if and only if there exist $x, y \in \mathbb{Z}$ such that $ax + by = 1$.

Question 12

Euclid's Lemma

Accepted Answer

If $p$ is a prime number and $p \mid ab$ for $a, b \in \mathbb{Z}$, then $p \mid a$ or $p \mid b$.
More generally, if $a \mid bc$ and $\gcd(a, b) = 1$, then $a \mid c$.

Question 13

Fundamental Theorem of Arithmetic (FTA)

Accepted Answer

Every integer $n > 1$ can be factored into a product of prime numbers in a way that is unique, up to the order of the prime factors:
$n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$.

Question 14

Congruence Modulo $m$

Accepted Answer

For $a, b \in \mathbb{Z}$ and $m \in \mathbb{Z}^+$, $a$ is congruent to $b$ modulo $m$ ($a \equiv b \pmod{m}$) if $m \mid (a - b)$.
Equivalently, $a$ and $b$ yield the same remainder when divided by $m$.

Question 15

Properties of Congruence

Accepted Answer

If $a \equiv b \pmod{m}$ and $c \equiv d \pmod{m}$, then:
1. $a + c \equiv b + d \pmod{m}$
2. $a - c \equiv b - d \pmod{m}$
3. $ac \equiv bd \pmod{m}$
4. $a^k \equiv b^k \pmod{m}$ for any $k \in \mathbb{Z}^+$

Question 16

Linear Congruence Theorem (LCT)

Accepted Answer

The linear congruence $ax \equiv c \pmod{m}$ has a solution if and only if $d \mid c$, where $d = \gcd(a, m)$. If a solution exists, there are exactly $d$ incongruent solutions modulo $m$.

Question 17

Modular Inverse

Accepted Answer

An integer $x$ is a modular inverse of $a$ modulo $m$ if $ax \equiv 1 \pmod{m}$.
An inverse exists if and only if $\gcd(a, m) = 1$ and is unique modulo $m$.

Question 18

Fermat's Little Theorem (FLT)

Accepted Answer

If $p$ is a prime number and $a \in \mathbb{Z}$ is not divisible by $p$, then:
$a^{p-1} \equiv 1 \pmod{p}$.
Equivalently, for any integer $a$, $a^p \equiv a \pmod{p}$.

Question 19

Complex Number Forms

Accepted Answer

A complex number $z \in \mathbb{C}$ can be represented as:
1. **Cartesian Form:** $z = x + yi$ where $x, y \in \mathbb{R}$.
2. **Polar/Exponential Form:** $z = r(\cos 	heta + i \sin 	heta) = re^{i	heta}$, where $r = |z| = \sqrt{x^2+y^2}$ and $	heta = 	ext{Arg}(z)$.

Question 20

Complex Conjugate Properties

Accepted Answer

For $z = x + yi \in \mathbb{C}$, its conjugate is $\bar{z} = x - yi$.
Properties:
1. $z \bar{z} = x^2 + y^2 = |z|^2$
2. $\overline{z + w} = \bar{z} + \bar{w}$
3. $\overline{zw} = \bar{z} \bar{w}$
4. $z + \bar{z} = 2	ext{Re}(z)$ and $z - \bar{z} = 2i	ext{Im}(z)$

Question 21

De Moivre's Theorem

Accepted Answer

For any real number $	heta$ and integer $n$:
$(\cos 	heta + i \sin 	heta)^n = \cos(n	heta) + i \sin(n	heta)$.
In exponential form: $(e^{i	heta})^n = e^{in	heta}$.

Question 22

$n$-th Roots of Unity

Accepted Answer

The solutions to $z^n = 1$ for $z \in \mathbb{C}$ are given by:
$z_k = e^{i \frac{2k\pi}{n}} = \cos\left(\frac{2k\pi}{n}\right) + i \sin\left(\frac{2k\pi}{n}\right)$
for $k = 0, 1, 2, \dots, n-1$. These points form a regular $n$-gon inscribed in the unit circle.

Waterloo MATH135 - Algebra for Honours Mathematics

Cards in this deck

Related Flashcard Sets

JLPT N2 - Upper-Intermediate Japanese Kanji, Grammar & Expressions

CompTIA Network+ (N10-008) - Networking Fundamentals & Subnetting

HSK 4 - Intermediate Chinese Vocabulary & Grammar

CompTIA Network+ (N10-008) - Networking Fundamentals & Protocols