Make learning comfortable

Visual experienceAnimationRead-aloud speedChanging style, motion, or reading speed keeps your current question, answers, homework, and saved progress. The school band still chooses your task layout. Saved to your learner profile across devices. All lessons and help stay available.

Introduction to Number Theory / LEVEL 1 · DIFFICULTY 1/5

Divisibility and Prime Structure

Organize factors and divisors.

3 stages · 24 practice problems · two 6-question assessment forms

Choose an island to read its lesson.

MINI QUEST NT 1.1Euclid’s AlgorithmRead the lesson
MINI QUEST NT 1.2Counting DivisorsRead the lesson
MINI QUEST NT 1.3Summing DivisorsRead the lesson
LEVEL CHECKCastle challenge
6 questions across this level.
Sign in for the level check →

STAGE NT 1.1 · 8 PRACTICE PROBLEMS · 2 NEW-CONTEXT APPLICATIONS

Euclid’s Algorithm

Goal: Understand and apply euclid’s algorithm.

Before you begin: Integer arithmetic, prime factorization and fractions.

Understand the idea

A common divisor of a and b also divides a−qb. Replacing the larger input by its remainder therefore preserves the complete set of common divisors.

\displaystyle \operatorname{gcd}\, \left(a, b\right) = \operatorname{gcd}

(b,a mod b)

Choose and carry out a method

Repeatedly divide with remainder until the remainder is zero. The last nonzero remainder is the greatest common divisor.

Check the reasoning

It must divide both original numbers. The backward remainder identities explain why no larger common divisor was missed.

WORKED EXAMPLE 1

Find $\displaystyle \operatorname{gcd}\, \left(36, 57\right)$ using the Euclidean algorithm.

Replacing the larger number by its remainder preserves the common divisors.
$\displaystyle 57 = 36 + 21$ ; continue dividing until the remainder is zero.
The last nonzero remainder is 3. Both lengths are multiples of it.

WORKED EXAMPLE 2

Find $\displaystyle \operatorname{gcd}\, \left(48, 76\right)$ using the Euclidean algorithm.

Replacing the larger number by its remainder preserves the common divisors.
$\displaystyle 76 = 48 + 28$ ; continue dividing until the remainder is zero.
The last nonzero remainder is 4. Both lengths are multiples of it.

Common pitfalls

Possible mix-up: The first remainder is always the $\displaystyle \operatorname{gcd}$ .

Continue until a zero remainder appears.

Possible mix-up: A correct numerical answer alone explains the method.

State the governing relationship and check the conditions described above.

Explain it to yourself

Explain why subtracting a multiple preserves common divisors.

Preview the eight practice prompts

Problem 1
Find $\displaystyle \operatorname{gcd}\, \left(72{,}114\right)$ using the Euclidean algorithm.
Practise this exact problem →
Problem 2
Find $\displaystyle \operatorname{gcd}\, \left(84{,}133\right)$ using the Euclidean algorithm.
Practise this exact problem →
Problem 3
Find $\displaystyle \operatorname{gcd}\, \left(96{,}152\right)$ using the Euclidean algorithm.
Practise this exact problem →
Problem 4
Find $\displaystyle \operatorname{gcd}\, \left(108{,}171\right)$ using the Euclidean algorithm.
Practise this exact problem →
Problem 5
Find $\displaystyle \operatorname{gcd}\, \left(120{,}190\right)$ using the Euclidean algorithm.
Practise this exact problem →
Problem 6
Find $\displaystyle \operatorname{gcd}\, \left(132{,}209\right)$ using the Euclidean algorithm.
Practise this exact problem →
Problem 7New context
Two cables measure 144 cm and 228 cm. They must be cut into equal pieces with no leftover cable. What is the greatest possible piece length in centimeters?
Practise this exact problem →
Problem 8New context
Two cables measure 156 cm and 247 cm. They must be cut into equal pieces with no leftover cable. What is the greatest possible piece length in centimeters?
Practise this exact problem →

Open stage NT 1.1 in the student workspace →

STAGE NT 1.2 · 8 PRACTICE PROBLEMS · 2 NEW-CONTEXT APPLICATIONS

Counting Divisors

Useful preparation: Euclid’s Algorithm

Goal: Understand and apply counting divisors.

Before you begin: Euclid’s Algorithm

Understand the idea

Unique prime factorization means each positive divisor is specified by choosing one exponent for each prime. An exponent may be zero, which includes divisors omitting that prime.

\displaystyle d\, \left(p^{a}\, q^{b}\right) = \left(a + 1\right)\, \left(b + 1\right)

Choose and carry out a method

For $\displaystyle p^{a}\, q^{b}$ , choose the p-exponent from 0 through a and the q-exponent from 0 through b. Multiply the independent choice counts.

Check the reasoning

One and the original number must both be included. Listing a small example checks the interpretation of the exponent choices.

WORKED EXAMPLE 1

How many positive divisors does $\displaystyle 2^{3} \cdot 3^{1}$ have?

A divisor chooses a permitted exponent for each prime independently.
The exponent of 2 has 4 choices and that of 3 has 2.
There are 8 divisors; each determines exactly one complementary height.

WORKED EXAMPLE 2

How many positive divisors does $\displaystyle 2^{4} \cdot 3^{1}$ have?

A divisor chooses a permitted exponent for each prime independently.
The exponent of 2 has 5 choices and that of 3 has 2.
There are 10 divisors; each determines exactly one complementary height.

Common pitfalls

Possible mix-up: Multiply the exponents themselves.

Include zero, so each exponent gives one additional choice.

Possible mix-up: A correct numerical answer alone explains the method.

State the governing relationship and check the conditions described above.

Explain it to yourself

How does each divisor correspond to a rectangle width when the area is fixed?

Preview the eight practice prompts

Problem 1
How many positive divisors does $\displaystyle 2^{2} \cdot 3^{2}$ have?
Practise this exact problem →
Problem 2
How many positive divisors does $\displaystyle 2^{3} \cdot 3^{2}$ have?
Practise this exact problem →
Problem 3
How many positive divisors does $\displaystyle 2^{4} \cdot 3^{2}$ have?
Practise this exact problem →
Problem 4
How many positive divisors does $\displaystyle 2^{5} \cdot 3^{2}$ have?
Practise this exact problem →
Problem 5
How many positive divisors does $\displaystyle 2^{2} \cdot 3^{3}$ have?
Practise this exact problem →
Problem 6
How many positive divisors does $\displaystyle 2^{3} \cdot 3^{3}$ have?
Practise this exact problem →
Problem 7New context
A set of 432 tiles can be arranged into ordered rectangles of positive whole-number width and height. Rotating a nonsquare rectangle counts as a different arrangement. How many widths are possible?
Practise this exact problem →
Problem 8New context
A set of 864 tiles can be arranged into ordered rectangles of positive whole-number width and height. Rotating a nonsquare rectangle counts as a different arrangement. How many widths are possible?
Practise this exact problem →

Open stage NT 1.2 in the student workspace →

STAGE NT 1.3 · 8 PRACTICE PROBLEMS · 2 NEW-CONTEXT APPLICATIONS

Summing Divisors

Useful preparation: Counting Divisors

Goal: Understand and apply summing divisors.

Before you begin: Counting Divisors

Understand the idea

Expanding a product of sums of prime powers produces each positive divisor exactly once. This converts a long list of divisors into short geometric sums.

\displaystyle \sigma\, \left(p^{a}\, q^{b}\right)

=(1+…

\displaystyle +p^{a}

)(1+…

\displaystyle +q^{b}

)

Choose and carry out a method

Write one sum $\displaystyle 1 + p$ +… $\displaystyle +p^{a}$ for each prime factor. Evaluate each sum and multiply them, keeping the divisor count separate from their sum.

Check the reasoning

The sum must exceed the number itself whenever the number is greater than one. Check a small factorization by listing its divisors.

WORKED EXAMPLE 1

Find the sum of the positive divisors of $\displaystyle 2^{2} \cdot 3$ .

Distribute a product of sums of prime powers to enumerate divisors once.
( $\displaystyle 1 + 2$ +… $\displaystyle +2^{2}$ ) $\displaystyle \left(1 + 3\right) = \left(7\right) \cdot 4$ .
The divisor sum is 28; do not confuse it with the number of divisors.

WORKED EXAMPLE 2

Find the sum of the positive divisors of $\displaystyle 2^{3} \cdot 3$ .

Distribute a product of sums of prime powers to enumerate divisors once.
( $\displaystyle 1 + 2$ +… $\displaystyle +2^{3}$ ) $\displaystyle \left(1 + 3\right) = \left(15\right) \cdot 4$ .
The divisor sum is 60; do not confuse it with the number of divisors.

Common pitfalls

Possible mix-up: The divisor count equals the divisor sum.

Counting terms and adding their values are different operations.

Possible mix-up: A correct numerical answer alone explains the method.

State the governing relationship and check the conditions described above.

Explain it to yourself

Why does distributing the product produce neither missing nor repeated divisors?

Preview the eight practice prompts

Problem 1
Find the sum of the positive divisors of $\displaystyle 2^{5} \cdot 3$ .
Practise this exact problem →
Problem 2
Find the sum of the positive divisors of $\displaystyle 2^{6} \cdot 3$ .
Practise this exact problem →
Problem 3
Find the sum of the positive divisors of $\displaystyle 2^{7} \cdot 3$ .
Practise this exact problem →
Problem 4
Find the sum of the positive divisors of $\displaystyle 2^{8} \cdot 3$ .
Practise this exact problem →
Problem 5
Find the sum of the positive divisors of $\displaystyle 2^{9} \cdot 3$ .
Practise this exact problem →
Problem 6
Find the sum of the positive divisors of $\displaystyle 2^{10} \cdot 3$ .
Practise this exact problem →
Problem 7New context
A scoring system awards d points for every positive divisor d of 6144. What is the total score?
Practise this exact problem →
Problem 8New context
A scoring system awards d points for every positive divisor d of 12288. What is the total score?
Practise this exact problem →

Open stage NT 1.3 in the student workspace →

Browse another level →

Divisibility and Prime Structure

Euclid’s Algorithm

Understand the idea

Choose and carry out a method

Check the reasoning

Find gcd⁡ (36,57)\displaystyle \operatorname{gcd}\, \left(36, 57\right)gcd(36,57) using the Euclidean algorithm.

Find gcd⁡ (48,76)\displaystyle \operatorname{gcd}\, \left(48, 76\right)gcd(48,76) using the Euclidean algorithm.

Common pitfalls

Explain it to yourself

Counting Divisors

Understand the idea

Choose and carry out a method

Check the reasoning

How many positive divisors does 23⋅31\displaystyle 2^{3} \cdot 3^{1}23⋅31 have?

How many positive divisors does 24⋅31\displaystyle 2^{4} \cdot 3^{1}24⋅31 have?

Common pitfalls

Explain it to yourself

Summing Divisors

Understand the idea

Choose and carry out a method

Check the reasoning

Find the sum of the positive divisors of 22⋅3\displaystyle 2^{2} \cdot 322⋅3.

Find the sum of the positive divisors of 23⋅3\displaystyle 2^{3} \cdot 323⋅3.

Common pitfalls

Explain it to yourself

Find $\displaystyle \operatorname{gcd}\, \left(36, 57\right)$ using the Euclidean algorithm.

Find $\displaystyle \operatorname{gcd}\, \left(48, 76\right)$ using the Euclidean algorithm.

How many positive divisors does $\displaystyle 2^{3} \cdot 3^{1}$ have?

How many positive divisors does $\displaystyle 2^{4} \cdot 3^{1}$ have?

Find the sum of the positive divisors of $\displaystyle 2^{2} \cdot 3$ .

Find the sum of the positive divisors of $\displaystyle 2^{3} \cdot 3$ .