QuanticaPrealgebraOpen in the courseSome numbers can be arranged into a rectangle with more than one row. Others only fit into a single strip. The strip-only numbers are the primes, and they turn out to be the building blocks for every other whole number.
Problem
Coin piles of 14, 17, 21, and 23. Which can form a fat rectangle with more than one row? How many of the four can ONLY be a single strip?
Show a hint
- A pile can be fattened only if you can split it into equal rows where each row has more than one coin and there is more than one row. Try to find any such split for each number.
- For each number, hunt for a factor other than 1 and itself. For 14 and 21 such a factor exists, so picture what rows that gives you. For 17 and 23, try dividing by 2, 3, 4, and so on, and watch what happens.
- Count only the numbers where you could find no helper factor at all, the ones left as a lonely one-row strip.
Show the full solution
\(14 = 2 \times 7\) and \(21 = 3 \times 7\), so both of those fatten into a rectangle with more than one row. For \(17\), nothing from \(2\) up to \(4\) divides it, and \(4^2 = 16 < 17\), so the check is finished. The same tests all miss on \(23\). Those two are stuck as single strips, so the count is \(\boxed{2}\).
A pile widens exactly when the number has a factor besides 1 and itself, and that factor is the number of rows.
Problem
Walk through every whole number strictly between 23 and 29. Name a factor for each one. How many primes lie strictly between 23 and 29?
Show a hint
- A number is prime only when its sole factors are \(1\) and itself. So go down the list \(24, 25, 26, 27, 28\) and try to break each one into a product of smaller whole numbers.
- Three of these five are even, so \(2\) divides them right away. For the two odd ones, test \(25\) against \(5\) and test \(27\) against \(3\).
- If every single number between \(23\) and \(29\) turns out to be composite, then none of them is prime. Count how many primes survived.
Show the full solution
Every number in the gap breaks apart.
$$24 = 2 \times 12, \qquad 25 = 5 \times 5, \qquad 26 = 2 \times 13, \qquad 27 = 3 \times 9, \qquad 28 = 2 \times 14$$
All five are composite, so the number of primes strictly between 23 and 29 is \(\boxed{0}\).
Five composites in a row, and gaps like this have no size limit. With the right construction you can find a stretch of a thousand composites with no prime inside.
Problem
A game show flashes 51, 91, 95, and 97, claiming at least one hides a small factor. Use the divisibility shortcuts from 3.2 to find every hidden factor. How many of the four are prime?
Show a hint
- A prime number has exactly two factors, itself and 1. So if you can find even one smaller number that divides a candidate, it is composite, not a prime.
- Go down your list of quick tests from 3.2. Look at the last digit for the 5 test, and add the digits for the 3 test. Which of 51, 91, 95, 97 get caught right away?
- Three of them fall to a small factor. For the one survivor, check that no small prime up to its square root divides it, then trust that it really is prime.
Show the full solution
Hunt for one small factor in each.
$$51 = 3 \times 17, \qquad 91 = 7 \times 13, \qquad 95 = 5 \times 19$$
Those three are composite. For 97, \(\sqrt{97}\) sits between 9 and 10, so only 2, 3, 5, and 7 need testing, and none of them divides 97. That leaves \(\boxed{1}\) prime.
The digit-sum test catches 51 and the last digit catches 95, but 91 slips past both. Products of 7 with a larger prime are where people usually go wrong.
Problem
Doors 2 through 50 are all lit. Each caretaker finds the lowest lit door (their prime) and turns off all its higher multiples. After sweeps for 2, 3, 5, and 7, how many doors stay lit?
Show a hint
- Track what it means for a door to get switched off. A door goes dark exactly when its number is a higher multiple of one of the sweeping numbers 2, 3, 5, or 7. So a door stays lit only if its number is not a multiple of any of those, except for the four sweeping doors themselves which are always left lit.
- A number that is not a multiple of 2, 3, 5, or 7 and is bigger than 1 has no small prime divisor at all. Think about what kind of number that has to be, and remember from 3.1 that you only need to test divisors up to the square root.
- Since the square root of 50 is about 7.07, any composite number up to 50 must have a prime factor of 7 or smaller. That means every composite door is switched off by 2, 3, 5, or 7. Count the doors that survive by listing the numbers from 2 to 50 with no factor among 2, 3, 5, 7, then add back the doors 2, 3, 5, 7 themselves.
Show the full solution
A door goes dark only if its number is a higher multiple of 2, 3, 5, or 7. Since \(\sqrt{50} \approx 7.07\), every composite number up to 50 carries a prime factor of 7 or smaller, so all of them get switched off. What stays lit is the primes from 2 to 50.
$$2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29,\ 31,\ 37,\ 41,\ 43,\ 47$$
That is \(\boxed{15}\) doors.
Sweeping with the primes up to \(\sqrt{N}\) is enough to clear every composite below \(N\), which is exactly why the sieve stops at 7 here.
Problem
Marta tests 223 for primality. Since \(15^2=225>223\), she only tests primes up to 14. She tries 2, 3, 5, 7, 11, 13, each leaving a remainder. What is the largest prime she divides by?
Show a hint
- Marta only needs to look for a factor whose partner is at least as big, so the smaller one sits at or below the square root of 223. Since \(15 \times 15 = 225\), that square root is just under 15. How far up does she actually have to test?
- She is smart and tests only primes, because any composite trial divisor (like 9 or 15) is built from smaller primes she already checked. List the primes from 2 up to 14 and find the biggest one.
- The primes she tests are 2, 3, 5, 7, 11, and 13. The next prime, 17, is past her stopping line, so it never gets used. Which of the primes she actually divides by is the largest?
Show the full solution
The primes from 2 up to 14 are 2, 3, 5, 7, 11, and 13, and the largest of those is \(\boxed{13}\).
She stops at 14 because \(15^2 = 225 > 223\), and she skips composite divisors like 9 or 14 because their prime factors were already tested.
Split a composite into two smaller factors, split each composite piece again, and stop when every piece is prime. The branching picture, a factor tree, leaves primes at the bottom. Do two different trees always give the same primes?
Problem
A display shows the prime fingerprint \(2 \times 3 \times 3 \times 7\). Multiply the atoms to find the hidden number.
Show a hint
- The fingerprint is just a multiplication waiting to happen. You do not need to divide anything, you only need to multiply the listed atoms together.
- Group the easy pieces first. The two 3s make \(3 \times 3 = 9\), which leaves you with \(2 \times 9 \times 7\).
- Multiply in any order you like, since the order never changes a product. Try \(2 \times 9 = 18\) first, then multiply that by 7.
Show the full solution
$$2 \times 3 \times 3 \times 7 = 2 \times 9 \times 7 = 18 \times 7 = 126$$
The hidden number is \(\boxed{126}\).
The fingerprint also tells you 126 is even, since it carries a 2, and divisible by 9, since it carries two 3s. No division needed.
Problem
Tara splits 90 as \(9\times10\), and Niko splits it as \(6\times15\). Both reach the same prime atoms. Counting every atom (with repeats), how many prime atoms does 90 have?
Show a hint
- A prime atom is a number you cannot split any further with whole-number factors bigger than 1, like \(2\), \(3\), or \(5\). Keep splitting until every piece is one of those.
- Both friends end with the same little collection of primes. Line up Tara's bottom row and Niko's bottom row and check that they match.
- Count the primes at the bottom one by one, and if the same prime appears twice, count it twice.
Show the full solution
Tara's \(9 \times 10\) breaks down into \(3 \times 3\) and \(2 \times 5\). Niko's \(6 \times 15\) breaks down into \(2 \times 3\) and \(3 \times 5\). Both bottom rows are the same.
$$90 = 2 \times 3 \times 3 \times 5 = 2 \times 3^2 \times 5$$
Counting with repeats gives \(\boxed{4}\) prime atoms.
The first cut never matters. Every factor tree for a number lands on the same bag of primes.
Problem
A craftsperson has 360 beads (\(360 = 2^3 \times 3^2 \times 5\)) and wants a perfect square total. What is the smallest whole number to multiply 360 by so that the result is a perfect square?
Show a hint
- Look at the fingerprint \(360 = 2^3 \times 3^2 \times 5\). When you build a square of side \(s\), each side gets exactly half of every prime in the total. So think about which exponents can be split into two equal whole pieces and which cannot.
- An exponent like the 2 on the \(3\) splits evenly into \(1\) and \(1\). But the 3 on the \(2\) and the hidden 1 on the \(5\) are odd, so they cannot be cut cleanly in half. Each odd exponent is the real problem.
- To turn an odd exponent into an even one, you only need one more copy of that prime. Find every prime with an odd exponent, and multiply by exactly one of each. Then ask what that product is.
Show the full solution
$$360 = 2^3 \times 3^2 \times 5$$
A perfect square needs every exponent even. The \(3^2\) is already fine, but \(2^3\) needs one more 2 and \(5^1\) needs one more 5, so multiply by \(2 \times 5 = 10\). That gives \(360 \times 10 = 3600 = 2^4 \times 3^2 \times 5^2 = 60^2\), so the smallest multiplier is \(\boxed{10}\).
Halving each exponent gives the side length, \(2^2 \times 3 \times 5 = 60\), and halving only works when every exponent is even.
Problem
A toy company has 144 cubes (\(144 = 2^4 \times 3^2\)). What is the smallest positive whole number to multiply 144 by so the result is a perfect cube?
Show a hint
- A perfect square wanted every prime to show up an even number of times so it could split into two equal groups. A perfect cube splits into three equal groups instead. How many times must each prime appear so it can be shared evenly among three layers?
- Look at the fingerprint \(2^4 \times 3^2\). For a cube, each exponent has to be a multiple of \(3\). The exponent \(4\) is not a multiple of \(3\), and neither is \(2\). Climb each one up to the next multiple of \(3\).
- The next multiple of \(3\) above \(4\) is \(6\), so you are short two \(2\)s. The next multiple of \(3\) above \(2\) is \(3\), so you are short one \(3\). Multiply those missing primes together to find your number.
Show the full solution
$$144 = 2^4 \times 3^2$$
A perfect cube needs every exponent to be a multiple of 3. The exponent 4 has to climb to 6, costing two more 2s, and the exponent 2 has to climb to 3, costing one more 3. So multiply by
$$2^2 \times 3 = 12,$$
which gives \(144 \times 12 = 2^6 \times 3^3 = 12^3 = 1728\). The answer is \(\boxed{12}\).
A square splits the primes into two equal groups and a cube into three, which is why the test moves from even exponents to multiples of 3.
Problem
The hidden number has fingerprint \(2^4 \times 3 \times 5^6\). Each trailing zero needs one 2 paired with one 5. How many zeros does the number end in?
Show a hint
- A number ends in a zero exactly when it is divisible by \(10\). What two prime building blocks does \(10\) split into?
- Since \(10 = 2 \times 5\), every trailing zero comes from one factor of \(2\) teamed up with one factor of \(5\). So count how many such teams you can make.
- You have four \(2\)s and six \(5\)s. Pair them off one for one. The moment you run out of the scarcer prime, you cannot form any more complete \(2\)-and-\(5\) teams.
Show the full solution
Each trailing zero is a factor of \(10 = 2 \times 5\), so it costs one 2 paired with one 5. The fingerprint \(2^4 \times 3 \times 5^6\) holds four 2s and six 5s, so you can build four pairs before the 2s run out. The number ends in \(\boxed{4}\) zeros.
The scarcer prime sets the count. Two spare 5s are left with no partner, and a lone 5 cannot make a zero.
Problem
Find the smallest perfect square divisible by 2, 3, 5, and 7 all at once.
Show a hint
- Think in terms of the prime fingerprint of the number. For the pile to share evenly into groups of \(2\), of \(3\), of \(5\), and of \(7\), each of those primes has to appear in the fingerprint at least once.
- Now bring in the perfect square idea from earlier. A number is a perfect square exactly when every exponent in its prime fingerprint is even. An odd count like one will not do, so each prime needs to show up an even number of times.
- Combine the two requirements. Each of \(2, 3, 5, 7\) must appear, and each must appear an even number of times. The smallest even count that is still at least one is two, so try giving every prime an exponent of exactly \(2\) and compute the result.
Show the full solution
Each of 2, 3, 5, and 7 has to appear in the fingerprint, and a perfect square needs every exponent even, so the smallest exponent each one can take is 2.
$$2^2 \times 3^2 \times 5^2 \times 7^2 = (2 \times 3 \times 5 \times 7)^2 = 210^2 = 44100$$
The smallest such square is \(\boxed{44100}\).
The divisibility demands set a floor on each exponent, and the square condition rounds every floor up to the next even number.
This section leaves you with two tools. You can test whether a number is prime by dividing by the primes up to \(\sqrt{n}\), and you can read a number's prime fingerprint to get divisibility, perfect powers, and trailing zeros. Next we put two fingerprints side by side to find the GCD and LCM.
Practice these ideas
Practice
A librarian checks which of 143, 149, 151, 161, and 167 are prime. Every number here is below \(169=13^2\), so test primes up to 13. How many of the five are prime?
Show the solution
All five are odd and none end in 0 or 5, and the digit sums 8, 14, 7, 8, 14 rule out 3. That leaves 7, 11, and 13 to test.
$$143 = 11 \times 13, \qquad 161 = 7 \times 23$$
Those two are composite. 149, 151, and 167 leave a remainder against 7, 11, and 13, and since all five sit below \(169 = 13^2\), there is nothing further to check. So \(\boxed{3}\) of the five are prime.
Trial division can stop at \(\sqrt{n}\), because any factor above it already comes with a smaller partner below it.
Practice
Find the largest two-digit prime whose tens digit and units digit are both composite.
Show the solution
The composite single digits are 4, 6, 8, and 9, so both digits must come from that set. Starting at the top, 99, 98, 96, and 94 are all composite, since three of them are even and \(99 = 9 \times 11\). Next comes 89. It is odd, its digit sum is 17, it does not end in 0 or 5, and 7 misses it since \(7 \times 12 = 84\) and \(7 \times 13 = 91\). With \(\sqrt{89} < 10\) that finishes the check, so the answer is \(\boxed{89}\).
The digit 1 counts as neither prime nor composite, so it is not allowed in either spot.
Practice
At a mixer, two guests pair if both ages are prime and add to 48. How many unordered prime pairs sum to 48?
Show the solution
Let the smaller prime \(p\) climb and ask each time whether \(48 - p\) is also prime.
$$(5, 43), \qquad (7, 41), \qquad (11, 37), \qquad (17, 31), \qquad (19, 29)$$
The rest fail, since \(45\), \(35\), and \(25\) are composite, and 2 is out because \(46\) is not prime. Stopping at the halfway point 24 keeps you from counting a pair twice, so there are \(\boxed{5}\) pairs.
An even sum forces both primes to be odd, which is why 2 never shows up in any pair here.
Practice
Stickers print in runs of \(6p\) where \(p\) is prime, and the run must stay under 800. What is the largest prime bundle size \(p\)?
Show the solution
The run \(6p\) must stay under 800, so \(p < \tfrac{800}{6} = 133\tfrac{1}{3}\), which caps \(p\) at 133. Walking down, \(133 = 7 \times 19\) is composite and 132 is even. Then 131 survives 2, 3, 5, 7, and 11, and \(12^2 = 144 > 131\), so it is prime. The largest bundle size is \(\boxed{131}\).
A number ending in 1 or 3 can still be composite, as 133 shows, so the top candidate is worth testing rather than trusting.
Practice
Find two prime numbers that add to 39. There is exactly one pair. What is the larger prime?
Show the solution
39 is odd, so one of the two primes has to be even, and 2 is the only even prime. That forces the other to be \(39 - 2 = 37\), which is prime since 2, 3, and 5 all miss and \(6^2 = 36 < 37 < 49\). The larger prime is \(\boxed{37}\).
Whenever two primes add to an odd number, one of them must be 2, which usually pins the whole pair down at once.
Practice
How many distinct prime factors does 2310 have?
Show the solution
Peel off the smallest prime each time. \(2310 = 2 \times 1155\), then \(1155 = 3 \times 385\), then \(385 = 5 \times 77\), and \(77 = 7 \times 11\).
$$2310 = 2 \times 3 \times 5 \times 7 \times 11$$
No prime repeats, so the number of distinct prime factors is \(\boxed{5}\).
2310 is the product of the first five primes, which is why its factorization comes out so clean.
Practice
Two tools, gathered. Test primality by dividing by primes up to \(\sqrt{n}\), and the 3.2 shortcuts clear 2, 3, 5 instantly. The fingerprint \(n=p^a q^b\cdots\) reveals divisibility, perfect squares (all exponents even), perfect cubes (all multiples of 3), and trailing zeros (2-and-5 pairs).
Practice
A box shows \(2^x \times 3^y \times 5^z = 6000\). Find \(x\), \(y\), \(z\) by factoring 6000, then enter their sum \(x+y+z\).
Show the solution
Split 6000 into \(6 \times 1000\). Six is \(2 \times 3\), and \(1000 = 10^3 = 2^3 \times 5^3\), so
$$6000 = 2^4 \times 3^1 \times 5^3.$$
A prime factorization is unique, so the exponents on each side must agree one for one, giving \(x = 4\), \(y = 1\), \(z = 3\) and \(x + y + z = \boxed{8}\).
Uniqueness is what lets you read the exponents straight off both sides. Without it, matching prime powers would prove nothing.
Practice
A tiler has 252 tiles (\(252 = 2^2 \times 3^2 \times 7\)) and needs a perfect-square total. What is the smallest whole number to multiply 252 by?
Show the solution
$$252 = 2^2 \times 3^2 \times 7$$
Only the 7 sits at an odd exponent, so one more 7 fixes it. The smallest multiplier is \(\boxed{7}\), and \(252 \times 7 = 2^2 \times 3^2 \times 7^2 = 42^2 = 1764\).
A perfect square has every exponent even, so you only ever multiply by the primes currently sitting at an odd exponent.
Practice
A sculptor has 72 cubes (\(72 = 2^3 \times 3^2\)) and wants a perfect-cube total. What is the smallest whole number to multiply 72 by?
Show the solution
$$72 = 2^3 \times 3^2$$
A perfect cube needs every exponent to be a multiple of 3. The exponent on 2 is already 3, and the exponent on 3 has to climb from 2 to 3, so one more factor of 3 does it. Multiplying by \(\boxed{3}\) gives \(2^3 \times 3^3 = 6^3 = 216\).
Nothing smaller works. Multiplying by 2 would push the exponent on 2 up to 4 and leave both exponents off a multiple of 3.
Practice
Two numbers multiply to 504. Each is divisible by 6 but neither equals 6. What is the larger of the two numbers?
Show the solution
Both numbers are divisible by 6, so write them as \(6m\) and \(6n\). Then \(36mn = 504\), which gives \(mn = 14\). The factor pairs of 14 are \(1 \times 14\) and \(2 \times 7\), and the first is out because it would make one number \(6 \times 1 = 6\). The other pair gives \(6 \times 2 = 12\) and \(6 \times 7 = 42\), so the larger is \(\boxed{42}\).
Pulling the shared factor out of both numbers shrinks 504 down to 14, which you can factor at a glance.
Practice
A rectangular garden has area 1271 sq ft with both side lengths two-digit whole numbers. There is exactly one such rectangle. What is the length of its longer side?
Show the solution
A side length has to divide 1271, and since \(35^2 = 1225\) and \(36^2 = 1296\), the smaller side is at most 35. Testing primes, 2, 3, and 5 fail on sight, then 7, 11, 13, 17, 19, 23, and 29 all fail, and 31 divides cleanly.
$$1271 = 31 \times 41$$
Both 31 and 41 are prime, so this is the only factor pair above 1, and the longer side is \(\boxed{41}\).
When a number is a product of two primes, it has exactly one rectangle with both sides bigger than 1.
Practice
Find all sets of three different primes that add to 30. How many such sets are there?
Show the solution
Three odd numbers add to an odd total, but 30 is even, so one of the three primes has to be 2. The other two must add to 28.
$$28 = 5 + 23, \qquad 28 = 11 + 17$$
The other starts fail, since 25, 21, and 15 are all composite. That gives the sets \(\{2, 5, 23\}\) and \(\{2, 11, 17\}\), so the count is \(\boxed{2}\).
A parity check collapses the search before you start guessing, turning a three-number hunt into a two-number one.
Practice
Every checked even number above 2 equals two primes added together. Goldbach conjectured this holds for all even numbers, but no proof exists after nearly 300 years.