Number theory path · N04

Before this lesson: Divisibility of integers, Algebraic identities and factorisation, How to write a proof

Your goal: Prove compositeness or an infinitude claim using a clear contradiction or factorisation.

Start with the idea and one example. Take a break before the written task if you need it. The questions are original teaching exercises, not official past-paper questions.

Prime numbers: the key idea

A prime is an integer greater than 1 with exactly two positive divisors, 1 and itself. A composite integer is greater than 1 and not prime; 1 is neither. If n is composite, it has a prime divisor at most n\sqrt{n}, so trial division need only test primes up to that bound. Euclid’s construction shows primes are infinite, but does not assert that one plus a product of primes is itself prime. Algebraic identities can expose hidden factors, such as Sophie Germain’s a⁴+4b⁴=(a²−2ab+2b²)(a²+2ab+2b²).

A worked example

Is 97 prime?

Since 97<10\sqrt{97}<10, test primes 2,3,5,7. None divides 97: it is odd, its digit sum is 16, its last digit is not 0 or 5, and 97=7·13+6. Therefore 97 is prime.

Your turn: change one thing

Factor 5⁴+4 using Sophie Germain’s identity.

Try this on paper before opening the explanation.

Compare your reasoning

Take a=5,b=1. The factors are 25−10+2=17 and 25+10+2=37, so 629=17·37.

Pause and check

A trap to avoid: Calling 1 prime or assuming Euclid’s constructed number is always prime.

Practise and adjust the level

Foundation checks the language; Core applies the method; Stretch asks you to choose or justify an idea. These are levels within this lesson. A session selects six of the nine questions; unused questions allow the level to change. Advanced theory still needs written practice.

Interactive practice loads here. You can also use the complete question set below.

Write a complete argument

Prove there are infinitely many primes.

Planning hint

List the assumptions and the exact conclusion. Identify the definition or theorem in this lesson that connects them. Explain why its conditions hold before using it.

Read the full solution after your attempt

Suppose a finite list p₁,…,pₖ contains all primes. Let N=p₁⋯pₖ+1>1. It has a prime divisor q. None of the pᵢ divides N, since division leaves remainder 1. Thus q is a prime missing from the list, a contradiction.

My proof notebook

Write on paper, or keep a draft here. Compare your reasoning with the solution only after a real attempt. The checklist is your own review, not an automatic mark.

All nine practice questions

Prefer paper or have JavaScript switched off? The complete question set, hints and solutions are here. Interactive practice uses these same questions in an order chosen from your answers.

1. Is 1 prime?

Foundation

  1. Yes
  2. Only in base two
  3. Sometimes
  4. No, it has only one positive divisor
Hint

Use the definition with exactly two divisors.

Answer and reasoning

No, it has only one positive divisor. The sole positive divisor of 1 is 1.

2. To test n for primality by trial division, primes up to which bound suffice?

Foundation

  1. n+1
  2. log n always
  3. n\sqrt{n}
  4. n²
Hint

A composite factor pair has a small factor.

Answer and reasoning

n\sqrt{n}. If both factors exceeded n\sqrt{n} their product would exceed n.

3. Which of these numbers is prime?

Core

  1. 91
  2. 87
  3. 95
  4. 97
Hint

Test prime divisors at most 9.

Answer and reasoning

97. 97 has no divisor among 2,3,5,7; the others are 7·13,3·29,5·19.

4. What is a nontrivial factor of 5⁴+4?

Core

  1. 7
  2. 11
  3. 17
  4. 5
Hint

Apply the Sophie Germain factorisation.

Answer and reasoning

17. 5⁴+4=17·37.

5. Does Euclid’s construction require p₁⋯pₖ+1 to be prime?

Stretch

  1. Yes always
  2. Only if k is even
  3. Only if 2 is on the list
  4. No, one of its prime divisors is enough
Hint

Separate the constructed integer from a prime factor.

Answer and reasoning

No, one of its prime divisors is enough. Every prime divisor is outside the assumed complete list.

6. Why is 1 excluded from primes in unique factorisation?

Stretch

  1. 1 divides no integers
  2. 1 has two distinct positive divisors
  3. Allowing arbitrary factors of 1 would destroy literal uniqueness
  4. 1 is negative
Hint

Think of inserting extra factors equal to 1.

Answer and reasoning

Allowing arbitrary factors of 1 would destroy literal uniqueness. The standard definition avoids unlimited redundant unit factors.

7. Which description defines a composite integer?

Foundation

  1. The integer 1
  2. Any odd integer
  3. An integer greater than 1 with a nontrivial factorisation
  4. Any integer greater than 1
Hint

It must have a divisor other than 1 and itself.

Answer and reasoning

An integer greater than 1 with a nontrivial factorisation. A composite integer has a factorisation ab with integers a,b greater than 1.

8. Find a nontrivial factor of 91.

Core

  1. 7
  2. 2
  3. 3
  4. 5
Hint

Test primes up to 91\sqrt{91}.

Answer and reasoning

7. 91=7·13.

9. If a composite n has factors a,b>1 with ab=n, why is one at most n\sqrt{n}?

Stretch

  1. Otherwise their product would exceed n
  2. Both must be equal
  3. Both are always prime
  4. Square roots are integers
Hint

Compare ab with n⋅n\sqrt{n}\cdot \sqrt{n}.

Answer and reasoning

Otherwise their product would exceed n. If both exceeded n\sqrt{n}, then ab>n, a contradiction.

Choose your next step

Continue to Unique prime factorisation. If this felt difficult, return to a prerequisite above. Every lesson stays open.

Open my revision list →

Original teaching material · IMOolympiad.com. Send a specific correction through our contact page. Learning progress is optional and stays in this browser.