Unit 1 - Number and Algebra
Required Prior Knowledge
Questions
Expand
a) \(\left(2x+1\right)\left(3x-4\right)\)
b) \(\left(2x+1\right)^{2}\)
Factorise
c) \(15n+12n^{2}\)
d) \(4\left(x+1\right)+6\left(x+1\right)^{2}\)
Solutions
Get Ready
Questions
For each of the following statements decide whether they are always true, sometimes true or never true.
a) Tomorrow is Thursday
b) There are 35 days in this month
c) If you double a natural number you get an even number
d) If you add 1 to a natural number you get an odd number
e) Christmas Day is on a Wednesday
f) There is a total of 61 days in April and May
g) The angles in a quadrilateral add up to \(360^{\circ}\)
h) If a quadrilateral has 4 equal sides then it is a square
i) \(x=3x+6\)
j) \(x+y=y+x\)
k) \(x=3x\)
l) \(x-y=y-x\)
m) \(6+2x=2x+1\)
n) \(2\left(3x+1\right)=4x+6\)
o) \(2\left(3x+1\right)=6x+2\)
p) \(x^{2}=9\)
q) \(x+x=2x\)
r) \(3^{x}=10\)
s) \(\frac{4}{x}=0\)
Solutions
-
a) Sometimes True
b) Never True
c) Always true
d) Sometimes True
e) Sometimes True
f) Always True
g) Always True
h) Sometimes True (could be a rhombus!)
i) Sometimes True (when \(x=-3\))
j) Always True
k) Sometimes True (when \(x=0\)0
l) Sometimes True
m) Never True
n) Sometimes True
o) Always True
p) Sometimes True
q) Always True
r) Sometimes True
s) Never True
Notes
-
A proof is a logical argument that establishes the truth of a mathematical statement or proposition. It consists of a series of deductive steps that demonstrate the validity of the statement based on previously established definitions, axioms, and theorems. Proofs ensure that conclusions drawn in mathematics are founded on rigorously justified reasoning, making them essential for the integrity and coherence of mathematical theory.
-
Proving mathematical results is important for several reasons. First, proofs create a solid foundation of certainty. Mathematicians use careful reasoning to establish truths that are accepted universally, without needing specific experiments or examples. This precision is essential in mathematics.
Second, proofs improve understanding. By creating a proof, mathematicians engage with the concepts, clarifying their own comprehension and helping others grasp complex ideas. This process often reveals connections between different mathematical areas.
Moreover, proving results can lead to new discoveries. The act of proving encourages further exploration and innovation, resulting in new findings and areas of study. In applied mathematics, proofs ensure that theoretical models and methods will work reliably in real-world applications, which is crucial in fields like engineering and physics.
Lastly, proofs drive the development of mathematics. They form the core of mathematical theory, allowing knowledge to build over time. Each accepted proof lays the groundwork for future exploration and advancements.
In short, proving mathematical results is essential for establishing certainty, enhancing understanding, fostering innovation, ensuring reliability in practice, and supporting the growth of mathematical knowledge.
-
Mathematical proof is different from proof in other subjects because it has a strict and formal structure. A proof in maths is a logical explanation that shows a statement is true based on accepted rules, definitions, and previous findings. It relies on deductive reasoning, where conclusions follow clearly from established facts.
In contrast, proofs in subjects like the humanities or social sciences often use qualitative evidence, context, and interpretation. For example, in history, proof may involve analyzing primary sources and combining various viewpoints to form an argument. This method allows for some personal interpretation and does not always follow universal rules.
Moreover, mathematical proofs seek absolute certainty and result in conclusions that are universally accepted in mathematics. In other fields, proofs can be more tentative and may change as new evidence comes in. In disciplines like science, proof is often temporary and can evolve, while a mathematical proof remains constant once it is established. For example, for many centuries scientists had proof that the Earth was flat, or that the Earth was the centre of the solar system. Even the proofs of Newton's Laws of Motion were eventually superseded by Einstein's Theory of Relativity.
In summary, mathematical proofs focus on certainty and logic, while proofs in other fields are more interpretive and flexible.
There are many types of proof used in Mathematics. The main ones, which all appear in this course, are listed below.
-
Starting with a statement or some information (a hypothesis) we show through logical deductions that something else is true.
Usually this involves some algebraic manipulation to get from one form to another.
We often use the symbols \(\therefore\) meaning 'therefore' and \(\Rightarrow\) meaning 'implies'.
-
In some proofs there are finite different cases that need to be shown. We can break a proof down by analysing each individual case. We ‘exhaust’ all the possible cases to show that the original conjecture is true.
E.G. Prove there are fewer square numbers than prime numbers in the positive integers less than 50.
-
If \(A\Rightarrow B\) then \(\lnot B\Rightarrow \lnot A\). This is known as the contrapositive.
E.g. Consider the statement: “If Diego is at school then he is learning.”
The contrapositive is: "If Diego is NOT learning then he is NOT at school"
A statement and its contrapositive are equivalent, so proving one proves the other.
-
To prove something is always true can be very difficult.
But to show something is NOT true, only requires a single counter example.
-
When there are infinitely many cases, exhaustion is not possible.
Assume we know that if a statement is true for a given case, it is also true for the next case. Then we need only to show it is true for the first case to show it is true for all cases
-
To prove something, we show that the opposite is not possible.
To prove “not all cars are blue”, assume “all cars are blue”.
But we know that there are cars which are red, which contradicts our assumption. If our assumption is not true, then the opposite must be true. That is, “not all cars are blue”.
The structure of good direct algebraic proof is important to maintain the rigorous, logical approach.
We start by stating any assumptions we make before beginning the proof. This is often turning some worded description into algebra.
Then we perform a series of algebraic manipulation steps to show that two things are equivalent. The best layout for this step is: $$\begin{align}LHS &= … \\ &= … \\ &= … \\ &= RHS\end{align}$$
Finally we must state our final conclusion that the proof has shown.
We usually end a proof with one of two things to show it is finished:
QED stands for "Quod Erat Demonstrandum," a Latin phrase meaning "which was to be demonstrated." It marks the conclusion of mathematical proofs, indicating that the statement has been conclusively shown to be true;
The symbol \(\square\) is also sometimes used to indicate that a proof has been completed.
Examples and Your Turns
Example
Prove that $$\left(a+b\right)^{2}\equiv a^{2}+2ab+b^{2}$$
Solution $$\begin{align}\left(a+b\right)^{2}&\equiv \left(a+b\right)\left(a+b\right) \\ &\equiv a^{2}+ab+ab+b^{2} \\ &\equiv a^{2}+2ab+b^{2}\end{align}$$Q.E.D.
Your Turn
Prove that $$\left(a+2b\right)^{2}\equiv a^{2}+4ab+4b^{2}$$
-
$$\begin{align}\left(a+2b\right)^{2}&\equiv \left(a+2b\right)\left(a+2b\right) \\ &\equiv a^{2}+2ab+2ab+4b^{2} \\ &\equiv a^{2}+4ab+4b^{2}\end{align}$$Q.E.D.
Your Turn
Prove that $$a^{2}-b^{2}\equiv \left(a+b\right)\left(a-b\right)$$
-
$$\begin{align}\left(a+b\right)\left(a-b\right)&\equiv a^{2}+ab-ab+b^{2} \\ &\equiv a^{2}-b^{2}\end{align}$$Q.E.D.
Your Turn
Prove that $$\left(3x+2\right)\left(x-5\right)\left(x+7\right)\equiv 3x^{3}+8x^{2}-101x-70$$
-
$$\begin{align}\left(3x+2\right)\left(x-5\right)\left(x+7\right)&\equiv \left(3x+2\right)\left(x^{2}+2x-35\right) \\ &\equiv 3x^{3}+6x^{2}-105x+2x^{2}+4x-70 \\ &\equiv 3x^{3}+8x^{2}-101x-70\end{align}$$Q.E.D.
Your Turn
Prove that $$\left(a-b\right)^{3}\equiv a^{3}-3a^{2}b+3ab^{2}-b^{3}$$
-
$$\begin{align}\left(a-b\right)^{3}&\equiv \left(a-b\right)\left(a-b\right)\left(a-b\right) \\ &\equiv \left(a-b\right)\left(a^{2}-2ab+b^{2}\right) \\ &\equiv a^{3}-2a^{2}b+ab^{2}-a^{2}b+2ab^{2}-b^{3} \\ & \equiv a^{3}-3a^{2}b+3ab^{2}-b^{3}\end{align}$$Q.E.D.
Your Turn
Prove that $$\frac{1}{2}\left(n+1\right)\left(n+2\right)-\frac{1}{2}n\left(n+1\right)\equiv n+1$$
-
$$\begin{align}\frac{1}{2}\left(n+1\right)\left(n+2\right)-\frac{1}{2}n\left(n+1\right)&\equiv \frac{1}{2}\left(n^{2}+3n+2\right)-\frac{1}{2}\left(n^{2}+n\right) \\ &\equiv \frac{1}{2}n^{2}+\frac{3}{2}n+1-\frac{1}{2}n^{2}-\frac{1}{2}n \\ &\equiv n+1\end{align}$$Q.E.D.
Your Turn
Prove that $$\left(n+4\right)^{2}-\left(3n+4\right)\equiv \left(n+1\right)\left(n+4\right)+8$$
-
$$\begin{align}\left(n+4\right)^{2}-\left(3n+4\right)&\equiv n^{2}+8n+16-3n-4 \\ &\equiv n^{2}+5n+12 \\ &\equiv n^{2}+5n+4+8 \\ & \equiv \left(n+1\right)\left(n+4\right)+8\end{align}$$Q.E.D.
Your Turn
Prove that $$\left(n+3\right)^{2}-\left(3n+5\right)\equiv \left(n+1\right)\left(n+2\right)+2$$
-
$$\begin{align}\left(n+3\right)^{2}-\left(3n+5\right)&\equiv n^{2}+6n+9-3n-5 \\ &\equiv n^{2}+3n+4 \\ &\equiv n^{2}+3n+2+2 \\ & \equiv \left(n+1\right)\left(n+2\right)+2\end{align}$$Q.E.D.
Your Turn
What is wrong with the following ‘proof’?
$$a=b \\ a^{2}=ab \\ a^{2}-b^{2}=ab-b^{2} \\ \left(a-b\right)\left(a+b\right)=b\left(a-b\right) \\ a+b=b \\ 2b=b \\ 2=1$$
Example
Prove that \(\left(3n+1\right)^{2}-\left(3n-1\right)^{2}\) is a multiple of \(6\) for all \(n\in \mathbb{Z}\).
Solution
$$\begin{align}\left(3n+1\right)^{2}-\left(3n-1\right)^{2} & \equiv \left(9n^{2}+6n+1\right)-\left(9n^{2}-6n+1\right) \\ & \equiv 9n^{2}+6n+1-9n^{2}+6n-1 \\ & \equiv 12n \\ & \equiv 6\left(2n\right)\end{align}$$ Since this is of the form \(6k\) where \(k\in\mathbb{Z}\), it is a multiple of \(6\).
Q.E.D.
Your Turn
Prove that \(\left(4n+1\right)^{2}-\left(4n-1\right)^{2}\) is a multiple of \(8\) for all \(n\in \mathbb{Z}^{+}\).
-
$$\begin{align}\left(4n+1\right)^{2}-\left(4n-1\right)^{2} & \equiv \left(16n^{2}+8n+1\right)-\left(16n^{2}-8n+1\right) \\ & \equiv 16n^{2}+8n+1-16n^{2}+8n-1 \\ & \equiv 16n \\ & \equiv 8\left(2n\right)\end{align}$$ Since this is of the form \(8k\) where \(k\in\mathbb{Z}\), it is a multiple of \(8\).
Q.E.D.
Your Turn
Prove that \(\left(5n+1\right)^{2}-\left(5n-1\right)^{2}\) is a multiple of both \(4\) and \(5\) for all \(n\in \mathbb{Z}^{+}\).
-
$$\begin{align}\left(5n+1\right)^{2}-\left(5n-1\right)^{2} & \equiv \left(25n^{2}+10n+1\right)-\left(25n^{2}-10n+1\right) \\ & \equiv 25n^{2}+10n+1-25n^{2}+10n-1 \\ & \equiv 10n \\ & \equiv 4\left(5n\right) \\ & \equiv 5\left(4n\right)\end{align}$$ Since this is of the form \(4k\) where \(k\in\mathbb{Z}\) and \(5m\) where \(m\in\mathbb{Z}\), it is a multiple of both \(4\) and \(5\).
Q.E.D.
Your Turn
Prove that \(\left(2n+1\right)^{2}-\left(2n+1\right)\) is even for all \(n\in \mathbb{Z}^{+}\).
-
$$\begin{align}\left(2n+1\right)^{2}-\left(2n+1\right) & \equiv \left(4n^{2}+4n+1\right)-\left(2n+1\right) \\ & \equiv 4n^{2}+2n \\ & \equiv 2\left(2n^{2}+n\right)\end{align}$$ Since this is of the form \(2k\) where \(k\in\mathbb{Z}\), it is a multiple of \(2\) and hence even.
Q.E.D.
Notes
Given that \(m\) and \(n\) are integers, complete the following by adding expressions for each description in words:
Examples and Your Turns
Example
Prove that the product of two odd numbers is odd.
Solution
Let \(m,n\in\mathbb{Z}\).
\(\therefore 2m+1\) and \(2n+1\) are both odd numbers.
$$\begin{align}\Rightarrow\left(2m+1\right)\left(2n+1\right) & \equiv 4mn+2m+2n+1 \\ & \equiv 2\left(2mn+m+n\right)+1\end{align}$$
Since the product of two numbers is of the form \(2k+1\) for some \(k\in\mathbb{Z}\), it is an odd number.
Q.E.D.
Your Turn
Prove that the product of two even numbers is even.
-
Let \(m,n\in\mathbb{Z}\).
\(\therefore 2m\) and \(2n\) are both even numbers.
$$\begin{align}\Rightarrow\left(2m\right)\left(2n\right) & \equiv 4mn \\ & \equiv 2\left(2mn\right)\end{align}$$
Since the product of two numbers is of the form \(2k\) for some \(k\in\mathbb{Z}\), it is an even number.
Q.E.D.
Your Turn
Prove that the product of an odd number and an even number is even.
-
Let \(m,n\in\mathbb{Z}\).
\(\therefore 2m\) is an even number and \(2n+1\) is an odd number.
$$\begin{align}\Rightarrow\left(2m\right)\left(2n+1\right) & \equiv 4mn+2m \\ & \equiv 2\left(2mn+m\right)\end{align}$$
Since the product of two numbers is of the form \(2k\) for some \(k\in\mathbb{Z}\), it is an even number.
Q.E.D.
Your Turn
Prove that the sum of three consecutive integers is a multiple of 3.
-
Let \(m\in\mathbb{Z}\).
\(\therefore m-1,m\) and \(m+1\) are three consecutive numbers.
$$\Rightarrow\left(m-1\right)+m+\left(m+1\right) \equiv 3m $$
Since the sum is of the form \(3k\) for some \(k\in\mathbb{Z}\), it is a multiple of 3.
Q.E.D.
Your Turn
Prove that the sum of three consecutive powers of \(2\) is a multiple of seven.
-
Let \(m\in\mathbb{Z}\).
\(\therefore 2^{m},2^{m+1}\) and \(2^{m+2}\) are consecutive powers of 2.
$$\begin{align}\Rightarrow2^{m}+2n^{m+1} +2^{m+2}& \equiv 2^{m}+2\times 2^{m}+2^{2}\times 2^{m} \\ & \equiv 2^{m}\left(1+2+4\right) \\ &\equiv 7\times 2^{m}\end{align}$$
Since the sum is of the form \(7k\) for some \(k\in\mathbb{Z}\), it is a multiple of \(7\).
Q.E.D.
Your Turn
Prove that the sum of four consecutive integers is even.
-
Let \(m\in\mathbb{Z}\).
\(\therefore m,m+1,m+2\) and \(m+3\) are four consecutive numbers.
$$\begin{align}\Rightarrow m+\left(m+1\right)+\left(m+2\right)+\left(m+3\right) & \equiv 4m+6 \\ & \equiv 2\left(2m+3\right)\end{align}$$
Since the sum is of the form \(2k\) for some \(k\in\mathbb{Z}\), it is an even number.
Q.E.D.
Your Turn
Prove that the product of three consecutive numbers is a multiple of six.
Your Turn
Prove that the sum of two consecutive square numbers is odd.
-
Let \(m\in\mathbb{Z}\).
\(\therefore m^{2}\) and \(\left(m+1\right)^{2}\) are consecutive square numbers.
$$\begin{align}\Rightarrow m^{2}+\left(m+1\right)^{2} & \equiv m^{2}+m^{2}+2m+1 \\ & \equiv 2m^{2}+2m+1 \\ & \equiv 2\left(m^{2}+m\right)+1\end{align}$$
Since the product of two numbers is of the form \(2k\) for some \(k\in\mathbb{Z}\), it is an even number.
Q.E.D.
Your Turn
Prove that the sum of the squares of two consecutive odd numbers is \(2\) more than a multiple of \(8\).
-
Let \(m\in\mathbb{Z}\).
\(\therefore 2m-1\) and \(2m+1\) are consecutive odd numbers.
$$\begin{align}\Rightarrow\left(2m-1\right)^{2}+\left(2m+1\right)^{2} & \equiv 4m^{2}-4m+1+4m^{2}+4m+1 \\ & \equiv 8m^{2}+2 \\ & \equiv 8\left(m^{2}\right)+2\end{align}$$
Since the sum is of the form \(8k +2\) for some \(k\in\mathbb{Z}\), it is two more than a multiple of \(8\).
Q.E.D.
Notes (HL)
Proof by exhaustion is when a proof of a statement is broken down into several cases, each of which is analysed and proven.
An important step, and sometimes the most difficult, in a proof by exhaustion is to prove that you have indeed covered all possible cases and there are no ‘gaps’ left.
Examples and Your Turns (HL)
Example
Prove that $$n^{5}-n\equiv \left(n-1\right)n\left(n+1\right)\left(n^{2}+1\right)$$ is divisible by \(5\) for all \(n\in\mathbb{Z}\).
Solution
All integers can be written in one of the following forms: $$\begin{matrix} 5k & 5k+1 & 5k+2 & 5k+3 & 5k+4 \end{matrix}$$These cover all possible cases, so we shall examine each in turn.
For brevity, let \(N=n^{5}-n=\left(n-1\right)n\left(n+1\right)\left(n^{2}+1\right)\).
Case 1 (\(n=5k\))
If \(n=5k\) then the factor \(n\) of \(N\) is divisible by \(5\). Hence, \(N\) is divisible by 5.
Case 2 (\(n=5k+1\))
If \(n=5+1\) then the factor $$\left(n-1\right)=5k+1-1=5k$$ of \(N\) is divisible by \(5\). Hence, \(N\) is divisible by 5.
Case 3 (\(n=5k+2\))
If \(n=5k+2\) then the factor $$\begin{align}\left(n^{2}+1\right)&=\left(5k+2\right)^{2}+1 \\ & = 25k^{2}+20k+5 \\ & = 5\left(5k^{2}+4k+1\right)\end{align}$$ of \(N\) is divisible by \(5\). Hence, \(N\) is divisible by 5.
Case 4 (\(n=5k+3\))
If \(n=5k+3\) then the factor $$\begin{align}\left(n^{2}+1\right)&=\left(5k+3\right)^{2}+1 \\ & = 25k^{2}+30k+10 \\ & = 5\left(5k^{2}+6k+2\right)\end{align}$$ of \(N\) is divisible by \(5\). Hence, \(N\) is divisible by 5.
Case 5 (\(n=5k+4\))
If \(n=5k+4\) then the factor $$\left(n+1\right)=5k+4+1=5k+5=5\left(k+1\right)$$ of \(N\) is divisible by \(5\). Hence, \(N\) is divisible by 5.
In all possible cases,\(N\) is divisible by \(5\).
So \(n^{5}-n\) is divisible by \(5\) for all \(n\in\mathbb{Z}\).
Q.E.D.
Your Turn
Prove that all square numbers end in \(0, 1, 4, 5, 6\) or \(9\).
-
All integers can be written in the form \(10k+n\) where \(k\in\mathbb{Z}\) and \(n=0,1,2,3,...,9\).
For all integers we have that $$\begin{align}\left(10k+n\right)^{2}&=100k^{2}+20k+n^{2}\\&=10\left(10k^{2}+2k\right)+n^{2}\end{align}$$and thus the final digit is always just the final digit of \(n^{2}\) (since the other parts are a multiple of \(10\), their digits part is always \(0\)).
Hence we only need consider the last digit of \(n^{2}\) for \(n=0,1,2,3,...,9\). The squares of these numbers are shown below. $$\begin{matrix}1^{2}&=&1\\2^{2}&=&4\\3^{2}&=&9\\4^{2}&=&16\\5^{2}&=&25\\6^{2}&=&=36\\7^{2}&=&49\\8^{2}&=&64\\9^{2}&=&81\end{matrix}$$In all cases, the last digits is one of \(0,1,4,5,6\) or \(9\).
Q.E.D.
Your Turn
Prove that the number \(3n^{2}+n+14\) is even \(\forall n\in\mathbb{Z}\) (HINT - consider when \(n\) is even and odd).
-
The value of \(n\) must be either even or odd, since it is an integer.
Case 1 (\(n\) is even)
Let \(n=2k\) for some \(k\in\mathbb{Z}\). $$\begin{align}3\left(2k\right)^{2}+\left(2k\right)+14&=12k^{2}+2k+14\\&=2\left(6k^{2}+k+7\right)\end{align}$$Since \(k\in\mathbb{Z}\), we have that \(6k^{2}+k+7\) is an integer, and so the result is even.Case 2 (\(n\) is odd)
Let \(n=2k+1\) for some \(k\in\mathbb{Z}\). $$\begin{align}3\left(2k+1\right)^{2}+\left(2k+1\right)+14&=12k^{2}+12k+3+2k+1+14\\&=12k^{2}+14k+18\\&=2\left(6k^{2}+7k+9\right)\end{align}$$Since \(k\in\mathbb{Z}\), we have that \(6k^{2}+7k+9\) is an integer, and so the result is even.Since in both cases \(3n^{2}+n+14\) is even, it is even for all \(n\in\mathbb{Z}\).
Q.E.D.
Notes (HL)
The contrapositive of a statement is made by reversing and negating both parts. For a statement like "If P, then Q" (P → Q), the contrapositive is "If not Q, then not P" (¬Q → ¬P).
A statement and its contrapositive are equivalent. If one is true, then so is the other. For example, "If it rains, then the ground is wet" has the contrapositive "If the ground is not wet, then it is not raining." Understanding the contrapositive is important for mathematical proofs as sometimes it is easier to prove the contrapositive than the original statement.
For each of these below, state the contrapositive
a) If a person is a teacher, then that person is clever
b) If a tree is a Christmas Tree, then it has a star on top
c) All referees make the correct decision all the time
d) If the sum of the squares of the shorter sides of a triangle equals the square of the longer side, then the triangle is a right-angled triangle
e) If a biscuit has chocolate, then it is delicious
-
a) If a person is not clever, then they are not a teacher
b) If a tree does not have a star on top, then it is not a Christmas Tree
c) If an incorrect decision is made, it was not made by a referee
d) If a triangle is not right-angled, then the sum of the squares of the shorter sides is not equal to the square of the longer side
e) If a biscuit is not delicious, then it does not have chocolate
Examples and Your Turns (HL)
Example
Let \(n\in\mathbb{Z}\). Prove that if \(n^{2}-4n+5\) is even then \(n\) is odd.
Solution
The contrapositive is: If \(n\) is even (an integer that is not odd), then \(n^{2}-4n+5\) is odd (an integer that is not even).
Suppose \(n\) is even, then \(n=2k\) for some \(k\in\mathbb{Z}\).
Hence $$\begin{align}n^{2}-4n+5 & = \left(2k\right)^{2}-4\left(2k\right)+5 \\ & = 4k^{2}-8k+5 \\ & = 2\left(2k^{2}-4k+2\right)+1\end{align}$$which is of the form \(2m+1\) and thus is odd.
Thus the contrapositive is true, and so the original statement must also be true.
Q.E.D.
Your Turn
Let \(n\) be a positive integer. Prove that if \(n\) has remainder \(2\) when divided by \(3\) (that is \(n\equiv 2 \text{ mod }3\)), then \(n\) is not a perfect square.
-
The contrapositive is: If \(n\) is a perfect square, then \(n\) does not have remainder \(2\) when divided by \(3\).
Suppose that \(n\) is a perfect square. That is \(n=k^{2}\) for some \(k\in\mathbb{N}\).
All integers \(k\) can be written in one the three forms:$$\begin{matrix}3q&,&3q+1&,&3q+2\end{matrix}$$
We shall consider each case in turn.
Case 1 (\(k=3q\))
If \(k=3q\) then $$\begin{align}n&=\left(3q\right)^{2}\\&=9q^{2}\\&=3\left(3q^{2}\right)\end{align}$$which is a multiple of \(3\).
Thus \(n\) does not have remainder \(2\) when divided by \(3\).Case 2 (\(k=3q+1\))
If \(k=3q+1\) then $$\begin{align}n&=\left(3q+1\right)^{2}\\&=9q^{2}+6q+1\\&=3\left(3q^{2}+2q\right)+1\end{align}$$which is one more than a multiple of \(3\).
Thus \(n\) does not have remainder \(2\) when divided by \(3\).Case 3 (\(k=3q+2\))
If \(k=3q+2\) then $$\begin{align}n&=\left(3q+2\right)^{2}\\&=9q^{2}+12q+4\\&=3\left(3q^{2}+4q+1\right)+1\end{align}$$which is one more than a multiple of \(3\).
Thus \(n\) does not have remainder \(2\) when divided by \(3\).So in all three possible cases, when \(n\) is a perfect square, it does not have remainder \(2\) when divided by \(3\).
Since the contrapositive is true, the original statement must also be true.
Q.E.D.
Your Turn
Prove that all prime numbers, except for \(2\) and \(3\), are one more than or one less than a multiple of \(6\). (hint - all numbers must be of the form \(6n+k\) for some values of \(k\))
-
The contrapositive is: all positive integers that are not one more or one less than a multiple of \(6\) are not prime, except \(2\) and \(3\).
We can write any positive integer in on of the following six forms:$$6k, 6k+1, 6k+2, 6k+3, 6k+4, 6k+5$$
We shall consider each case in turn.
Case 1 (\(6k\))
If our positive integer is of the form \(6k=2\left(3k\right)\) then it is a multiple of \(2\), and hence not prime.Case 2 (\(6k+1\))
If our positive integer is of the form \(6k+1)\) then there are no obvious factors and it COULD be prime.Case 3 (\(6k+2\))
If our positive integer is of the form \(6k+2=2\left(3k+1\right)\) then it is a multiple of \(2\), and hence not prime.Case 4 (\(6k+3\))
If our positive integer is of the form \(6k+3=3\left(2k+1\right)\) then it is a multiple of \(3\), and hence not prime.Case 5 (\(6k+4\))
If our positive integer is of the form \(6k+4=2\left(3k+2\right)\) then it is a multiple of \(2\), and hence not prime.Case 6 (\(6k+5\))
If our positive integer is of the form \(6k+5)\) then there are no obvious factors and it COULD be prime.After considering these cases we can say that all positive integers that are NOT one more or one less than a multiple of \(6\) are NOT prime.
Since the contrapositive is true, the original statement must also be true.
Notes (HL)
Disproof by counterexample is a method used to show that a general statement or conjecture is false. This is achieved by providing a specific example that contradicts the claim.
For instance, consider the statement: "All prime numbers are odd." To disprove this, one can present the number 2 as a counterexample. Since 2 is a prime number and is not odd (it is even), this singular instance is sufficient to invalidate the statement.
The effectiveness of disproof by counterexample lies in its simplicity; one example alone is enough to demonstrate that a universal claim does not hold in all cases. This technique is commonly employed in various fields of mathematics to challenge assertions, refine theories, and advance understanding.
Examples and Your Turns (HL)
Example
Show by counter example that \(n^{2}+n+41\) with \(n\in \mathbb{N}\) does not always generate a prime number.
Your Turn
Show by counter example that \(n^{2}+n+11\) with \(n\in \mathbb{N}\) does not always generate a prime number.
Your Turn
Show by counter example that \(2^{n}-1\) with \(n\ge 2, n\in \mathbb{N}\) does not always generate a prime number.
Your Turn
Fermat thinks all natural numbers can be written as the sum of two square numbers. Do you agree?
Key Facts
Use this applet to generate a prompt for a Key Fact that you need to know for the course. The idea is that you should KNOW these key facts in order to be able to solve problems.