Proof and Logic

This note covers IB Mathematics AA — Topic 1.4: Proof in full depth. Everything here is Examinable at both Standard Level and Higher Level, with HL extensions marked where relevant.

1. Logic Foundations

1.1 Propositions and Truth Values

A proposition is a declarative sentence that is either true or false — never both, never Neither.

“7 is prime” is a proposition (true). “Solve for x” is not a proposition. “This sentence is false” Is not a proposition (it is paradoxical).

The truth value of a proposition $P$ is denoted $\mathcal{T}(P) \in \{T, F\}$.

1.2 Logical Connectives

There are five fundamental connectives. Let $P$ and $Q$ be propositions.

Truth Tables

Negation:

Conjunction:

Disjunction (inclusive OR):

Implication:

The implication $P \implies Q$ is only false when a true premise leads to a false conclusion. This Is the single most misunderstood truth table entry in all of mathematics. When $P$ is false, the Implication is vacuously true — there is no counterexample to “whenever P holds, Q holds.”

Biconditional:

1.3 Logical Equivalence

Two compound propositions are logically equivalent (written $\equiv$) if they have identical Truth values for every possible assignment of truth values to their component propositions.

Key equivalences (Laws of Logic):

1. Commutative: $P \wedge Q \equiv Q \wedge P$And $P \vee Q \equiv Q \vee P$
2. Associative: $(P \wedge Q) \wedge R \equiv P \wedge (Q \wedge R)$And similarly for $\vee$
3. Distributive: $P \wedge (Q \vee R) \equiv (P \wedge Q) \vee (P \wedge R)$And $P \vee (Q \wedge R) \equiv (P \vee Q) \wedge (P \vee R)$
4. Identity: $P \wedge T \equiv P$And $P \vee F \equiv P$
5. Domination: $P \vee T \equiv T$And $P \wedge F \equiv F$
6. Idempotent: $P \wedge P \equiv P$And $P \vee P \equiv P$
7. Double Negation: $\neg(\neg P) \equiv P$
8. Absorption: $P \vee (P \wedge Q) \equiv P$And $P \wedge (P \vee Q) \equiv P$

1.4 De Morgan”s Laws

These are essential for negating compound statements.

$\neg(P \wedge Q) \equiv \neg P \vee \neg Q$

$\neg(P \vee Q) \equiv \neg P \wedge \neg Q$

Intuition: To negate an “and,” negate each part and switch to “or.” To negate an “or,” negate Each part and switch to “and.”

Worked Example — Negating a compound statement:

Negate: “The function $f$ is continuous and differentiable.”

Let $C$: ”$f$ is continuous.” Let $D$: ”$f$ is differentiable.” The statement is $C \wedge D$. Its Negation is $\neg C \vee \neg D$I.e., ”$f$ is either not continuous or not differentiable.”

:::info A common mistake is to negate “P and Q” as “not P and not Q.” That is wrong. The negation of ”$f$ is continuous and differentiable” is NOT ”$f$ is not continuous and not differentiable” — that Is too strong. :::

1.5 The Contrapositive

For any implication $P \implies Q$The contrapositive is $\neg Q \implies \neg P$.

Theorem: An implication and its contrapositive are logically equivalent.

$P \implies Q \equiv \neg Q \implies \neg P$

This is proved by comparing truth tables. Both are false only when $P$ is true and $Q$ is false.

Compare with two other related statements that are NOT equivalent:

• The converse of $P \implies Q$ is $Q \implies P$ (not equivalent )
• The inverse of $P \implies Q$ is $\neg P \implies \neg Q$ (not equivalent , but equivalent to the converse)

Danger: Danger Implication. Never confuse the contrapositive with the converse. Worked Example:

Statement: “If $n$ is even, then $n^2$ is even.”

Contrapositive: “If $n^2$ is odd, then $n$ is odd.”

Converse: “If $n^2$ is even, then $n$ is even.” (True in this case, but not logically guaranteed.)

Inverse: “If $n$ is odd, then $n^2$ is odd.” (Also true here, but again not guaranteed.)

1.6 Tautologies and Contradictions

A tautology is a compound proposition that is true for every possible truth assignment. A contradiction is a compound proposition that is false for every possible truth assignment.

Important tautology: $P \vee \neg P$ (Law of Excluded Middle)

Important contradiction: $P \wedge \neg P$

Another key tautology — Modus Ponens: $((P \implies Q) \wedge P) \implies Q$

This says: if you know $P \implies Q$ and you know $P$Then you can conclude $Q$. This is the Fundamental rule of direct …/1-number-and-algebra/3_proof-and-logic.

Modus Tollens: $((P \implies Q) \wedge \neg Q) \implies \neg P$

This says: if you know $P \implies Q$ and you know $\neg Q$Then you can conclude $\neg P$. This is The fundamental rule of …/1-number-and-algebra/3_proof-and-logic by contrapositive.

1.7 Quantifiers

Quantifiers let us express statements about collections of objects.

Universal quantifier ($\forall$): “For all” — the statement must hold for every element in the Domain.

$\forall x \in S, \; P(x)$

Existential quantifier ($\exists$): “There exists” — the statement must hold for at least one Element.

$\exists x \in S, \; P(x)$

Negating quantified statements:

$\neg(\forall x, \; P(x)) \equiv \exists x, \; \neg P(x)$

$\neg(\exists x, \; P(x)) \equiv \forall x, \; \neg P(x)$

To negate a universal statement, you get an existential counterexample. To negate an existential Statement, you must show it fails for every case.

Nested quantifiers require careful handling. The order matters:

$\forall x \, \exists y, \; P(x,y) \quad \mathrm{is NOT equivalent to} \quad \exists y \, \forall x, \; P(x,y)$

Worked Example — Negating a nested quantifier statement:

Negate: “For every positive real number $\varepsilon$There exists a positive real number $\delta$ Such that…”

$\neg\left(\forall \varepsilon \gt 0, \; \exists \delta \gt 0, \; P(\varepsilon, \delta)\right) \equiv \exists \varepsilon \gt 0, \; \forall \delta \gt 0, \; \neg P(\varepsilon, \delta)$

The existential becomes universal and the universal becomes existential. This is the logical Backbone of epsilon-delta definitions in analysis.

:::caution Warning Negate the predicate. The order of quantifiers does NOT change — it remains the same sequence but With each quantifier flipped. :::

2. Methods of Proof

2.1 Direct Proof

Strategy: To prove $P \implies Q$Assume $P$ is true and use logical deduction to arrive at $Q$.

This is the most straightforward method. You chain together known results, definitions, and Algebraic manipulations.

Template:

1. Assume $P$.
2. [Logical steps…]
3. Therefore $Q$.
4. Hence $P \implies Q$.

Worked Example — If $n$ is odd, then $n^2$ is odd:

Assume $n$ is odd. By definition, $n = 2k + 1$ for some $k \in \mathbb{Z}$.

$n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$

Since $2k^2 + 2k$ is an integer (sum and product of integers), let $m = 2k^2 + 2k \in \mathbb{Z}$. Then $n^2 = 2m + 1$Which is odd by definition.

Therefore, if $n$ is odd, then $n^2$ is odd.

Worked Example — The sum of two even numbers is even:

Let $a = 2m$ and $b = 2n$ for some $m, n \in \mathbb{Z}$.

$a + b = 2m + 2n = 2(m + n)$

Since $m + n \in \mathbb{Z}$We have $a + b = 2(m+n)$ is even.

2.2 Proof by Contradiction

Strategy: To prove a statement $P$Assume $\neg P$ and derive a logical contradiction (something that is always false, like $1 = 0$ or $0 \lt 0$).

Template:

1. Assume $\neg P$ (the negation of what you want to prove).
2. [Logical steps leading to a contradiction…]
3. This contradicts [known fact].
4. Therefore $\neg P$ is false, so $P$ is true.

This method is especially powerful when the statement you want to prove is a negation itself (“there Does not exist…” or “there are no…”).

:::info Info Which means $\neg P$ must be false, hence $P$ is true. It relies on the Law of Excluded Middle ($P \vee \neg P$ must be true). :::

Worked Example — $\sqrt{2}$ is irrational:

Assume $\sqrt{2}$ is rational. Then $\sqrt{2} = \frac{a}{b}$ where $a, b \in \mathbb{Z}^+$ $\gcd(a, b) = 1$ (the fraction is in lowest terms).

Squaring both sides: $2 = \frac{a^2}{b^2}$So $a^2 = 2b^2$.

Since $a^2 = 2b^2$We have $a^2$ is even. Therefore $a$ is even (by the lemma: if $a^2$ is even, Then $a$ is even — proved below).

Write $a = 2k$ for some $k \in \mathbb{Z}^+$. Substituting:

$(2k)^2 = 2b^2$So $4k^2 = 2b^2$So $b^2 = 2k^2$.

Therefore $b^2$ is even, so $b$ is even.

But now both $a$ and $b$ are even, contradicting $\gcd(a, b) = 1$.

Therefore our assumption is false, and $\sqrt{2}$ is irrational.

:::note Note Odd, then $a = 2k+1$So $a^2 = 4k^2 + 4k + 1 = 2(2k^2+2k) + 1$Which is odd. Hence if $a^2$ is Even, $a$ cannot be odd, so $a$ is even. :::

2.3 Proof by Contrapositive

Strategy: To prove $P \implies Q$Instead prove $\neg Q \implies \neg P$. Since an implication Is logically equivalent to its contrapositive, this proves the original statement.

When to use this: When the hypothesis $P$ feels “too big” or “too loose” to work with directly, But the negation of the conclusion $\neg Q$ gives you something concrete to grab.

Template:

1. We prove the contrapositive: if $\neg Q$Then $\neg P$.
2. Assume $\neg Q$.
3. [Logical steps…]
4. Therefore $\neg P$.
5. Hence $P \implies Q$.

Worked Example — If $n^2$ is even, then $n$ is even:

We prove the contrapositive: if $n$ is odd, then $n^2$ is odd.

Assume $n$ is odd. Then $n = 2k + 1$ for some $k \in \mathbb{Z}$.

$n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$

This is odd. Therefore, if $n$ is odd, $n^2$ is odd. By contrapositive, if $n^2$ is even, then $n$ Is even.

:::tip Tip ”$n^2$ even implies $n$ even” by contradiction (assume $n^2$ even and $n$ odd, derive that $n^2$ is Both even and odd). But the contrapositive …/1-number-and-algebra/3_proof-and-logic is cleaner — it is a direct …/1-number-and-algebra/3_proof-and-logic of the equivalent Statement. :::

2.4 Mathematical Induction

Induction proves statements of the form $\forall n \ge n_0, \; P(n)$Where $n_0 \in \mathbb{Z}$.

2.4.1 Standard (Weak) Induction

Template:

1. Base case: Verify $P(n_0)$ is true.
2. Inductive hypothesis: Assume $P(k)$ is true for some arbitrary $k \ge n_0$.
3. Inductive step: Using the hypothesis that $P(k)$ holds, prove that $P(k+1)$ holds.
4. Conclusion: By the Principle of Mathematical Induction, $P(n)$ is true for all $n \ge n_0$.

Worked Example — Sum formula $1 + 2 + \cdots + n = \frac{n(n+1)}{2}$:

Let $P(n)$: $1 + 2 + \cdots + n = \frac{n(n+1)}{2}$.

Base case ($n = 1$): LHS $= 1$RHS $= \frac{1 \cdot 2}{2} = 1$. So $P(1)$ is true.

Inductive hypothesis: Assume $P(k)$ is true for some $k \ge 1$I.e., $1 + 2 + \cdots + k = \frac{k(k+1)}{2}$.

Inductive step: We must show $P(k+1)$: $1 + 2 + \cdots + k + (k+1) = \frac{(k+1)(k+2)}{2}$.

Starting from the LHS:

$1 + 2 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1)$

(by the inductive hypothesis)

$= \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k + 2)}{2}$

This is exactly the RHS of $P(k+1)$. Therefore $P(k+1)$ holds.

Conclusion: By induction, $P(n)$ is true for all $n \ge 1$.

Worked Example — Sum of squares $1^2 + 2^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}$:

Let $P(n)$: $\displaystyle\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$.

Base case ($n = 1$): LHS $= 1$RHS $= \frac{1 \cdot 2 \cdot 3}{6} = 1$. True.

Inductive hypothesis: Assume $P(k)$ holds for some $k \ge 1$.

Inductive step:

$\sum_{i=1}^{k+1} i^2 = \sum_{i=1}^{k} i^2 + (k+1)^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2$

$= \frac{k(k+1)(2k+1) + 6(k+1)^2}{6}$

$= \frac{(k+1)[k(2k+1) + 6(k+1)]}{6}$

$= \frac{(k+1)[2k^2 + k + 6k + 6]}{6}$

$= \frac{(k+1)(2k^2 + 7k + 6)}{6}$

$= \frac{(k+1)(k+2)(2k+3)}{6}$

$= \frac{(k+1)((k+1)+1)(2(k+1)+1)}{6}$

This is $P(k+1)$. By induction, the formula holds for all $n \ge 1$.

2.4.2 Strong Induction

In strong induction, the inductive hypothesis assumes $P(n_0), P(n_0+1), \ldots, P(k)$ are ALL true, Not just $P(k)$.

Template:

1. Base case(s): Verify $P(n_0)$ (and possibly more base cases).
2. Inductive hypothesis: Assume $P(j)$ is true for all $n_0 \le j \le k$.
3. Inductive step: Using that $P(j)$ holds for all $j \le k$Prove $P(k+1)$.
4. Conclusion: By the Principle of Strong Induction, $P(n)$ is true for all $n \ge n_0$.

When to use strong induction: When proving $P(k+1)$ requires not just $P(k)$ but some earlier Case $P(j)$ where $j \lt k$.

:::caution Weak and strong induction are logically equivalent — anything provable by one is provable By the other. But strong induction can make certain …/1-number-and-algebra/3_proof-and-logics much more natural. Use it when the Inductive step needs to reference cases earlier than just $k$. :::

Worked Example — Every integer $n \ge 2$ is a product of primes:

Let $P(n)$: ”$n$ is a product of primes (possibly a single prime).”

Base case ($n = 2$): 2 is prime, hence a product of primes. True.

Strong inductive hypothesis: Assume $P(j)$ is true for all $2 \le j \le k$.

Inductive step for $n = k + 1$:

Case 1: $k+1$ is prime. Then it is a product of primes.

Case 2: $k+1$ is composite. Then $k+1 = ab$ where $2 \le a \le b \le k$. By the strong inductive Hypothesis, both $a$ and $b$ are products of primes. Therefore $k+1 = ab$ is a product of primes.

In either case, $P(k+1)$ holds. By strong induction, every integer $n \ge 2$ is a product of primes.

2.5 Proof by Exhaustion

Strategy: When the domain of possible cases is finite and small, prove the statement by Verifying each case individually.

This is brute-force but rigorous. It is only practical when the number of cases is manageable.

Worked Example — Show that $n^2 + n + 17$ is prime for $n = 0, 1, 2, 3, 4$:

$n = 0$: $0 + 0 + 17 = 17$ (prime) $n = 1$: $1 + 1 + 17 = 19$ (prime) $n = 2$: $4 + 2 + 17 = 23$ (prime) $n = 3$: $9 + 3 + 17 = 29$ (prime) $n = 4$: $16 + 4 + 17 = 37$ (prime)

All five cases verified. (Note: this polynomial produces primes for $n = 0$ through $n = 15$But Fails at $n = 16$ since $16^2 + 16 + 17 = 289 = 17^2$.)

2.6 Counterexamples

A single counterexample is sufficient to disprove a universal statement.

Strategy: To disprove $\forall x \in S, \; P(x)$Find one $a \in S$ such that $P(a)$ is false.

Worked Example — Disprove: “All prime numbers are odd.”

Counterexample: $2$ is prime and $2$ is even.

Worked Example — Disprove: ”$n^2 - n + 41$ is prime for all $n \in \mathbb{N}$.”

When $n = 41$: $41^2 - 41 + 41 = 41^2 = 1681$Which is composite ($41 \times 41$).

:::tip To prove a universal claim requires a general …/1-number-and-algebra/3_proof-and-logic. To disprove it requires only one Counterexample. This asymmetry is fundamental to mathematical logic. :::

3. Classical Proof Examples

3.1 $\sqrt{2}$ is Irrational (Detailed)

This …/1-number-and-algebra/3_proof-and-logic appeared in Section 2.2. Here we present it with full commentary on every logical step.

Theorem: $\sqrt{2} \notin \mathbb{Q}$.

Proof:

We proceed by contradiction.

Assume $\sqrt{2} \in \mathbb{Q}$. Then there exist coprime integers $a, b$ with $b \gt 0$ such that $\sqrt{2} = \frac{a}{b}$.

The requirement that $\gcd(a, b) = 1$ is without loss of generality: any rational number can be Expressed as a fraction in lowest terms.

Squaring: $2 = \frac{a^2}{b^2}$So $a^2 = 2b^2$. Equation (1).

From (1): $a^2$ is divisible by 2, so $a^2$ is even. By the contrapositive of “odd implies square is Odd,” $a$ is even.

Since $a$ is even, write $a = 2m$ for some integer $m$. Substituting into (1):

$(2m)^2 = 2b^2$I.e., $4m^2 = 2b^2$I.e., $b^2 = 2m^2$. Equation (2).

From (2): $b^2$ is even, so $b$ is even (same reasoning as above).

But now $a$ and $b$ are both even, meaning $\gcd(a, b) \ge 2$Contradicting $\gcd(a, b) = 1$.

This contradiction shows our assumption is false. Hence $\sqrt{2} \notin \mathbb{Q}$. $\blacksquare$

3.2 There Are Infinitely Many Primes

Theorem (Euclid): The set of prime numbers is infinite.

Proof:

We proceed by contradiction.

Assume there are only finitely many primes: $p_1, p_2, \ldots, p_n$.

Consider the number $N = p_1 p_2 \cdots p_n + 1$.

Since $N \gt 1$By the Fundamental Theorem of Arithmetic, $N$ has a prime factor $p$.

This prime $p$ must be one of $p_1, p_2, \ldots, p_n$ (since we assumed these are all the primes).

But $N = p_1 p_2 \cdots p_n + 1$And for each $p_i$:

$N \equiv 0 + 1 \equiv 1 \pmod{p_i}$

So $p_i \nmid N$ for all $i$. This contradicts that some $p_i$ divides $N$.

Therefore, there are infinitely many primes. $\blacksquare$

:::info Info Example, $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \times 509$. The …/1-number-and-algebra/3_proof-and-logic only Requires that $N$ has SOME prime factor not in the list. :::

3.3 $\log_2{3}$ is Irrational

Theorem: $\log_2{3}$ is irrational.

Proof:

We proceed by contradiction. Assume $\log_2{3}$ is rational.

Then $\log_2{3} = \frac{p}{q}$ for some coprime positive integers $p, q$ with $q \ge 1$.

This means $2^{p/q} = 3$So $2^p = 3^q$.

Since p \ge 1$$2^p is a power of 2. Its only prime factor is 2.

Since q \ge 1$$3^q is a power of 3. Its only prime factor is 3.

By the Fundamental Theorem of Arithmetic, prime factorizations are unique. The number $2^p = 3^q$ Would need to have prime factorization consisting of only 2’s AND only 3’s simultaneously. This is Impossible unless $p = q = 0$But $p \ge 1$.

Contradiction. Hence $\log_2{3}$ is irrational. $\blacksquare$

3.4 Sum Formulas

We proved these by induction in Section 2.4. Here is the complete reference:

$\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$

$\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$

$\sum_{i=1}^{n} i^3 = \frac{n^2(n+1)^2}{4} = \left(\frac{n(n+1)}{2}\right)^2$

The last identity is notable: the sum of cubes equals the square of the sum of the first $n$ Integers.

3.5 Divisibility Proofs

Theorem: If $n^2$ is even, then $n$ is even.

We proved this by contrapositive in Section 2.3. Here are additional divisibility results.

Theorem: If $a \mid b$ and $b \mid c$Then $a \mid c$ (transitivity of divisibility).

Proof:

Since $a \mid b$There exists $m \in \mathbb{Z}$ such that $b = am$. Since $b \mid c$There exists $n \in \mathbb{Z}$ such that $c = bn$.

Therefore $c = bn = (am)n = a(mn)$.

Since $mn \in \mathbb{Z}$We have $a \mid c$. $\blacksquare$

Theorem: If $d \mid a$ and $d \mid b$Then $d \mid (ax + by)$ for all $x, y \in \mathbb{Z}$.

Proof:

Since $d \mid a$Write $a = dm$ for some $m \in \mathbb{Z}$. Since $d \mid b$Write $b = dn$ for Some $n \in \mathbb{Z}$.

$ax + by = (dm)x + (dn)y = d(mx + ny)$.

Since mx + ny \in \mathbb{Z}$$d \mid (ax + by). $\blacksquare$

:::note This theorem is the foundation of the Euclidean algorithm. The expression $ax + by$ is Called a linear combination of $a$ and $b$. The greatest common divisor $\gcd(a, b)$ can always Be expressed as a linear combination of $a$ and $b$ (Bezout’s identity). :::

3.6 Inequality Proofs

AM-GM Inequality (two variables): For $a, b \ge 0$:

$\frac{a + b}{2} \ge \sqrt{ab}$

With equality if and only if $a = b$.

Proof:

Note that $(\sqrt{a} - \sqrt{b})^2 \ge 0$ for all $a, b \ge 0$.

Expanding: $a - 2\sqrt{ab} + b \ge 0$So $a + b \ge 2\sqrt{ab}$.

Dividing by 2: $\frac{a+b}{2} \ge \sqrt{ab}$. Equality holds when $\sqrt{a} = \sqrt{b}$I.e., $a = b$. $\blacksquare$

Cauchy-Schwarz Inequality (statement): For real numbers $a_1, \ldots, a_n$ and $b_1, \ldots, b_n$:

$\left(\sum_{i=1}^{n} a_i b_i\right)^2 \le \left(\sum_{i=1}^{n} a_i^2\right) \left(\sum_{i=1}^{n} b_i^2\right)$

With equality when the vectors are proportional ($a_i = \lambda b_i$ for all $i$ and some scalar $\lambda$).

The …/1-number-and-algebra/3_proof-and-logic is beyond the scope of this note but uses the fact that $\sum (a_i x + b_i)^2 \ge 0$ for All $x \in \mathbb{R}$And a quadratic in $x$ that is always non-negative must have a non-positive Discriminant.

4. Number Theory Proofs (HL Extension)

4.1 Divisibility Properties

For integers $a, b, c$ with $a \ne 0$:

Definition: $a \mid b$ (read ”$a$ divides $b$”) means there exists $k \in \mathbb{Z}$ such that $b = ak$.

Key properties:

1. $a \mid 0$ for all $a \ne 0$ (since $0 = a \cdot 0$)
2. $1 \mid b$ for all $b$ (since $b = 1 \cdot b$)
3. If $a \mid b$ and $b \mid a$Then $a = \pm b$
4. If $a \mid b$ and $a \mid c$Then $a \mid (b + c)$ and $a \mid (b - c)$

Proof of property 3:

$a \mid b$ implies $b = ma$ for some $m \in \mathbb{Z}$. $b \mid a$ implies $a = nb$ for some $n \in \mathbb{Z}$.

Substituting: $a = n(ma) = (nm)a$So $(nm - 1)a = 0$. Since $a \ne 0$We have $nm = 1$.

In integers, $nm = 1$ implies $(n, m) = (1, 1)$ or $(n, m) = (-1, -1)$.

If $m = 1$: $b = a$. If $m = -1$: $b = -a$. So $a = \pm b$. $\blacksquare$

4.2 Congruences and Modular Arithmetic

Definition: $a \equiv b \pmod{n}$ means $n \mid (a - b)$I.e., $a - b = kn$ for some $k \in \mathbb{Z}$.

Key properties of congruences:

If $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$Then:

1. $a + c \equiv b + d \pmod{n}$
2. $a - c \equiv b - d \pmod{n}$
3. $ac \equiv bd \pmod{n}$
4. $a^m \equiv b^m \pmod{n}$ for any $m \in \mathbb{Z}^+$

Proof of property 1:

$a \equiv b \pmod{n}$ means $a - b = kn$. $c \equiv d \pmod{n}$ means $c - d = ln$.

$(a+c) - (b+d) = (a-b) + (c-d) = kn + ln = (k+l)n$.