Number theory path · N05

Before this lesson: Prime numbers, Greatest common divisor and Bézout

Your goal: Use prime-exponent parity to justify perfect-power conclusions.

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.

Names you may know: unique factorization theorem; prime factorisation theorem.

Fundamental Theorem of Arithmetic: the key idea

Every integer n>1 has a factorisation into primes, unique apart from the order of the factors. Write n=∏piein=\prod p_{i}^{e_{i}} with positive exponents. Products add exponents, gcd takes their minima and lcm their maxima. A positive integer is a square exactly when every prime exponent is even; it is a kth power exactly when all exponents are divisible by k. Uniqueness rests on Euclid’s lemma: a prime dividing ab divides a or b. The word prime is essential.

A worked example

Find the smallest positive integer m such that 72m is a square.

72=2³3². Only the exponent of 2 is odd. Multiplying by 2 makes 72m=2⁴3²=144, so the smallest m is 2. Every valid m must supply an odd exponent of 2 and even exponents of other primes; 2 is least.

Your turn: change one thing

If coprime positive a,b have ab a square, prove both are squares.

Try this on paper before opening the explanation.

Compare your reasoning

Coprimality means no prime occurs in both. Every prime exponent in ab therefore comes entirely from one factor and is even. Each factor is a square.

Pause and check

A trap to avoid: Inferring that both factors are squares without the needed coprimality.

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 Euclid’s lemma using Bézout’s identity.

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

If prime p divides ab and does not divide a, then gcd(p,a)=1. Bézout gives integers u,v with up+va=1. Multiply by b: upb+vab=b. Both terms on the left are divisible by p, so p divides b.

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. A positive integer is a square exactly when its prime exponents are what?

Foundation

  1. All even
  2. All odd
  3. All prime
  4. All equal
Hint

Squaring doubles every exponent.

Answer and reasoning

All even. Conversely, halve even exponents to construct the square root.

2. In a product, the exponents of a fixed prime do what?

Foundation

  1. Take the minimum
  2. Add
  3. Multiply
  4. Take the maximum
Hint

Use papb=pa+bp^{a}p^{b}=p^{a+b}.

Answer and reasoning

Add. Multiplication combines the prime factors by adding their counts.

3. Smallest m>0 with 72m a square?

Core

  1. 8
  2. 2
  3. 3
  4. 6
Hint

72=2³3².

Answer and reasoning

2. One additional factor 2 makes both exponents even.

4. The gcd of 2³3² and 2²3⁴ is what?

Core

  1. 324
  2. 36
  3. 72
  4. 144
Hint

Take the smaller exponent of each prime.

Answer and reasoning

36. gcd=2²3²=36.

5. If ab is a square, why is coprimality needed to conclude both are squares?

Stretch

  1. Coprime numbers are always squares
  2. The product would otherwise be negative
  3. Shared odd exponents can pair up
  4. Every square is prime
Hint

Try a=b=2.

Answer and reasoning

Shared odd exponents can pair up. 2·2=4 is square though neither factor is square; the shared prime invalidates the conclusion without coprimality.

6. Can Euclid’s lemma replace prime p by any composite integer?

Stretch

  1. No
  2. Yes always
  3. Only odd composites
  4. Only squares
Hint

Test 6 dividing 2·3.

Answer and reasoning

No. 6 divides 6 but divides neither 2 nor 3.

7. The exponent of p in papbp^{a}p^{b} is what?

Foundation

  1. max(a,b)
  2. a+b
  3. ab
  4. a−b
Hint

Combine identical prime factors.

Answer and reasoning

a+b. The product has a+b copies of p.

8. Smallest positive m making 18m a square?

Core

  1. 9
  2. 2
  3. 3
  4. 6
Hint

18=2·3².

Answer and reasoning

2. Multiplying by 2 gives 36=6².

9. If coprime positive a,b have ab a cube, what follows?

Stretch

  1. Both are cubes
  2. Both are prime
  3. One must equal 1
  4. Neither can be a cube
Hint

Prime exponents in the product are multiples of 3.

Answer and reasoning

Both are cubes. Coprimality puts each prime entirely in one factor, whose exponent must therefore be divisible by 3.

Choose your next step

Continue to Counting and summing divisors. 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.