8.02i–8.02k - Primes, factors and Euclid's lemma | OCR A-Level Further Mathematics A

Use prime factorisation to recognise composites and find highest common factors. Then turn common divisors into divisors of small integer combinations, prove coprimality without factorising large numbers, and apply Euclid's lemma with its essential condition.

Primes and composites

Can the numbers $3n+2$ and $5n+3$ ever share a factor greater than one, when $n$ is a positive integer? For $n=1$ they are five and eight; for $n=100$ they are $302$ and $503$ . Their sizes grow, but their common-factor question will turn out to have a one-line answer.

First be precise about the building blocks of an integer.

You already know

$a\mid b$ means $b=ak$ for an integer $k$ . Expanding and factorising expressions can expose such an integer multiplier; exact division has remainder zero.

Prime and composite are classifications of positive integers greater than one.

Prime and composite numbers

A prime number is a positive integer greater than one with exactly two positive divisors, one and itself. A composite number is a positive integer greater than one with a positive divisor other than one and itself. For example, two is prime and nine is composite. One is neither prime nor composite, and negative integers are not prime numbers under this definition.

To prove compositeness by factorisation, produce two integer factors both greater than one. They need not be different: $49=7\times7$ is composite. For example,

n^2+3n+2=(n+1)(n+2)

is composite for every positive integer $n$ , because both factors exceed one. At $n=0$ it is two, so the restriction matters.

Every positive integer greater than one can be built from primes in an essentially unique way.

Fundamental theorem of arithmetic

Every integer greater than one is a product of prime numbers, uniquely apart from their order. Equivalently, it has a unique expression

p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}

with distinct primes $p_i$ and positive integer exponents $a_i$ .
Not in the formula booklet: learn it.

For instance, $360=2^3\times3^2\times5$ . Writing $360=6\times60$ is a factorisation, but not a prime factorisation. You may use the fundamental theorem without proving it.

Key idea

To prove a number composite, find a non-trivial factorisation; to compare divisibility systematically, reduce its factors to primes.

The following flawed argument confuses the boundary on a factor with whether the two factors are equal.

Highest common factors

A common divisor must fit inside both prime factorisations, so each prime exponent is limited by the smaller exponent available.

Highest common factor and coprimality

The highest common factor of positive integers $a,b$ , written $\operatorname{hcf}(a,b)$ , is their largest positive common divisor. They are coprime, or relatively prime, if $\operatorname{hcf}(a,b)=1$ . For example, eight and fifteen are coprime although neither is prime; six and fifteen are not.

If a prime occurs in only one factorisation, its exponent in the other is zero, so it contributes nothing to the highest common factor.

Prime exponents in the highest common factor

Write $a=\prod p^{\alpha_p}$ and $b=\prod p^{\beta_p}$ , using exponent zero for a prime absent from one number. Then

\operatorname{hcf}(a,b)=\prod p^{\min(\alpha_p,\beta_p)}

Not in the formula booklet: learn it.

The picture compares the exponents directly.

[DIAGRAM: asset_name: Common prime exponents; asset_slug: h245_8_02_common_prime_factors; caption: The smaller exponent of each prime determines the highest common factor; description: Four aligned columns labelled prime 2, prime 3, prime 5 and prime 7 compare the prime factorisations of 84 and 150. Pale blocks show each exponent; shared blocks for one factor of two and one factor of three are blue and all remaining blocks grey. The bottom line states that the highest common factor is two times three, giving six.]
The smaller exponent of each prime determines the highest common factor

There is no need for the two numbers themselves to be prime.

Worked example 1: extracting the common prime factors

Question. Find $\operatorname{hcf}(84,150)$ .

Plan. Factor both numbers into primes and take the smaller exponent of each prime.

\begin{aligned} 84&=2^2\times3\times7 &&\text{prime factorisation}\\ 150&=2\times3\times5^2 &&\text{prime factorisation}\\ \operatorname{hcf}(84,150)&=2^1\times3^1=6 &&\text{common primes, smaller exponents} \end{aligned}

Why this step? A factor containing $2^2$ would not divide $150$ , and a factor containing five or seven would fail for one of the numbers.

Answer. The highest common factor is $6$ .

Check. $84=6\times14$ and $150=6\times25$ ; fourteen and twenty-five share no prime factor, so no larger common divisor remains.

The next example changes only the second number. The absence of a shared prime now gives coprimality.

Worked example 2: composite but coprime

Question. Determine whether $84$ and $125$ are coprime.

Plan. Compare their prime factorisations and check for a common prime.

\begin{aligned} 84&=2^2\times3\times7 &&\text{as before}\\ 125&=5^3 &&\text{prime factorisation}\\ \operatorname{hcf}(84,125)&=1 &&\text{no common prime} \end{aligned}

Why this step? A common divisor greater than one would have a prime divisor; that prime would have to occur in both factorisations.

Answer. The two numbers are coprime.

Check. The only positive divisors of $125$ are $1,5,25,125$ ; among them only one divides $84$ .

Coprimality is a relation between two integers, rather than a statement that either one is prime.

Watch out

Wrong: “Both numbers are composite, so they are not coprime.” Right: eight and nine are composite and coprime. Check shared factors, not the separate classifications.

The next pair shares a prime but has different exponents.

Integer linear combinations

A common divisor also divides every integer combination of the two numbers.

For example, a common divisor of $84$ and $150$ divides $150-84=66$ , and it also divides $2\times84-150=18$ . These smaller numbers can be easier to analyse than the originals.

Divisibility of integer combinations

If $a\mid b$ and $a\mid c$ , then

a\mid(bx+cy)\qquad\text{for all integers }x,y

Not in the formula booklet: learn it.

Here is the reason. If $b=au$ and $c=av$ , then $bx+cy=a(ux+vy)$ , and the bracket is an integer. Negative multipliers are allowed; they are often the useful ones because they cancel a large term.

The converse needs care: a divisor of one combination need not divide both original numbers. For instance, three divides $4+5$ , but divides neither four nor five.

Worked example 3: consecutive integers

Question. Prove that $n$ and $n+1$ are coprime for every positive integer $n$ .

Plan. Let $d$ be a positive common divisor and use the difference to restrict it.

\begin{aligned} d\mid n,\quad d\mid(n+1) &\ \Longrightarrow\ d\mid\bigl((n+1)-n\bigr) &&\text{integer combination}\\ &\ \Longrightarrow\ d\mid1 &&\text{simplify}\\ &\ \Longrightarrow\ d=1 &&d\text{ is positive} \end{aligned}

Why this step? A difference removes the unknown $n$ , replacing the common-divisor problem by the fixed number one.

Answer. The only positive common divisor is one, so $\operatorname{hcf}(n,n+1)=1$ .

Check. $24$ and $25$ share no prime factor, consistent with the proof.

The next example changes only the gap between the two integers. The difference now leaves a small set of possibilities rather than a single one.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account

Last Accessed

Pure Core

Statistics

Mechanics

Discrete Mathematics

Additional Pure Mathematics

8.02i–8.02k - Primes, factors and Euclid's lemma

Primes and composites

Highest common factors

Integer linear combinations

Continue this lesson.

Learn faster with Nova