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.

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

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

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:

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$

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

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

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.

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.

Worked Example: Negate $\forall n \in \mathbb{Z}^+, \; \exists p \mathrm{ prime}, \; p \gt n$

Step 1: Identify the structure, it is $\forall n, \; \exists p, \; P(n,p)$ where $P(n,p)$ is ”$p$ is prime and $p \gt n$.”

Step 2: Negate, $\exists n \in \mathbb{Z}^+, \; \forall p \mathrm{ prime}, \; \neg(p \gt n)$

Step 3: Simplify, $\exists n \in \mathbb{Z}^+, \; \forall p \mathrm{ prime}, \; p \le n$

Reading: “There exists a positive integer $n$ such that every prime $p$ satisfies $p \le n$.” This is false (there are infinitely many primes), so the original statement is true.

---

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.

Exercise: Prove that the product of two odd numbers is odd.

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

$a \cdot b = (2m+1)(2n+1) = 4mn + 2m + 2n + 1 = 2(2mn + m + n) + 1$

Since $2mn + m + n \in \mathbb{Z}$ The product is of the form $2k + 1$ Hence odd.

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…”).

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.

Exercise: Prove that $\sqrt{3}$ is irrational.

Assume $\sqrt{3} = \frac{a}{b}$ in lowest terms. Then $a^2 = 3b^2$ So $a^2$ is divisible by 3. By The lemma (if $3 \mid a^2$ Then $3 \mid a$), write $a = 3k$. Then $9k^2 = 3b^2$ So $b^2 = 3k^2$ Hence $3 \mid b^2$ So $3 \mid b$. Both $a$ and $b$ are divisible by 3, contradicting lowest terms.

The supporting lemma “if $p \mid a^2$ for prime $p$ Then $p \mid a$” follows from the Fundamental Theorem of Arithmetic: if $p$ appears in the prime factorization of $a^2$ It must appear in the factorization of $a$.

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.

Exercise: Prove that if $3n + 2$ is odd, then $n$ is odd (by contrapositive).

Contrapositive: If $n$ is even, then $3n + 2$ is even.

Assume $n$ is even, so $n = 2k$ for some $k \in \mathbb{Z}$.

$3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1)$

Since $3k + 1 \in \mathbb{Z}$, $3n + 2$ is even. By contrapositive, if $3n + 2$ is odd, then $n$ is odd.

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

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

Exercise: Prove by induction that $1 + 3 + 5 + \cdots + (2n-1) = n^2$ for all $n \ge 1$.

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

Base case ($n = 1$): LHS $= 1$ RHS $= 1$. True.

Inductive hypothesis: Assume $P(k)$: $1 + 3 + \cdots + (2k-1) = k^2$.

Inductive step: $1 + 3 + \cdots + (2k-1) + (2(k+1)-1) = k^2 + (2k + 1) = k^2 + 2k + 1 = (k+1)^2$.

By induction, $P(n)$ holds for all $n \ge 1$.

Exercise: Prove by induction that $2^n \gt n$ for all $n \ge 1$.

Let $P(n)$: $2^n \gt n$.

Base case ($n = 1$): $2^1 = 2 \gt 1$. True.

Inductive hypothesis: Assume $2^k \gt k$ for some $k \ge 1$.

Inductive step: $2^{k+1} = 2 \cdot 2^k \gt 2k$ (by IH, since $2^k \gt k$ and multiplying by 2).

Now, $2k = k + k \ge k + 1$ for $k \ge 1$. Therefore $2^{k+1} \gt k + 1$.

By induction, $P(n)$ holds for all $n \ge 1$.

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

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.

Exercise: Prove that every amount of postage $\ge 4$ cents can be formed using 4-cent and 5-cent stamps.

Let $P(n)$: “Postage of $n$ cents can be formed using 4-cent and 5-cent stamps.”

Base cases: $P(4)$: one 4-cent stamp. $P(5)$: one 5-cent stamp. $P(6)$: cannot, wait, this needs Checking. $P(7)$: cannot either. Let me reconsider.

Actually, we need $P(8)$: two 4-cent stamps. $P(9)$: one 4-cent + one 5-cent. $P(10)$: two 5-cent Stamps. $P(11)$: … Hmm, $P(12)$: three 4-cent stamps. $P(13)$: two 4-cent + one 5-cent. $P(14)$: One 4-cent + two 5-cent. $P(15)$: three 5-cent stamps.

Let us use base cases $P(12)$, $P(13)$, $P(14)$, $P(15)$. Strong inductive hypothesis: assume $P(j)$ for all $12 \le j \le k$ Where $k \ge 15$.

For $P(k+1)$: note that $(k+1) - 4 = k - 3 \ge 12$ (since $k \ge 15$). By strong IH, $P(k-3)$ holds, Meaning we can form $(k-3)$ cents. Adding one 4-cent stamp gives $(k-3) + 4 = k+1$ cents.

By strong induction, $P(n)$ holds for all $n \ge 12$. But we should verify the smaller cases: $P(4)$ through $P(11)$. We find $P(4)$, $P(5)$, $P(8)$, P(9)$$P(10) hold, but P(6)$$P(7)$$P(11) Do not. So the correct statement is: all postage $n \ge 8$ except $n = 11$. Or: all $n \ge 12$.

The cleanest formulation: all $n \ge 12$ can be formed. Base cases $P(12)$ through $P(15)$. Inductive step as above.

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

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

Exercise: Disprove: "For all positive integers $a$ and $b$$\gcd(a+b, a-b) = \gcd(a, b)$."

Take a = 3$$b = 1. Then $\gcd(3+1, 3-1) = \gcd(4, 2) = 2$ But $\gcd(3, 1) = 1$. Since $2 \ne 1$ The statement is false.

---

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$

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$

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$

Exercise: Prove that $\log_3{5}$ is irrational.

Assume $\log_3{5} = \frac{p}{q}$ in lowest terms, so $3^p = 5^q$. The LHS has only prime factor 3; The RHS has only prime factor 5. By uniqueness of prime factorization, this is impossible unless $p = q = 0$ Contradicting $p \ge 1$. Hence $\log_3{5}$ is irrational.

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.

Exercise: Prove $\sum_{i=1}^{n} i^3 = \left(\frac{n(n+1)}{2}\right)^2$ by induction.

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

Base case ($n = 1$): LHS $= 1$ RHS $= \left(\frac{1 \cdot 2}{2}\right)^2 = 1$. True.

Inductive hypothesis: Assume $P(k)$ holds.

Inductive step:

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

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

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$

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.

Exercise: Prove the AM-GM inequality for three variables: $\frac{a+b+c}{3} \ge \sqrt[3]{abc}$ for $a, b, c \ge 0$.

Apply two-variable AM-GM twice. First, $\frac{a+b}{2} \ge \sqrt{ab}$. Let $m = \frac{a+b}{2}$. Then:

$\frac{m + c}{2} \ge \sqrt{mc} \ge \sqrt{\sqrt{ab} \cdot c} = (abc)^{1/4}$

Wait, that gives us $\frac{\frac{a+b}{2} + c}{2} \ge (abc)^{1/4}$ I.e., $\frac{a+b+2c}{4} \ge (abc)^{1/4}$.

That is not quite right for three-variable AM-GM. A cleaner approach: let $a = x^3$, $b = y^3$ $c = z^3$ with $x, y, z \ge 0$. We need $\frac{x^3 + y^3 + z^3}{3} \ge xyz$.

Consider $x^3 + y^3 + z^3 - 3xyz = \frac{1}{2}(x+y+z)[(x-y)^2 + (y-z)^2 + (z-x)^2] \ge 0$.

Since $x+y+z \ge 0$ and squares are non-negative, $x^3 + y^3 + z^3 \ge 3xyz$. Dividing by 3 and substituting back gives the result.

---

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$

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

Therefore $n \mid [(a+c) - (b+d)]$ So $a+c \equiv b+d \pmod{n}$. $\blacksquare$

Proof of property 3:

$a = b + kn$ and $c = d + ln$ for some $k, l \in \mathbb{Z}$.

$ac = (b + kn)(d + ln) = bd + bln + dkn + kln^2 = bd + n(bl + dk + kln)$.

Therefore $n \mid (ac - bd)$ So $ac \equiv bd \pmod{n}$. $\blacksquare$

Worked Example: Find the last two digits of $7^{100}$.

We need $7^{100} \pmod{100}$.

First, find $7^{100} \pmod{4}$: $7 \equiv 3 \equiv -1 \pmod{4}$ So $7^{100} \equiv (-1)^{100} = 1 \pmod{4}$.

Next, find $7^{100} \pmod{25}$: By Euler’s theorem (or Fermat’s Little Theorem since 25 is a prime Power and $\gcd(7, 25) = 1$), $\phi(25) = 20$ So $7^{20} \equiv 1 \pmod{25}$ Hence $7^{100} = (7^{20})^5 \equiv 1^5 = 1 \pmod{25}$.

We need $x$ such that $x \equiv 1 \pmod{4}$ and $x \equiv 1 \pmod{25}$. By CRT, $x \equiv 1 \pmod{100}$.

The last two digits are 01.

Theorem (Fermat’s Little Theorem): If $p$ is prime and $\gcd(a, p) = 1$ Then:

$$a^{p-1} \equiv 1 \pmod{p}$$

Equivalently, for any integer $a$ and prime $p$: $a^p \equiv a \pmod{p}$.

Proof sketch (using the fact that $\{a, 2a, 3a, \ldots, (p-1)a\}$ is a permutation of $\{1, 2, \ldots, p-1\}$ modulo $p$):

Consider the product $1 \cdot 2 \cdot 3 \cdots (p-1) = (p-1)!$.

Modulo $p$ The numbers $a, 2a, 3a, \ldots, (p-1)a$ are all nonzero and pairwise non-congruent Modulo $p$ (since $ja \equiv ka \pmod{p}$ implies $p \mid (j-k)a$ And since $p \nmid a$ We get $p \mid (j-k)$ Which means $j \equiv k \pmod{p}$ And since $1 \le j, k \le p-1$ We get $j = k$).

Therefore $\{a, 2a, \ldots, (p-1)a\}$ is a complete residue system modulo $p$ excluding 0, so:

$$a \cdot 2a \cdot 3a \cdots (p-1)a \equiv (p-1)! \pmod{p}$$ $$a^{p-1} \cdot (p-1)! \equiv (p-1)! \pmod{p}$$

Since $p \nmid (p-1)!$ (Wilson’s theorem tells us $(p-1)! \equiv -1 \pmod{p}$), we can divide both sides by $(p-1)!$ modulo $p$:

$$a^{p-1} \equiv 1 \pmod{p} \quad \blacksquare$$

Worked Example, Find $2^{100} \pmod{13}$:

Since 13 is prime and $\gcd(2, 13) = 1$ By Fermat: $2^{12} \equiv 1 \pmod{13}$.

$100 = 8 \cdot 12 + 4$ So $2^{100} = (2^{12})^8 \cdot 2^4 \equiv 1^8 \cdot 16 \equiv 16 \equiv 3 \pmod{13}$.

Exercise: Find $3^{50} \pmod{11}$.

By Fermat: $3^{10} \equiv 1 \pmod{11}$.

$50 = 5 \cdot 10$ So $3^{50} = (3^{10})^5 \equiv 1^5 = 1 \pmod{11}$.

Answer: $3^{50} \equiv 1 \pmod{11}$.

Theorem: Every integer $n \ge 2$ can be expressed uniquely (up to order of factors) as a product Of primes:

$$n = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}$$

Where $p_1 \lt p_2 \lt \cdots \lt p_k$ are primes and $a_i \ge 1$.

Existence was proved in Section 2.4.2 using strong induction. Here we sketch uniqueness.

Uniqueness …/1-number-and-algebra/3_proof-and-logic (sketch):

Suppose $n$ has two prime factorizations:

$$n = p_1 p_2 \cdots p_r = q_1 q_2 \cdots q_s$$

Where all $p_i, q_j$ are primes. Since $p_1 \mid n = q_1 q_2 \cdots q_s$ By Euclid’s lemma ($p \mid ab$ and $p$ prime implies $p \mid a$ or $p \mid b$), $p_1$ divides some $q_j$.

Since $q_j$ is prime and $p_1$ is prime with $p_1 \mid q_j$ We must have $p_1 = q_j$. Cancel this factor and repeat. By induction, the factorizations are identical. $\blacksquare$

Definition: $\gcd(a, b)$ is the greatest common divisor of $a$ and $b$, the largest positive Integer dividing both.

Definition: $\mathrm{lcm}(a, b)$ is the least common multiple, the smallest positive integer That both $a$ and $b$ divide.

Key relationship:

$$\gcd(a, b) \cdot \mathrm{lcm}(a, b) = |ab|$$

Proof (using prime factorizations):

Let $a = \prod p_i^{\alpha_i}$ and $b = \prod p_i^{\beta_i}$ (with $\alpha_i, \beta_i \ge 0$ Padding with zeros where needed).

$\gcd(a, b) = \prod p_i^{\min(\alpha_i, \beta_i)}$

$\mathrm{lcm}(a, b) = \prod p_i^{\max(\alpha_i, \beta_i)}$

$\gcd(a,b) \cdot \mathrm{lcm}(a,b) = \prod p_i^{\min(\alpha_i, \beta_i) + \max(\alpha_i, \beta_i)} = \prod p_i^{\alpha_i + \beta_i} = ab$. $\blacksquare$

Bezout’s Identity: For integers $a, b$ (not both zero), there exist integers $x, y$ such that:

$$\gcd(a, b) = ax + by$$

This is proved constructively by the Euclidean algorithm (reversing the steps).

Theorem: The Euclidean algorithm correctly computes $\gcd(a, b)$.

Algorithm: For $a \ge b \ge 0$:

$a = bq_1 + r_1, \quad 0 \le r_1 \lt b$ $b = r_1 q_2 + r_2, \quad 0 \le r_2 \lt r_1$

$$r_1 = r_2 q_3 + r_3, \quad 0 \le r_3 \lt r_2$$ $$\vdots$$

$r_{n-2} = r_{n-1} q_n + r_n, \quad 0 \le r_n \lt r_{n-1}$ $r_{n-1} = r_n q_{n+1} + 0$

The algorithm terminates with $\gcd(a, b) = r_n$.

Proof of correctness:

Claim 1: The remainders form a strictly decreasing sequence of non-negative integers: $b \gt r_1 \gt r_2 \gt \cdots \ge 0$. This follows from the division algorithm: each remainder is Strictly less than the previous divisor.

Claim 2: The algorithm terminates. Since the remainders are non-negative integers and strictly Decrease, the process must eventually reach remainder 0 (by the well-ordering principle).

Claim 3: $\gcd(a, b) = \gcd(b, r_1) = \gcd(r_1, r_2) = \cdots = \gcd(r_{n-1}, r_n)$. This Follows from the key lemma: $\gcd(a, b) = \gcd(b, a - bq)$ for any integer $q$.

Proof of the key lemma: if $d \mid a$ and $d \mid b$ Then $d \mid (a - bq)$. Conversely, if $d \mid b$ and $d \mid (a - bq)$ Then $d \mid (a - bq + bq) = a$. So $d$ divides both $a$ and $b$ If and only if $d$ divides both $b$ and $a - bq$. Therefore $\gcd(a, b) = \gcd(b, a - bq)$.

Claim 4: $\gcd(r_{n-1}, r_n) = r_n$. Since $r_n \mid r_{n-1}$ (the last step is $r_{n-1} = r_n q_{n+1}$), the GCD is $r_n$.

Combining claims: $\gcd(a, b) = r_n$. $\blacksquare$

Worked Example: Compute $\gcd(252, 105)$ and express it as a linear combination.

$252 = 105 \cdot 2 + 42$ $105 = 42 \cdot 2 + 21$ $42 = 21 \cdot 2 + 0$

So $\gcd(252, 105) = 21$.

Back-substitution to find Bezout coefficients:

$21 = 105 - 42 \cdot 2$

$42 = 252 - 105 \cdot 2$

$21 = 105 - (252 - 105 \cdot 2) \cdot 2 = 105 - 252 \cdot 2 + 105 \cdot 4 = 105 \cdot 5 - 252 \cdot 2$

So $\gcd(252, 105) = 21 = 5 \cdot 105 + (-2) \cdot 252$.

---

Circular reasoning occurs when you implicitly assume what you are trying to prove.

Example of circular reasoning:

“Prove that $\sqrt{2}$ is irrational.”

Bad …/1-number-and-algebra/3_proof-and-logic: “Since $\sqrt{2}$ is irrational, it cannot be written as $\frac{a}{b}$. Therefore $\sqrt{2}$ is irrational.”

The conclusion ($\sqrt{2}$ is irrational) appears in the hypothesis. This proves nothing.

How to avoid: Check that every step of your …/1-number-and-algebra/3_proof-and-logic relies only on axioms, definitions, and Previously established theorems, never on the statement you are proving.

Related to circular reasoning, this occurs when you “work backwards” from the conclusion without checking reversibility.

Example:

“Prove: If $x^2 = 4$ Then $x = 2$.”

Bad …/1-number-and-algebra/3_proof-and-logic: $x^2 = 4$ So $x = \sqrt{4} = 2$. Done.

This is wrong because $x = -2$ also satisfies $x^2 = 4$. The step $x = \sqrt{4}$ implicitly assumes $x \ge 0$.

The statement itself is false: $x^2 = 4$ does not imply $x = 2$. The correct implication is $x^2 = 4 \implies x = 2$ or $x = -2$.

The negation of $P \implies Q$ is NOT $P \implies \neg Q$.

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

Reasoning: $P \implies Q$ is logically equivalent to $\neg P \vee Q$ (check the truth table). So:

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

Worked Example:

Negate: “If it rains, the ground gets wet.”

Correct negation: “It rains AND the ground does NOT get wet.” (The premise holds but the conclusion Fails.)

Incorrect negation: “If it rains, the ground does not get wet.” (This is a different implication Entirely.)

The pitfall: Skipping the base case or proving the wrong base case.

Example:

“Prove: $n = n + 1$ for all $n \ge 1$.”

Bad …/1-number-and-algebra/3_proof-and-logic: Assume $k = k + 1$. Then $k + 1 = (k + 1) + 1 = k + 2$. So $k + 1 = k + 2$ I.e., $k + 1 = (k+1) + 1$. QED.

This ”…/1-number-and-algebra/3_proof-and-logic” never checks the base case. The statement $1 = 1 + 1 = 2$ is false, so the base case Fails.

Another example: When using strong induction with a recursive definition like the Fibonacci Sequence, you may need MULTIPLE base cases. Proving the induction step from $P(k)$ and $P(k-1)$ to $P(k+1)$ requires both $P(1)$ and $P(2)$ as base cases.

Worked Example: Prove $F_n \le 2^n$ for all $n \ge 1$ Where $F_n$ is the $n$-th Fibonacci number.

Let $P(n)$: $F_n \le 2^n$.

Base cases: $F_1 = 1 \le 2 = 2^1$. True. $F_2 = 1 \le 4 = 2^2$. True. We need TWO base cases because the recurrence $F_{k+1} = F_k + F_{k-1}$ references two previous terms.

Strong inductive hypothesis: Assume $F_j \le 2^j$ for all $1 \le j \le k$ Where $k \ge 2$.

Inductive step:

$F_{k+1} = F_k + F_{k-1} \le 2^k + 2^{k-1} = 2^{k-1}(2 + 1) = 3 \cdot 2^{k-1}$

Now, $3 \cdot 2^{k-1} \le 4 \cdot 2^{k-1} = 2^{k+1}$ since $3 \le 4$.

Therefore $F_{k+1} \le 2^{k+1}$. By strong induction, $P(n)$ holds for all $n \ge 1$.

If we had only checked $P(1)$ and tried to use weak induction, the inductive step from $P(k)$ alone would not suffice because $F_{k+1}$ depends on $F_{k-1}$ as well.

Weak induction assumes $P(k)$ and proves $P(k+1)$.

Strong induction assumes $P(1), P(2), \ldots, P(k)$ and proves $P(k+1)$.

Common mistake: Using weak induction when you need strong induction. If $P(k+1)$ depends on $P(k-1)$ or earlier, weak induction’s hypothesis is insufficient.

Common mistake (reverse): Always using strong induction “to be safe.” While not logically wrong, This is unnecessary and makes …/1-number-and-algebra/3_proof-and-logics harder to read. Use weak induction unless the structure Of the problem requires strong induction.

A true implication does NOT guarantee a true converse.

Example: “If a number is prime, then it is positive.” True (for integers). Converse: “If a Number is positive, then it is prime.” False ($4$ is positive but not prime).

The implication $P \implies Q$ is true whenever $P$ is false, regardless of $Q$.

Example: “If $1 = 0$ Then the moon is made of cheese.” This is TRUE (vacuously), because the Premise "$1 = 0$" is false.

Practical consequence: To disprove $P \implies Q$ You must show $P$ is true AND $Q$ is false. Showing $P$ is false does NOT disprove the implication.

---

Comprehensive Exercise Set

1. Prove that $\sqrt{6}$ is irrational.

2. Prove that the product of any three consecutive integers is divisible by 6.

3. Prove by induction that $\sum_{i=0}^{n} 2^i = 2^{n+1} - 1$ for all $n \ge 0$.

4. Prove that if $n^2$ is divisible by 3, then $n$ is divisible by 3.

5. Disprove: “For all real numbers $x$, $x^2 \gt x$.”

6. Negate: “For every real number $x$ There exists a real number $y$ such that $x + y = 0$.”

7. Prove that there is no largest prime number.

8. Prove that $\log_5{7}$ is irrational.

9. Find $\gcd(372, 84)$ using the Euclidean algorithm, and express it as a linear combination.

10. Prove that if $a \equiv b \pmod{m}$ and $n \mid m$ Then $a \equiv b \pmod{n}$.

Answers to Selected Exercises

Exercise 1: Assume $\sqrt{6} = \frac{a}{b}$ in lowest terms. Then $a^2 = 6b^2$ So $a^2$ is even (divisible by 2), hence $a$ is even. Write $a = 2k$. Then $4k^2 = 6b^2$ So $2k^2 = 3b^2$. This Means $3b^2$ is even, so $b^2$ is even, so $b$ is even. Both $a$ and $b$ are even, contradicting Lowest terms.

Exercise 2: Among any three consecutive integers $n, n+1, n+2$: one is divisible by 3 (since one Of $n, n+1, n+2$ is a multiple of 3), and at least one is even (among any two consecutive integers, One is even, and we have three). Since 2 and 3 are coprime, the product is divisible by $2 \cdot 3 = 6$.

Exercise 4: By contrapositive. If $3 \nmid n$ Then $n \equiv 1 \pmod{3}$ or $n \equiv 2 \pmod{3}$. If $n \equiv 1$ Then $n^2 \equiv 1 \pmod{3}$. If $n \equiv 2$ Then $n^2 \equiv 4 \equiv 1 \pmod{3}$. In either case $n^2 \not\equiv 0 \pmod{3}$ So $3 \nmid n^2$.

Exercise 5: Counterexample: $x = 0.5$. Then $x^2 = 0.25 \not\gt 0.5$. Also $x = 0$: $0^2 = 0 \not\gt 0$.

Exercise 6: $\exists x \in \mathbb{R}, \; \forall y \in \mathbb{R}, \; x + y \ne 0$.

Exercise 10: $a \equiv b \pmod{m}$ means $m \mid (a-b)$. Since $n \mid m$ and $m \mid (a-b)$ By Transitivity of divisibility, $n \mid (a-b)$. Therefore $a \equiv b \pmod{n}$.

---

Example 1: Logarithm laws

Solve $\log_3(x + 1) + \log_3(x - 1) = 2$.

Solution:

$$\log_3[(x+1)(x-1)] = 2$$ $$(x+1)(x-1) = 3^2 = 9$$

$x^2 - 1 = 9 \implies x^2 = 10 \implies x = \sqrt{10}$ (since $x > 1$)

• Proof by induction: verify base case, assume $P(k)$, derive $P(k+1)$
• Proof by contradiction: assume the negation, derive an impossibility
• Necessary condition ($\implies$) vs sufficient condition ($\impliedby$) vs biconditional ($\iff$)
• Logical equivalence verified by truth tables; De Morgan’s laws for negation
• Counterexample disproves a universal statement

• Number And Algebra
• Number and Algebra
• Complex Numbers