Prime, Composite and Co-prime Numbers

Learning outcome

Identify primes and composites, justify a simple primality test and distinguish a prime number from a co-prime pair.

Concepts and reasons

A positive divisor divides a number exactly, leaving remainder 0. A prime is an integer greater than 1 with exactly two positive divisors: 1 and itself. A composite is an integer greater than 1 with more than two positive divisors.

The number 1 is neither prime nor composite: it has only one positive divisor. Zero and negative integers are also outside these definitions.

The number 2 is the only even prime. Any larger even integer has divisor 2 in addition to 1 and itself. However, an odd integer greater than 1 need not be prime; it may have other divisors.

To test an integer n greater than 1, try integer divisors d starting at 2 while d × d ≤ n. If none divides n, it is prime. Why stop there? For composite n = a × b, choose a and b greater than 1. Both cannot exceed √n, or their product would exceed n. Therefore one factor lies between 2 and √n.

Two positive integers are co-prime when their only common positive divisor is 1. This describes their relationship, not whether each number is prime. Distinct primes are co-prime, but two composites can also be co-prime. The number 1 is co-prime to every positive integer.

Worked examples

Example 1. Classify 1, 2 and 21. The number 1 is neither type. The divisors of 2 are 1 and 2, so it is prime. Since 21 = 3 × 7, it is composite.

Example 2. Is 29 prime? Test 2, 3, 4 and 5; none divides 29 exactly. Since 6 × 6 = 36 > 29, no further divisor needs testing. Therefore 29 is prime.

Example 3. The divisors of 8 are 1, 2, 4, 8; those of 15 are 1, 3, 5, 15. Only 1 is common. Thus 8 and 15 are co-prime although both are composite.

Common traps

“Odd” does not mean “prime.” Co-prime does not mean “both prime.” Two identical primes are not co-prime, because their common prime divides both.

Practice questions

1. Is 49 prime or composite? Give a decisive reason.
2. Are 14 and 25 co-prime?
3. Which pairs are co-prime: (1, 12), (9, 15), (11, 11)?

Answers and explanations

1. Composite: 49 = 7 × 7. Its positive divisors are 1, 7 and 49, not just two.
2. Yes. Their divisor lists are 1, 2, 7, 14 and 1, 5, 25. Only 1 is common.
3. Only (1, 12). The pair (9, 15) has common divisor 3; (11, 11) has common divisor 11.