NumeriveMATH
CurriculumFamily workspaceStudentMy characterAchievementsContact
← Introduction to Number Theory levels

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.

  1. MINI QUEST NT 1.1Euclid’s AlgorithmRead the lesson
  2. MINI QUEST NT 1.2Counting DivisorsRead the lesson
  3. MINI QUEST NT 1.3Summing DivisorsRead the lesson
  4. 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.

gcd(a,b)=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 gcd(36,57) using the Euclidean algorithm.

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

3

WORKED EXAMPLE 2

Find gcd(48,76) using the Euclidean algorithm.

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

4

Common pitfalls

Possible mix-up: The first remainder is always the 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
  1. Find gcd(72,114) using the Euclidean algorithm.
  2. Find gcd(84,133) using the Euclidean algorithm.
  3. Find gcd(96,152) using the Euclidean algorithm.
  4. Find gcd(108,171) using the Euclidean algorithm.
  5. Find gcd(120,190) using the Euclidean algorithm.
  6. Find gcd(132,209) using the Euclidean algorithm.
  7. 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? New context
  8. 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? New context
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.

d(p^a q^b)=(a+1)(b+1)

Choose and carry out a method

For 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 2^3·3^1 have?

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

8

WORKED EXAMPLE 2

How many positive divisors does 2^4·3^1 have?

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

10

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
  1. How many positive divisors does 2^2·3^2 have?
  2. How many positive divisors does 2^3·3^2 have?
  3. How many positive divisors does 2^4·3^2 have?
  4. How many positive divisors does 2^5·3^2 have?
  5. How many positive divisors does 2^2·3^3 have?
  6. How many positive divisors does 2^3·3^3 have?
  7. 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? New context
  8. 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? New context
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.

σ(p^a q^b)=(1+…+p^a)(1+…+q^b)

Choose and carry out a method

Write one sum 1+p+…+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 2^2·3.

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

28

WORKED EXAMPLE 2

Find the sum of the positive divisors of 2^3·3.

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

60

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
  1. Find the sum of the positive divisors of 2^5·3.
  2. Find the sum of the positive divisors of 2^6·3.
  3. Find the sum of the positive divisors of 2^7·3.
  4. Find the sum of the positive divisors of 2^8·3.
  5. Find the sum of the positive divisors of 2^9·3.
  6. Find the sum of the positive divisors of 2^10·3.
  7. A scoring system awards d points for every positive divisor d of 6144. What is the total score? New context
  8. A scoring system awards d points for every positive divisor d of 12288. What is the total score? New context
Open stage NT 1.3 in the student workspace →
Browse another level →