What is a counterexample with no working?

State the value and show it fails the claim; an unjustified number earns nothing.

Find (35, 14) by the Euclidean algorithm. [2 marks]

SQA AH style: Euclidean algorithm-style practice: Use the Euclidean algorithm to find (56, 15) and express it as 56m + 15n.

56 = 3× 15 + 11; 15 = 1× 11 + 4; 11 = 2× 4 + 3; 4 = 1× 3 + 1; 3 = 3× 1 + 0, so = 1 (2 marks). Back-substitute: 1 = 4 - 1× 3 = 4 - (11 - 2× 4) = 3× 4 - 11 = 3(15 - 11) - 11 = 3× 15 - 4× 11 = 3× 15 - 4(56 - 3× 15) = 15× 15 - 4× 56 (1 mark). So 1 = 56(-4) + 15(15), giving m = -4, n = 15 (1 mark). Markers reward the division chain, the gcd, and the back-substitution to a linear combination.

ScotlandMathsSyllabus dot point

How do you prove a mathematical statement directly, by contradiction or by contrapositive, and how do you use the Euclidean algorithm?

Construct proofs using direct proof, proof by contradiction and proof by contrapositive, disprove a conjecture by counterexample, and use the Euclidean algorithm to find the highest common factor and express it as a linear combination.

A focused answer to the SQA Advanced Higher Mathematics number theory and methods of proof content, covering direct proof, proof by contradiction, proof by contrapositive, disproof by counterexample, the fundamental theorem of arithmetic, and the Euclidean algorithm for the highest common factor and its linear combination.

Generated by Claude Opus 4.812 min answerUpdated 2026-06-14

Reviewed by: AI editorial process; not yet individually human-reviewed

Have a quick question? Jump to the Q&A page

Jump to a section

What this dot point is asking
Direct proof
Proof by contradiction and contrapositive
Disproof by counterexample
The Euclidean algorithm
Try this

What this dot point is asking

The SQA wants you to write rigorous proofs using the three main techniques, direct proof, proof by contradiction and proof by contrapositive, to disprove a false claim with a counterexample, and to use the Euclidean algorithm to find a highest common factor and express it as a linear combination.

Direct proof

A direct proof moves from what you are given to what you must show, using precise definitions. To prove a statement about even or odd numbers, for instance, write an even number as $2k$ and an odd number as $2k + 1$ and manipulate algebraically.

Proof by contradiction and contrapositive

These two indirect methods are the SQA's favourites for statements that resist a direct attack. Contradiction assumes the negation and forces an absurdity. Contrapositive swaps and negates the implication, which is logically equivalent but often easier to prove.

Disproof by counterexample

A claim of the form "for all $n$ , ..." is false the moment one case fails. To disprove it you need exhibit only a single counterexample, with the arithmetic shown.

The Euclidean algorithm

The Euclidean algorithm finds the highest common factor of two integers by repeated division: replace the larger number by the remainder until the remainder is zero, and the last non-zero remainder is the gcd. Reversing the chain expresses the gcd as an integer combination of the originals, a result underpinned by the fundamental theorem of arithmetic that every integer factorises uniquely into primes.

Find

\gcd(48, 18)

by the Euclidean algorithm

We want the highest common factor of $48$ and $18$ , and we want to express it as an integer combination of the two numbers.

Step 1: Apply repeated division with remainder

At each stage, divide the larger number by the smaller and record the remainder. We keep replacing the pair with the smaller number and the new remainder until the remainder reaches zero.

48 = 2\times 18 + 12

18 = 1\times 12 + 6

12 = 2\times 6 + 0

Step 2: Read off the gcd

The algorithm terminates when the remainder is zero. The last non-zero remainder is the highest common factor, because it divides all previous remainders and hence both original numbers.

\gcd(48, 18) = 6

Step 3: Back-substitute to express the gcd as a linear combination

Work backwards through the division equations, substituting each remainder in turn. This is the reverse of the algorithm, used to write the gcd as $48m + 18n$ for integers $m$ and $n$ .

6 = 18 - 1\times 12

= 18 - 1\times (48 - 2\times 18)

= 3\times 18 - 1\times 48

Final answer: $\gcd(48, 18) = 6 = 48(-1) + 18(3)$ , so $m = -1$ , $n = 3$ .

Try this

Q1. Disprove: $n^2 + n + 41$ is prime for every positive integer $n$ . [2 marks]

Cue. At $n = 41$ the expression is $41^2 + 41 + 41 = 41(41 + 2)$ , divisible by $41$ , so not prime.

Q2. Find $\gcd(35, 14)$ by the Euclidean algorithm. [2 marks]

Cue. $35 = 2\times 14 + 7$ ; $14 = 2\times 7 + 0$ ; gcd $= 7$ .

Exam-style practice questions

Practice questions written in the style of SQA exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.

AH style: contradiction4 marksProve by contradiction that

\sqrt{2}

is irrational.

Show worked answer →

Assume the opposite: $\sqrt{2} = \dfrac{a}{b}$ in lowest terms, so $a$ and $b$ share no common factor (1 mark).

Then $a^2 = 2b^2$ , so $a^2$ is even, hence $a$ is even; write $a = 2c$ , giving $4c^2 = 2b^2$ , so $b^2 = 2c^2$ and $b$ is even (2 marks).

Both $a$ and $b$ are even, contradicting the assumption that the fraction was in lowest terms. Therefore $\sqrt{2}$ is irrational (1 mark). Markers reward the assumption, the deductions that $a$ and $b$ are even, the contradiction, and the conclusion.

AH style: Euclidean algorithm4 marksUse the Euclidean algorithm to find

\gcd(56, 15)

and express it as

56m + 15n

Show worked answer →

$56 = 3\times 15 + 11$ ; $15 = 1\times 11 + 4$ ; $11 = 2\times 4 + 3$ ; $4 = 1\times 3 + 1$ ; $3 = 3\times 1 + 0$ , so $\gcd = 1$ (2 marks).

Back-substitute: $1 = 4 - 1\times 3 = 4 - (11 - 2\times 4) = 3\times 4 - 11 = 3(15 - 11) - 11 = 3\times 15 - 4\times 11 = 3\times 15 - 4(56 - 3\times 15) = 15\times 15 - 4\times 56$ (1 mark).

So $1 = 56(-4) + 15(15)$ , giving $m = -4$ , $n = 15$ (1 mark). Markers reward the division chain, the gcd, and the back-substitution to a linear combination.

Related dot points

Sources & how we know this

SQA Advanced Higher Mathematics Course Specification — SQA (2019)