Number Theory and Algebraic Proofs

Problem Statement

In lower high school, mathematics is mostly about calculation—finding the value of $x$. In Extension 2, mathematics shifts towards justification—proving why a statement must always be true for every possible $x$.

This introduces formal Number Theory. We stop relying on specific examples and start using algebraic definitions to describe broad categories of numbers.

• An even number is defined as $2k$ (where $k$ is an integer).
• An odd number is defined as $2k + 1$.
• A rational number is defined as $\frac{p}{q}$ (where $p$ and $q$ are integers with no common factors, and $q \neq 0$).

One of the most powerful introductory proof techniques is the Proof by Contradiction. Instead of proving a statement directly, you assume the statement is false, follow logical algebraic steps, and show that this assumption leads to an impossible conclusion (a contradiction). Since logic cannot be contradictory, your initial assumption must be wrong, meaning the original statement is true.

Consider the classic number theory theorem: "The square root of 2 is irrational."

(a) To begin a proof by contradiction, what assumption must we initially make?

(b) Write down the algebraic definition of a rational number, and set it equal to $\sqrt{2}$. What condition must be placed on the numerator and denominator?

(c) Perform algebraic manipulations to show that this leads to a contradiction regarding the evenness of the numerator and denominator.

Hints

• Part (a): The opposite of irrational is rational. Assume $\sqrt{2}$ is rational.
• Part (b): Let $\sqrt{2} = \frac{p}{q}$. The crucial condition for this proof is that the fraction must be in its simplest form. This means $p$ and $q$ share no common factors (they are coprime). If they are both even, they would share a factor of 2.
• Part (c):
  1. Square both sides to remove the square root: $2 = \frac{p^2}{q^2}$.
  2. Rearrange to make $p^2$ the subject: $p^2 = 2q^2$. What does this tell you about $p^2$?
  3. If a square is even, its base must also be even. Therefore, $p$ is even. Let $p = 2k$.
  4. Substitute $p = 2k$ back into $p^2 = 2q^2$. Simplify to find out what $q^2$ equals. What does this tell you about $q$?
  5. Compare your conclusions about $p$ and $q$ to your initial condition from part (b).

Solutions

Part (a): The Initial Assumption

1. We want to prove $\sqrt{2}$ is irrational.
2. Assume the contrary: Assume that $\sqrt{2}$ is a rational number.

Part (b): The Algebraic Definition

1. By the definition of a rational number, we can write $\sqrt{2}$ as a fraction: $\sqrt{2} = \frac{p}{q}$
2. Where $p$ and $q$ are integers, $q \neq 0$.
3. Crucial Condition: Assume that the fraction $\frac{p}{q}$ is fully simplified. This means $p$ and $q$ share no common factors (they are coprime). Specifically, they cannot both be even.

Part (c): The Algebraic Contradiction

1. Take the equation $\sqrt{2} = \frac{p}{q}$ and square both sides: $2 = \frac{p^2}{q^2}$
2. Multiply both sides by $q^2$: $2q^2 = p^2$
3. Since $p^2$ is equal to 2 multiplied by an integer ($q^2$), $p^2$ must be an even number.
4. If the square of an integer is even, the integer itself must be even. Therefore, $p$ is an even number.
5. Since $p$ is even, we can write it as $p = 2k$, where $k$ is an integer.
6. Substitute this definition of $p$ back into our equation $2q^2 = p^2$: $2q^2 = (2k)^2$ $2q^2 = 4k^2$
7. Divide both sides by 2: $q^2 = 2k^2$
8. By the exact same logic as step 3, since $q^2$ is 2 multiplied by an integer, $q^2$ must be an even number.
9. Therefore, $q$ is an even number.
10. The Contradiction: We have just proven that both $p$ and $q$ are even. This means they share a common factor of 2. However, in Part (b), we established that $\frac{p}{q}$ was fully simplified and shared no common factors.
11. Conclusion: Our logic led to an impossible contradiction. The only flaw was our initial assumption. Therefore, the assumption that $\sqrt{2}$ is rational must be false.
12. Thus, $\sqrt{2}$ is an irrational number.

Takeaways

• Definitions are Power: Algebraic proofs rely entirely on translating English sentences into rigorous algebra. Knowing the exact definition of terms like 'even', 'odd', 'rational', and 'consecutive' is the first step in any proof.
• The Power of Contradiction: Proof by contradiction is a brilliant tool when a direct proof is too difficult. It is often used to prove that things don't exist, or that numbers belong to infinite sets like irrational numbers or primes.
• The Copernican Shift: Extension 2 Mathematics marks a transition from computation to pure logic. You are no longer just solving problems; you are building the foundation of mathematics itself.

Further Readings

• HSC Proofs: https://vumaths.com/booklets/hsc-proofs/
• HSC Inequalities: https://vumaths.com/booklets/hsc-inequalities/
• HSC Polynomials: https://vumaths.com/booklets/hsc-polynomials/

Connect with me

If you enjoyed the elegant logic of this proof, check out my complete proof writing guides on Vu's Maths Hub. I break down how to structure direct, contrapositive, and contradiction proofs step-by-step. Watch me tackle difficult past paper proofs on my YouTube channel. Follow my Instagram for daily maths challenges, and subscribe to my Substack to learn how this logic underpins computer science!