Star problems Advanced ← Back to chapter

Factors and Multiples: Star problems

Ten optional challenges to stretch your reasoning. Work on paper, use hints when you need them, and check the answer or full solution when you are ready. You can skip these problems and continue the course.

1 of 3 stars: Stretch
2 of 3 stars: Challenge
3 of 3 stars: Deep challenge

Stars indicate difficulty within this set.

0 of 10 completed

Progress saved in this browser.

Problem 1 of 10

Problem 1 The two middle factors

Difficulty: 1 of 3 stars, Stretch

A positive integer has exactly eight positive factors. Written in increasing order, its fourth factor is 9 and its fifth factor is 15. Find the integer and all eight factors. Explain why your answer is forced.
1. Hint 1
  If a factor is larger, is its partner in the product larger or smaller?
2. Hint 2
  Pair the smallest factor with the largest, then the second smallest with the second largest. Which factors pair in the middle?
Answer

The integer is 135. Its factors are 1, 3, 5, 9, 15, 27, 45, and 135.

Full solution

For any factor of a positive integer, dividing the integer by that factor gives another factor.
A larger factor has a smaller partner.
Thus, in an ordered list of eight factors, the first and eighth form a pair, as do the second and seventh, the third and sixth, and the fourth and fifth.
Every pair has product equal to the original integer.

The two middle factors therefore force the integer to be
$9\times15=135.$
We must still check that this number really has exactly eight factors, with the stated middle entries.
Since $135=3^3\times5$ , every factor uses 0, 1, 2, or 3 copies of 3, and either no copy or one copy of 5.
These choices give the eight distinct factors 1, 3, 5, 9, 15, 27, 45, and 135.
The fourth and fifth entries are indeed 9 and 15.
Both the reconstruction and the required factor count check out.

Answer

The integer is 135. Its factors are 1, 3, 5, 9, 15, 27, 45, and 135.

Key idea

An ordered factor list has a hidden symmetry: opposite entries multiply to the original number.
Problem 1: Mark complete
Problem 2 Three primes with fixed gaps

Difficulty: 1 of 3 stars, Stretch

Find every prime number $p$ for which $p+2$ and $p+10$ are also prime. Prove that you have found all possibilities.
1. Hint 1
  Consider the possible remainders when $p$ is divided by 3.
2. Hint 2
  Among $p$ , $p+2$ , and $p+10$ , one is divisible by 3. A prime divisible by 3 must be 3 itself.
Answer

The only possibility is $p=3$ , giving the primes 3, 5, and 13.

Full solution

Every integer leaves remainder 0, 1, or 2 when divided by 3.
If $p$ leaves remainder 0, then $p$ is divisible by 3.
If $p$ leaves remainder 1, then $p+2$ is divisible by 3.
If $p$ leaves remainder 2, then $p+10$ is divisible by 3, since adding 10 increases the remainder by the same amount as adding 1.

All three numbers are required to be prime.
Therefore, whichever one is divisible by 3 must equal 3; a larger positive multiple of 3 has a factor other than 1 and itself.
The possibilities are $p=3$ , $p+2=3$ , or $p+10=3$ .
The second gives $p=1$ , which is not prime, and the third gives a negative number.
Only $p=3$ remains.
It works: 3, 5, and 13 are all prime.
This remainder argument rules out every other prime without searching through a long list.

Answer

The only possibility is $p=3$ , giving the primes 3, 5, and 13.

Key idea

A small divisor can rule out an unlimited number of candidates.
Problem 2: Mark complete
Problem 3 Same GCF, same LCM

Difficulty: 1 of 3 stars, Stretch

Find all pairs of positive integers $a<b$ whose greatest common factor is 6 and whose least common multiple is 180. Explain why your list is complete.
1. Hint 1
  Both integers contain a factor of 6. Remove that shared factor from each.
2. Hint 2
  The remaining two numbers must have no common prime factor, and their LCM is 30. Decide which number receives each of the primes 2, 3, and 5.
Answer

The pairs are $(6,180)$ , $(12,90)$ , $(18,60)$ , and $(30,36)$ .

Full solution

Because the GCF is 6, both numbers are multiples of 6.
Divide each by 6.
The two resulting positive integers are relatively prime, meaning their GCF is 1.
Their LCM is
$180\div6=30.$
Multiplying both numbers by 6 multiplies their LCM by 6, since every common multiple is scaled by that same factor.

The prime factorization of 30 is $2\times3\times5$ .
Each of these three primes must occur in one of the two reduced numbers, or their LCM would miss it.
None can occur in both, because the reduced numbers are relatively prime.
No other prime or higher power is allowed.
Thus we distribute the three prime factors between two groups.
Ignoring the order of the groups gives $(1,30)$ , $(2,15)$ , $(3,10)$ , and $(5,6)$ .

Multiplying each pair by 6 gives $(6,180)$ , $(12,90)$ , $(18,60)$ , and $(30,36)$ .
Each has the required GCF and LCM.
Every possible distribution has been included, so there are no additional pairs.

Answer

The pairs are $(6,180)$ , $(12,90)$ , $(18,60)$ , and $(30,36)$ .

Key idea

After removing a GCF, distribute complete prime factors between relatively prime parts.
Problem 3: Mark complete
Problem 4 Make the product a square

Difficulty: 2 of 3 stars, Challenge

Twelve cards are labeled 1 through 12. Remove as few cards as possible so that the product of the labels on the remaining cards is a perfect square. A perfect square is the square of a positive integer. Find the minimum number of cards to remove and every set of removed cards that achieves it.
1. Hint 1
  In a perfect square, the exponent of every prime in the prime factorization is even.
2. Hint 2
  First consider the primes 7 and 11. After dealing with those cards, which prime still has an odd exponent?
Answer

Remove three cards. The only minimum sets are {3, 7, 11} and {7, 11, 12}.

Full solution

The full product has prime factorization $2^{10}\times3^5\times5^2\times7\times11$ .
For example, the factors 2, 4, 6, 8, 10, and 12 contribute $1+2+1+3+1+2=10$ copies of 2.
The factors 3, 6, 9, and 12 contribute five copies of 3.

A perfect square has even prime exponents because squaring doubles every exponent.
Only the card 7 contributes a factor of 7, and only the card 11 contributes a factor of 11.
Both cards must therefore be removed.
Removing just those two leaves five copies of 3, so at least one more removal is necessary.

If exactly one further card is removed, it must contribute an odd number of copies of 3 and an even number of copies of every other prime.
Among the remaining labels 1 through 12, precisely 3 and 12 have this property: their factorizations are $3$ and $2^2\times3$ .
Removing 3, 7, and 11 leaves
$2^{10}\times3^4\times5^2=1440^2.$
Removing 7, 11, and 12 leaves
$2^8\times3^4\times5^2=720^2.$
Thus three removals are sufficient, necessary, and achieved by exactly the two listed sets.

Answer

Remove three cards. The only minimum sets are {3, 7, 11} and {7, 11, 12}.

Key idea

For square products, track whether each prime exponent is odd or even instead of multiplying everything.
Problem 4: Mark complete
Problem 5 A divisor that never fails

Difficulty: 2 of 3 stars, Challenge

Choose any five consecutive positive integers and multiply them. What is the greatest positive integer that is guaranteed to divide the product, regardless of which five integers were chosen? Prove both that your number always works and that no larger number can always work.
1. Hint 1
  The choice 1, 2, 3, 4, 5 puts a limit on any guaranteed divisor.
2. Hint 2
  For every block of five consecutive integers, count the factors of 2, 3, and 5 that must appear.
Answer

The greatest guaranteed divisor is 120.

Full solution

First use the smallest allowed block.
The product of 1, 2, 3, 4, and 5 is 120.
Any number that divides every possible product must divide this one.
In particular, it cannot be greater than 120.

Now consider any five consecutive positive integers.
At least one is divisible by 5, because a multiple of 5 appears once in every five consecutive integers.
At least one is divisible by 3.
There are also at least three factors of 2 in the product: among the first four integers, one is a multiple of 4 and another is even.
The multiple of 4 contributes two copies of 2, and the other even integer contributes at least one more.

The product therefore contains at least $2^3\times3\times5=120$ as a factor.
Some of these contributions may come from the same integer, which is harmless: factors of different primes can be counted independently.
Thus 120 always divides the product.
The first block showed that no larger guaranteed divisor is possible, so 120 is the exact answer.

Answer

The greatest guaranteed divisor is 120.

Key idea

For a greatest guaranteed divisor, combine a universal divisibility proof with one limiting example.
Problem 5: Mark complete
Problem 6 Can these GCF reports be true?

Difficulty: 2 of 3 stars, Challenge

Three positive integers are named $a$ , $b$ , and $c$ . Two proposed reports list their pairwise greatest common factors.

Report I: the GCF of $a,b$ is 6; the GCF of $b,c$ is 10; the GCF of $c,a$ is 15.

Report II: the GCF of $a,b$ is 12; the GCF of $b,c$ is 18; the GCF of $c,a$ is 30.

Determine which reports are possible. For every possible report, find the smallest value of $a+b+c$ and give integers that attain it. Justify your conclusions.
1. Hint 1
  If two integers have an even GCF, what does that tell you about each integer?
2. Hint 2
  For Report II, $a$ must be divisible by both 12 and 30. Obtain a separate lower bound for each of $a$ , $b$ , and $c$ .
Answer

Report I is impossible. Report II has minimum sum 186, attained by $(a,b,c)=(60,36,90)$ .

Full solution

Report I cannot be true.
Since the GCF of $a,b$ is 6, both $a$ and $b$ are even.
Since the GCF of $b,c$ is 10, both $b$ and $c$ are even.
Consequently $a$ and $c$ are both even, so their GCF must be even.
It cannot be 15.

For Report II, $a$ must be a multiple of both 12 and 30, so $a$ is at least their LCM, 60.
Similarly, $b$ must be a multiple of both 12 and 18, giving $b\geq36$ .
Finally, $c$ must be a multiple of both 18 and 30, giving $c\geq90$ .
Every possible triple therefore has sum at least
$60+36+90=186.$

A lower bound alone does not establish that a report is possible.
Check the proposed minimum triple directly: the GCF of 60 and 36 is 12; that of 36 and 90 is 18; and that of 90 and 60 is 30.
All three requirements hold simultaneously.
Report II is possible, and its minimum sum is 186.

Answer

Report I is impossible. Report II has minimum sum 186, attained by $(a,b,c)=(60,36,90)$ .

Key idea

Local conditions must agree with one another; after deriving lower bounds, check that they can be attained together.
Problem 6: Mark complete
Problem 7 Exactly eighteen factors

Difficulty: 2 of 3 stars, Challenge

Find the smallest positive integer that is divisible by 12 and has exactly eighteen positive factors. Prove that no smaller integer works.

You may use or establish this fact: if $n=p^a q^b$ for distinct primes $p,q$ and nonnegative integer exponents $a,b$ , then its number of positive factors is $(a+1)(b+1)$ . Each additional distinct prime contributes another factor of one more than its exponent.
1. Hint 1
  Begin with the required factors $2^2\times3$ . A factor count of eighteen severely restricts the possible exponents.
2. Hint 2
  First check a candidate using the primes 2, 3, and 5. To rule out smaller numbers, separate numbers with only primes 2 and 3 from those with another prime.
Answer

The smallest integer is $180=2^2\times3^2\times5$ .

Full solution

For each prime, a factor can use any exponent from zero through the exponent in the original number.
These independent choices explain the factor-count rule.
The candidate $180=2^2\times3^2\times5$ is divisible by 12 and has $(2+1)(2+1)(1+1)=18$ factors.

Suppose a smaller number works.
It contains $2^a\times3^b$ with $a\geq2$ and $b\geq1$ .
If these are its only primes, the factor count requires
$(a+1)(b+1)=18.$
The eligible ordered factor pairs are $(3,6)$ , $(6,3)$ , and $(9,2)$ .
They give numbers 972, 288, and 768, respectively, all greater than 180.

If another prime occurs, that prime is at least 5.
A number below 180 cannot contain its square, since
$12\times25=300.$
Nor can it contain two additional distinct primes, since
$12\times5\times7=420.$
Thus there is exactly one additional prime, with exponent one.
Its contribution of 2 to the factor count leaves
$(a+1)(b+1)=9.$
The required bounds force both factors to be 3, so $a=b=2$ .
The number is then at least $2^2\times3^2\times5=180$ , contradicting its being smaller.
Therefore 180 is minimal.

Answer

The smallest integer is $180=2^2\times3^2\times5$ .

Key idea

Counting factors converts a search through integers into a short search through possible prime exponents.
Problem 7: Mark complete
Problem 8 Reconstruct from common-factor counts

Difficulty: 3 of 3 stars, Deep challenge

A positive integer $n$ has exactly three positive factors in common with 72 and exactly four positive factors in common with 108. Describe every possible $n$ , and prove your description is complete.
1. Hint 1
  The common factors of two numbers are exactly the factors of their GCF.
2. Hint 2
  A number with exactly three factors is a prime square. A number with exactly four factors is either a prime cube or the product of two distinct primes.
Answer

Exactly the odd multiples of 27 work: $27,81,135,189,\ldots$ .

Full solution

The common factors of $n$ and 72 are the factors of their GCF.
A positive integer has exactly three factors only when it is the square of a prime: the factor-count choices must be $3=2+1$ .
Since $72=2^3\times3^2$ , the GCF of $n$ and 72 must therefore be 4 or 9.

Similarly, four factors arise from a prime cube, or from two distinct primes to the first power, because
$4=3+1=2\times2.$
Since $108=2^2\times3^3$ , the GCF of $n$ and 108 must be 27 or 6.

If the first GCF were 4, $n$ would contain exactly two copies of 2 and no factor of 3.
Its GCF with 108 would then also be 4, which has three factors, not four.
This case is impossible.

Therefore the first GCF is 9.
This means $n$ is odd and contains at least two copies of 3.
Its GCF with 108 cannot be 6, since $n$ is odd, so it must be 27.
Thus $n$ is an odd multiple of 27.
Conversely, every odd multiple of 27 has GCF 9 with 72 and GCF 27 with 108.
Those GCFs have three and four factors, respectively.
This proves both directions of the description.

Answer

Exactly the odd multiples of 27 work: $27,81,135,189,\ldots$ .

Key idea

Information about common-factor counts becomes much sharper when translated into information about the GCF.
Problem 8: Mark complete
Problem 9 Three numbers, one pairwise LCM

Difficulty: 3 of 3 stars, Deep challenge

Three distinct positive integers have this property: the least common multiple of any two of them is 180. Find the smallest possible sum of the three integers. Give a triple that attains it and prove that no smaller sum is possible.
1. Hint 1
  Every integer in the triple divides 180. Use $180=4\times9\times5$ , where these three factors use different primes.
2. Hint 2
  For any pair to have LCM 180, at least one number in that pair must contain the full factor 4; likewise for 9 and 5. How many of the three numbers can lack each full factor?
Answer

The minimum sum is 101, attained by the triple 20, 36, and 45.

Full solution

The triple 20, 36, and 45 works: their factorizations are $4\times5$ , $4\times9$ , and $9\times5$ .
Every pair supplies all three full prime-power factors 4, 9, and 5, so every pair has LCM 180.
Their sum is 101.

Now consider any triple that might improve this sum.
Each number divides 180, because it divides its LCM with either partner.
If one number is 180, the sum already exceeds 101.
We may therefore assume all three are less than 180.

Each number must then lack at least one full factor among 4, 9, and 5.
A full factor cannot be lacking from two numbers: their pairwise LCM would lack it too.
There are three numbers needing a missing factor, and only three possible full factors to miss.
Consequently each number misses exactly one of these factors, and the missing factors are different.

The number lacking the full factor 4 must still contain both 9 and 5, so it is at least 45.
The number lacking 9 is at least $4\times5=20$ , and the one lacking 5 is at least
$4\times9=36.$
Their sum is at least 101.
The displayed triple attains the bound, completing the proof.

Answer

The minimum sum is 101, attained by the triple 20, 36, and 45.

Key idea

Pairwise LCM conditions limit how missing prime powers can be distributed across a collection.
Problem 9: Mark complete
Problem 10 The largest relatively prime collection

Difficulty: 3 of 3 stars, Deep challenge

Choose a set of distinct integers from 1 through 30 so that the greatest common factor of any two chosen integers is 1.

(a) What is the largest possible number of chosen integers? Prove your answer.

(b) Among all sets of that largest size, what is the greatest possible sum? Find a set that attains it and justify its optimality.
1. Hint 1
  Every chosen integer greater than 1 must use at least one prime factor. Can two chosen integers use the same prime?
2. Hint 2
  If you attain the maximum size, could any chosen integer use two different primes? Then select the largest allowed power of each prime.
Answer

(a) 11 integers. (b) The greatest sum is 188, from {1, 7, 11, 13, 16, 17, 19, 23, 25, 27, 29}.

Full solution

The primes at most 30 are 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29: ten primes.
Every chosen integer greater than 1 has a prime factor.
Two chosen integers cannot share a prime factor, because their GCF would exceed 1.
Thus at most ten chosen integers can exceed 1.
Including 1 gives at most eleven integers.
The set consisting of 1 and the ten primes attains eleven.

For part (b), a set of eleven must include 1 and ten integers greater than 1.
These ten integers collectively require at least ten different primes.
Since only ten are available, each integer must use exactly one prime, and every available prime must be used.
In other words, each of these integers is a power of a different prime.

To maximize the sum, independently choose the largest power of each prime that is at most 30.
For 2, 3, and 5 these are 16, 27, and 25.
For every prime from 7 onward, even the square exceeds 30, so use the prime itself.
Together with 1 this gives the stated set, whose sum is 188.
Raising any selected power further is impossible, so no maximum-size set has a greater sum.

Answer

(a) 11 integers. (b) The greatest sum is 188, from {1, 7, 11, 13, 16, 17, 19, 23, 25, 27, 29}.

Key idea

A limited supply of prime factors gives a size bound; attaining that bound can force a much more rigid structure.
Problem 10: Mark complete