소수와 소인수분해Primes & Prime Factorization

기초 산술Foundations · 2. 약수와 배수2. Factors & Multiples

학습 목표

소수와 합성수를 정의하고, $1$ 이 소수도 합성수도 아닌 이유를 설명할 수 있다.
에라토스테네스의 체로 소수를 찾고, 소수 판정 때 "제곱해서 그 수를 넘지 않는 소수까지만" 확인하면 되는 이유를 설명할 수 있다.
수를 소인수분해해 거듭제곱으로 정리하고, 소인수분해로 약수의 개수를 셀 수 있다.
소수가 끝없이 많다는 유클리드의 증명을 따라갈 수 있다.

더 쪼개지지 않는 수

$12 = 3 \times 4$ 처럼 어떤 수는 더 작은 두 수의 곱으로 쪼개진다. $4 = 2 \times 2$ 로 한 번 더 쪼개면 $12 = 2 \times 2 \times 3$ 이고, 여기서 끝이다. $2$ 와 $3$ 은 $1$ 과 자기 자신 말고는 약수가 없어서 더 쪼갤 수 없다. 이런 수가 소수다. 곱셈 세계의 원자라고 할 수 있다.

정의소수와 합성수

$1$ 보다 큰 자연수 중에서 약수가 $1$ 과 자기 자신뿐인 수를 소수, 약수가 그 밖에도 있는 수를 합성수라고 한다. $1$ 은 소수도 합성수도 아니다.

\text{소수: } 2, 3, 5, 7, 11, 13, 17, 19, 23, \ldots \qquad \text{합성수: } 4, 6, 8, 9, 10, 12, 14, 15, \ldots

$1$ 을 따로 빼 두는 데는 이유가 있다. 약수가 $1$ 하나뿐이라 "약수가 두 개"라는 소수의 모양에 맞지 않고, 더 중요하게는 $1$ 을 소수로 치면 $12 = 2 \times 2 \times 3 = 1 \times 2 \times 2 \times 3 = 1 \times 1 \times 2 \times 2 \times 3$ 처럼 쪼개는 방법이 무한히 많아져 버린다. 잠시 뒤 볼 "쪼개는 방법은 한 가지"라는 사실을 지키기 위해 $1$ 은 원자 목록에서 뺀다. $2$ 는 유일한 짝수 소수다. 다른 짝수는 전부 $2$ 를 약수로 갖기 때문이다.

에라토스테네스의 체

$50$ 까지의 소수를 한 번에 찾는 방법이 있다. $2$ 부터 $50$ 까지 늘어놓고, $2$ 를 남긴 채 $2$ 의 배수를 전부 지운다. 남은 수 중 다음 수 $3$ 을 남기고 $3$ 의 배수를 지운다. 다음 남은 수 $5$ , 그다음 $7$ 에 대해서도 같이 한다. 지워지지 않고 남은 수가 소수다.

1부터 50까지의 체. 2, 3, 5, 7의 배수를 지우고 남은 15개가 소수다.

$7$ 까지만 하고 멈춰도 될까? $50$ 이하의 합성수 $n = a \times b$ ( $a$ 가 작은 쪽)에서 $a \times a \le n \le 50$ 이므로 $a \le 7$ 이다. $a$ 가 소수가 아니면 $a$ 의 소인수는 더 작다. 그러니 $50$ 이하의 모든 합성수는 $7$ 이하의 소수 중 하나를 약수로 가지고, $2, 3, 5, 7$ 의 배수를 지우는 것으로 합성수는 전부 걸러진다. 같은 논리가 소수 판정의 지름길이 된다.

정의소수 판정

$n$ 이 소수인지 알아보려면 제곱해서 $n$ 을 넘지 않는 소수들로만 나누어 보면 된다. 어느 것으로도 나누어떨어지지 않으면 소수다.

예제 1 · 소수처럼 보이는 수

$97$ 과 $91$ 은 소수인가?

풀이. $10 \times 10 = 100 > 97$ 이므로 $10$ 미만의 소수 $2, 3, 5, 7$ 만 확인한다. $97$ 은 홀수, 자릿수 합 $16$ 은 $3$ 의 배수가 아니고, 끝자리가 $5$ 나 $0$ 이 아니며, $97 = 7 \times 13 + 6$ . 넷 다 안 되므로 $97$ 은 소수다.

$91$ : $2, 3, 5$ 는 같은 이유로 안 되지만 $91 = 7 \times 13$ . 합성수다.

검산: $7 \times 13 = 91$ ✓. $97$ 은 $8, 9$ 로도 나누어 볼 필요가 없다. $8$ 이나 $9$ 가 약수라면 그 약수 $2$ 나 $3$ 이 먼저 걸렸을 것이다 ✓.

소인수분해

합성수를 소수만의 곱으로 쓰는 것을 소인수분해라 하고, 곱에 나오는 소수를 소인수라 한다. $360$ 을 분해해 보자. 두 수의 곱으로 쪼개고, 쪼개진 수가 합성수면 또 쪼갠다.

360의 인수 나무. 36 × 10으로 쪼개기 시작해 끝에 남는 잎은 2, 2, 2, 3, 3, 5.

360 = 36 \times 10 = (4 \times 9) \times (2 \times 5) = 2 \times 2 \times 2 \times 3 \times 3 \times 5.

같은 수를 여러 번 곱한 것은 줄여 쓴다. $2 \times 2 \times 2$ 는 $2^3$ (" $2$ 의 세제곱")이라 쓰고, 위에 작게 쓴 $3$ 을 지수라 부른다. 그러면

360 = 2^3 \times 3^2 \times 5.

$360 = 12 \times 30$ 이나 $360 = 8 \times 45$ 로 시작해도 나무의 모양은 달라지지만 마지막 잎은 똑같이 $2, 2, 2, 3, 3, 5$ 다. 어떤 자연수든 소인수분해의 결과는 순서를 빼면 한 가지뿐이다. 이 사실은 이 단원의 모든 도구가 서 있는 땅인데, 증명은 경시 과정의 정수론에서 한다. 지금은 믿고 쓰자.

나무 대신 나눗셈 사다리로 해도 된다. 가장 작은 소수부터 나누어떨어지는 동안 계속 나누고, 안 되면 다음 소수로 넘어간다.

예제 2 · 나눗셈 사다리

$504$ 를 소인수분해하여라.

풀이. $504 \div 2 = 252$ , $252 \div 2 = 126$ , $126 \div 2 = 63$ . 이제 $2$ 로는 안 된다. $63 \div 3 = 21$ , $21 \div 3 = 7$ . $7$ 은 소수이므로 끝.

504 = 2^3 \times 3^2 \times 7.

검산: $2^3 = 8$ , $3^2 = 9$ , $8 \times 9 \times 7 = 504$ ✓.

주의

소인수분해는 소수로만 쓴다. $360 = 8 \times 45$ 나 $360 = 2^3 \times 45$ 는 곱으로 쪼갠 것이지 소인수분해가 아니다. $45$ 가 아직 $3^2 \times 5$ 로 쪼개지기 때문이다. 끝에 남은 수가 전부 소수인지 확인하고 멈춘다.

소인수분해로 약수 세기

약수와 배수 차시에서 $72$ 의 약수를 짝지어 $12$ 개 찾았다. 소인수분해 $72 = 2^3 \times 3^2$ 로 보면 세지 않고도 개수를 알 수 있다. $72$ 의 약수는 $2$ 를 $0, 1, 2, 3$ 개 중 몇 개, $3$ 을 $0, 1, 2$ 개 중 몇 개 골라 곱한 수다. 다른 소수는 들어갈 수 없다. $2$ 와 $3$ 말고 다른 소인수를 가진 수는 $72$ 를 나누지 못하기 때문이다.

	$3^0 = 1$	$3^1 = 3$	$3^2 = 9$
$2^0 = 1$	$1$	$3$	$9$
$2^1 = 2$	$2$	$6$	$18$
$2^2 = 4$	$4$	$12$	$36$
$2^3 = 8$	$8$	$24$	$72$

$2$ 의 개수 $4$ 가지와 $3$ 의 개수 $3$ 가지가 짝지어 표의 칸 $4 \times 3 = 12$ 개를 만들고, 칸마다 다른 약수 하나씩이 들어간다. 그때의 목록과 정확히 같다.

정의약수의 개수

$n = p^a \times q^b \times \cdots$ 로 소인수분해되면 약수의 개수는 $(a + 1) \times (b + 1) \times \cdots$ 이다. 각 소수를 " $0$ 개부터 지수 개까지" 고르는 가짓수를 곱한 것이다.

예제 3 · 세지 않고 세기

$360$ 의 약수는 몇 개인가?

풀이. $360 = 2^3 \times 3^2 \times 5^1$ 이므로 $(3 + 1) \times (2 + 1) \times (1 + 1) = 4 \times 3 \times 2 = 24$ 개.

검산: 짝으로 세어도 된다. $18 \times 18 = 324 \le 360 < 361$ 이므로 $18$ 까지 확인 — $1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18$ 의 $12$ 개가 작은 쪽이고 각각 짝이 있으니 $24$ 개 ✓.

약수와 배수 차시의 "약수 개수가 홀수 ⟺ 제곱수"도 여기서 다시 보인다. $3{,}600 = 2^4 \times 3^2 \times 5^2$ 처럼 지수가 모두 짝수이면 $(4 + 1)(2 + 1)(2 + 1) = 45$ 로 홀수이고, 실제로 $3{,}600 = (2^2 \times 3 \times 5)^2 = 60^2$ 이다. 지수가 하나라도 홀수이면 그 $(\text{지수} + 1)$ 이 짝수라 전체가 짝수가 된다.

소수는 끝이 없다

소수 목록은 $2, 3, 5, 7, 11, \ldots$ 로 이어진다. 언젠가 끝날까? 이천 년도 더 전에 유클리드가 끝나지 않는다는 것을 증명했고, 그 논증은 지금도 그대로 통한다.

소수가 유한 개뿐이라서 전부 적을 수 있다고 하자. 그 소수를 모두 곱한 뒤 $1$ 을 더한 수 $N$ 을 만든다. $N$ 을 목록의 어떤 소수로 나누어도 나머지가 $1$ 이다. 곱한 부분은 나누어떨어지고 더한 $1$ 이 남기 때문이다. 그런데 $N$ 은 $1$ 보다 큰 자연수이므로 소수이거나, 소수인 약수를 가진다. 그 소수는 목록의 어느 소수로도 나누어떨어지지 않는 $N$ 을 나누므로 목록에 없던 소수다. 목록이 전부였다는 가정에 모순이다. 그러므로 소수는 끝이 없다.

작은 예로 감을 잡자. $2 \times 3 \times 5 \times 7 + 1 = 211$ 은 소수다. $2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30{,}031 = 59 \times 509$ 는 소수가 아니지만, 그 소인수 $59$ 와 $509$ 는 곱한 목록에 없던 새 소수다. 증명이 약속한 것은 " $N$ 이 소수"가 아니라 " $N$ 의 소인수가 새 소수"라는 점이다.

참고

소수는 무한히 많지만 규칙적으로 나타나지는 않는다. $100$ 까지 $25$ 개, $1{,}000$ 까지 $168$ 개로 점점 드물어지고, $2$ 와 $3$ 말고는 이웃한 소수가 없다(하나는 짝수이므로). $11$ 과 $13$ , $17$ 과 $19$ 처럼 $2$ 차이 나는 쌍이 무한히 많은지는 아직 아무도 모른다.

Goals

Define prime and composite numbers, and explain why $1$ is neither.
Find primes with the sieve of Eratosthenes, and explain why testing a number for primality only needs the primes whose square does not exceed it.
Factor a number into primes, write the result with exponents, and count factors from the prime factorization.
Follow Euclid's proof that the primes never run out.

Numbers that cannot be split

Some numbers split into a product of smaller numbers, like $12 = 3 \times 4$ . Split once more, $4 = 2 \times 2$ , and $12 = 2 \times 2 \times 3$ , where it ends: $2$ and $3$ have no factors besides $1$ and themselves, so they cannot be split further. Such numbers are primes, the atoms of multiplication.

DefinitionPrimes and composites

A whole number greater than $1$ whose only factors are $1$ and itself is prime; one with additional factors is composite. The number $1$ is neither prime nor composite.

\text{Primes: } 2, 3, 5, 7, 11, 13, 17, 19, 23, \ldots \qquad \text{Composites: } 4, 6, 8, 9, 10, 12, 14, 15, \ldots

There is a reason for setting $1$ aside. Its only factor is $1$ itself, so it does not fit the "exactly two factors" shape of a prime; more importantly, if $1$ counted as a prime, then $12 = 2 \times 2 \times 3 = 1 \times 2 \times 2 \times 3 = 1 \times 1 \times 2 \times 2 \times 3$ would have infinitely many splittings. To protect the fact, coming shortly, that "there is only one way to split," $1$ is left off the list of atoms. Note that $2$ is the only even prime, since every other even number has $2$ as a factor.

The sieve of Eratosthenes

There is a way to find all primes up to $50$ in one sweep. List $2$ through $50$ . Keep $2$ and cross out every other multiple of $2$ . The next survivor is $3$ : keep it and cross out its multiples. Do the same with the next survivors, $5$ and $7$ . Whatever is never crossed out is prime.

The sieve from 1 to 50. After crossing out the multiples of 2, 3, 5, and 7, the 15 survivors are the primes.

Is it safe to stop at $7$ ? Take a composite $n = a \times b$ with $n \le 50$ and $a$ the smaller factor. Then $a \times a \le n \le 50$ , so $a \le 7$ ; and if $a$ is not itself prime, it has an even smaller prime factor. So every composite up to $50$ has a prime factor of at most $7$ , and crossing out the multiples of $2, 3, 5, 7$ catches every composite. The same reasoning gives a shortcut for testing a single number.

DefinitionTesting for primality

To decide whether $n$ is prime, divide only by the primes whose square does not exceed $n$ . If none divides evenly, $n$ is prime.

Example 1 · Numbers that look prime

Are $97$ and $91$ prime?

Solution. Since $10 \times 10 = 100 > 97$ , only the primes below $10$ need testing: $2, 3, 5, 7$ . $97$ is odd; its digit sum $16$ is not a multiple of $3$ ; it does not end in $0$ or $5$ ; and $97 = 7 \times 13 + 6$ . All four fail, so $97$ is prime.

$91$ : $2, 3, 5$ fail for the same reasons, but $91 = 7 \times 13$ . Composite.

Check: $7 \times 13 = 91$ ✓. There was no need to try $8$ or $9$ on $97$ : if either divided it, its factor $2$ or $3$ would have been caught first ✓.

Prime factorization

Writing a composite number as a product of primes only is called prime factorization, and the primes involved are its prime factors. Let's factor $360$ . Split it into two factors; whenever a factor is composite, split it again.

A factor tree for 360. Starting from 36 × 10, the leaves at the bottom are 2, 2, 2, 3, 3, 5.

360 = 36 \times 10 = (4 \times 9) \times (2 \times 5) = 2 \times 2 \times 2 \times 3 \times 3 \times 5.

Repeated factors are abbreviated: $2 \times 2 \times 2$ is written $2^3$ (" $2$ cubed," or " $2$ to the third"), and the small raised $3$ is the exponent. So

360 = 2^3 \times 3^2 \times 5.

Starting from $360 = 12 \times 30$ or $360 = 8 \times 45$ gives a differently shaped tree, but the leaves at the bottom are the same $2, 2, 2, 3, 3, 5$ . For every whole number, the prime factorization is unique apart from the order of the factors. This fact is the ground on which every tool in this unit stands; its proof belongs to the number theory of the competition track. For now, use it with confidence.

Instead of a tree, a division ladder works too: divide by the smallest prime as long as it goes in evenly, then move on to the next prime.

Example 2 · The division ladder

Factor $504$ into primes.

Solution. $504 \div 2 = 252$ , $252 \div 2 = 126$ , $126 \div 2 = 63$ . Now $2$ no longer goes in. $63 \div 3 = 21$ , $21 \div 3 = 7$ . Since $7$ is prime, stop.

504 = 2^3 \times 3^2 \times 7.

Check: $2^3 = 8$ , $3^2 = 9$ , and $8 \times 9 \times 7 = 504$ ✓.

Watch out

A prime factorization uses primes only. $360 = 8 \times 45$ and $360 = 2^3 \times 45$ are splittings, not prime factorizations, because $45$ still splits into $3^2 \times 5$ . Stop only when every number left is prime.

Counting factors from the factorization

In the factors-and-multiples lesson we paired up the factors of $72$ and found $12$ of them. From the factorization $72 = 2^3 \times 3^2$ , the count can be known without listing. A factor of $72$ is built by choosing $0, 1, 2$ , or $3$ copies of $2$ and $0, 1$ , or $2$ copies of $3$ , then multiplying. No other prime can appear, since a number with some other prime factor cannot divide $72$ .

	$3^0 = 1$	$3^1 = 3$	$3^2 = 9$
$2^0 = 1$	$1$	$3$	$9$
$2^1 = 2$	$2$	$6$	$18$
$2^2 = 4$	$4$	$12$	$36$
$2^3 = 8$	$8$	$24$	$72$

Four choices for the $2$ s and three for the $3$ s combine into $4 \times 3 = 12$ cells, each holding a different factor. It is exactly that list.

DefinitionThe number of factors

If $n = p^a \times q^b \times \cdots$ is the prime factorization, the number of factors of $n$ is $(a + 1) \times (b + 1) \times \cdots$ : the product of the number of ways to choose each prime, from $0$ copies up to the exponent.

Example 3 · Counting without listing

How many factors does $360$ have?

Solution. $360 = 2^3 \times 3^2 \times 5^1$ , so there are $(3 + 1) \times (2 + 1) \times (1 + 1) = 4 \times 3 \times 2 = 24$ factors.

Check by pairing: since $18 \times 18 = 324 \le 360 < 361$ , test up to $18$ . The smaller members are $1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18$ , twelve of them, each with a partner, so $24$ ✓.

The factors-and-multiples lesson's "odd number of factors exactly for perfect squares" shows up here too. When every exponent is even, as in $3{,}600 = 2^4 \times 3^2 \times 5^2$ , the count $(4 + 1)(2 + 1)(2 + 1) = 45$ is odd, and indeed $3{,}600 = (2^2 \times 3 \times 5)^2 = 60^2$ . If any exponent is odd, that $(\text{exponent} + 1)$ is even and so is the whole product.

The primes never run out

The list of primes goes $2, 3, 5, 7, 11, \ldots$ . Does it ever stop? More than two thousand years ago Euclid proved that it does not, and his argument works today exactly as it did then.

Suppose there were only finitely many primes, so that all of them could be written down. Form the number $N$ by multiplying all of them together and adding $1$ . Dividing $N$ by any prime on the list leaves remainder $1$ , because the product part divides evenly and the added $1$ is left over. But $N$ is a whole number greater than $1$ , so it is either prime or has a prime factor. That prime divides $N$ , which none of the listed primes does, so it is a prime not on the list. This contradicts the assumption that the list was complete. Therefore the primes never run out.

Small cases give a feel for it. $2 \times 3 \times 5 \times 7 + 1 = 211$ is prime. $2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30{,}031 = 59 \times 509$ is not prime, but its prime factors $59$ and $509$ are new primes missing from the product. What the proof promises is not " $N$ is prime" but "the prime factors of $N$ are new."

Note

The primes are infinite but irregular. There are $25$ of them up to $100$ and $168$ up to $1{,}000$ , so they thin out; and apart from $2$ and $3$ , no two primes are neighbors, since one of any two neighbors is even. Whether there are infinitely many pairs two apart, like $11$ and $13$ or $17$ and $19$ , is a question nobody has answered yet.

몸풀기Warm-up

배운 것을 그대로 손에 익히는 단계straightforward practice to get moving

문제Problem 1 몸풀기Warm-up

$21, 23, 27, 29, 31, 33$ 을 소수와 합성수로 나누어라. 합성수는 소수의 곱으로 써라.

Sort $21, 23, 27, 29, 31, 33$ into primes and composites. Write each composite as a product of primes.

정답과 풀이Answer & solution

정답 · 소수:

23, 29, 31

. 합성수:

21 = 3 \times 7

27 = 3 \times 3 \times 3

33 = 3 \times 11

Answer · Primes:

23, 29, 31

. Composites:

21 = 3 \times 7

27 = 3 \times 3 \times 3

33 = 3 \times 11

모두 $36 = 6 \times 6$ 보다 작으므로 $2, 3, 5$ 로만 나누어 보면 된다.

$21$ : 자릿수 합 $3$ → $3$ 의 배수, $21 = 3 \times 7$ .
$23$ : 홀수, 자릿수 합 $5$ , 끝자리 $3$ → 소수.
$27$ : 자릿수 합 $9$ → $27 = 3 \times 9 = 3 \times 3 \times 3$ .
$29$ : 홀수, 자릿수 합 $11$ , 끝자리 $9$ → 소수.
$31$ : 홀수, 자릿수 합 $4$ , 끝자리 $1$ → 소수.
$33$ : 자릿수 합 $6$ → $33 = 3 \times 11$ .

검산: $3 \times 7 = 21$ , $3 \times 3 \times 3 = 27$ , $3 \times 11 = 33$ ✓.

All are below $36 = 6 \times 6$ , so only $2, 3, 5$ need testing.

$21$ : digit sum $3$ , a multiple of $3$ : $21 = 3 \times 7$ .
$23$ : odd, digit sum $5$ , ends in $3$ : prime.
$27$ : digit sum $9$ : $27 = 3 \times 9 = 3 \times 3 \times 3$ .
$29$ : odd, digit sum $11$ , ends in $9$ : prime.
$31$ : odd, digit sum $4$ , ends in $1$ : prime.
$33$ : digit sum $6$ : $33 = 3 \times 11$ .

Check: $3 \times 7 = 21$ , $3 \times 3 \times 3 = 27$ , $3 \times 11 = 33$ ✓.

문제Problem 2 몸풀기Warm-up

소인수분해하여 거듭제곱으로 나타내어라.

(a) $84$ (b) $126$

Factor into primes and write the result with exponents.

(a) $84$ (b) $126$

정답과 풀이Answer & solution

정답 · (a)

2^2 \times 3 \times 7

(b)

2 \times 3^2 \times 7

Answer · (a)

2^2 \times 3 \times 7

(b)

2 \times 3^2 \times 7

(a) $84 \div 2 = 42$ , $42 \div 2 = 21$ , $21 \div 3 = 7$ . 따라서 $84 = 2 \times 2 \times 3 \times 7 = 2^2 \times 3 \times 7$ .

(b) $126 \div 2 = 63$ , $63 \div 3 = 21$ , $21 \div 3 = 7$ . 따라서 $126 = 2 \times 3 \times 3 \times 7 = 2 \times 3^2 \times 7$ .

검산:

(a)

4 \times 3 \times 7 = 84

✓.

(b)

2 \times 9 \times 7 = 126

✓.

(a) $84 \div 2 = 42$ , $42 \div 2 = 21$ , $21 \div 3 = 7$ . So $84 = 2 \times 2 \times 3 \times 7 = 2^2 \times 3 \times 7$ .

(b) $126 \div 2 = 63$ , $63 \div 3 = 21$ , $21 \div 3 = 7$ . So $126 = 2 \times 3 \times 3 \times 7 = 2 \times 3^2 \times 7$ .

Check:

(a)

4 \times 3 \times 7 = 84

✓.

(b)

2 \times 9 \times 7 = 126

✓.

문제Problem 3 몸풀기Warm-up

다음 수를 계산하여라.

(a) $2^4 \times 5$ (b) $2^2 \times 3 \times 5^2$

Compute.

(a) $2^4 \times 5$ (b) $2^2 \times 3 \times 5^2$

정답과 풀이Answer & solution

정답 · (a)

80

(b)

300

Answer · (a)

80

(b)

300

(a) $2^4 = 2 \times 2 \times 2 \times 2 = 16$ 이므로 $16 \times 5 = 80$ .

(b) $2^2 = 4$ , $5^2 = 25$ 이므로 $4 \times 3 \times 25 = 12 \times 25 = 300$ .

검산:

(a)

80 = 2 \times 40 = 2 \times 2 \times 20 = 2 \times 2 \times 2 \times 10 = 2^4 \times 5

✓.

(b)

300 \div 4 = 75 = 3 \times 25

✓.

(a) $2^4 = 2 \times 2 \times 2 \times 2 = 16$ , so $16 \times 5 = 80$ .

(b) $2^2 = 4$ and $5^2 = 25$ , so $4 \times 3 \times 25 = 12 \times 25 = 300$ .

Check:

(a)

80 = 2 \times 40 = 2 \times 2 \times 20 = 2 \times 2 \times 2 \times 10 = 2^4 \times 5

✓.

(b)

300 \div 4 = 75 = 3 \times 25

✓.

문제Problem 4 몸풀기Warm-up

$1$ 부터 $50$ 까지의 소수를 모두 쓰고 개수를 구하여라.

List every prime from $1$ through $50$ and count them.

정답과 풀이Answer & solution

정답 ·

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

—

15

개

Answer ·

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

—

15

primes

체를 쓴다. $2$ 의 배수를 지우면 홀수만 남고, $3$ 의 배수( $9, 15, 21, 27, 33, 39, 45$ )를 지우고, $5$ 의 배수( $25, 35$ )를 지우고, $7$ 의 배수( $49$ )를 지운다. 남는 수는

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

의 $15$ 개다. $7 \times 7 = 49 \le 50 < 121 = 11 \times 11$ 이므로 $7$ 까지만 지우면 충분하다.

검산: $1$ 은 소수가 아니므로 빠졌고, $49 = 7 \times 7$ 이 지워진 것이 맞다 ✓.

Use the sieve. Crossing out multiples of $2$ leaves the odd numbers; then cross out multiples of $3$ ( $9, 15, 21, 27, 33, 39, 45$ ), of $5$ ( $25, 35$ ), and of $7$ ( $49$ ). The survivors are

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,

fifteen of them. Since $7 \times 7 = 49 \le 50 < 121 = 11 \times 11$ , sieving up to $7$ is enough.

Check: $1$ is not prime and is left out, and $49 = 7 \times 7$ was rightly crossed out ✓.

핵심Core

이 차시의 목표 수준the target level for this lesson

문제Problem 5 핵심Core

$143$ 과 $221$ 은 소수인가? 아니면 소인수분해하여라.

Are $143$ and $221$ prime? If not, factor them into primes.

정답과 풀이Answer & solution

정답 · 둘 다 합성수.

143 = 11 \times 13

221 = 13 \times 17

Answer · Both composite:

143 = 11 \times 13

221 = 13 \times 17

$143$ : $12 \times 12 = 144 > 143$ 이므로 $11$ 까지의 소수 $2, 3, 5, 7, 11$ 을 확인한다. 홀수, 자릿수 합 $8$ , 끝자리 $3$ , $143 = 7 \times 20 + 3$ 으로 $2, 3, 5, 7$ 은 안 되고, $143 = 11 \times 13$ . 합성수.

$221$ : $15 \times 15 = 225 > 221$ 이므로 $13$ 까지의 소수를 확인한다. $2, 3, 5, 7$ ( $221 = 7 \times 31 + 4$ ), $11$ ( $221 = 11 \times 20 + 1$ )은 안 되고, $221 = 13 \times 17$ . 합성수.

검산: $11 \times 13 = 143$ ✓, $13 \times 17 = 221$ ✓.

$143$ : since $12 \times 12 = 144 > 143$ , test the primes up to $11$ : $2, 3, 5, 7, 11$ . It is odd, has digit sum $8$ , ends in $3$ , and $143 = 7 \times 20 + 3$ , so $2, 3, 5, 7$ fail; but $143 = 11 \times 13$ . Composite.

$221$ : since $15 \times 15 = 225 > 221$ , test the primes up to $13$ . $2, 3, 5, 7$ ( $221 = 7 \times 31 + 4$ ) and $11$ ( $221 = 11 \times 20 + 1$ ) fail; but $221 = 13 \times 17$ . Composite.

Check: $11 \times 13 = 143$ ✓ and $13 \times 17 = 221$ ✓.

문제Problem 6 핵심Core

약수의 개수를 소인수분해로 구하여라.

(a) $360$ (b) $1{,}000$

Use prime factorization to find the number of factors.

(a) $360$ (b) $1{,}000$

정답과 풀이Answer & solution

정답 · (a)

24

개 (b)

16

개

Answer · (a)

24

(b)

16

(a) $360 = 2^3 \times 3^2 \times 5$ 이므로 $(3 + 1)(2 + 1)(1 + 1) = 24$ 개.

(b) $1{,}000 = 10^3 = (2 \times 5)^3 = 2^3 \times 5^3$ 이므로 $(3 + 1)(3 + 1) = 16$ 개.

검산: (b) $1{,}000$ 의 약수를 $2$ 의 개수(0~3)와 $5$ 의 개수(0~3)로 표를 만들면 $4 \times 4 = 16$ 칸: $1, 2, 4, 8, 5, 10, 20, 40, 25, 50, 100, 200, 125, 250, 500, 1{,}000$ ✓.

(a) $360 = 2^3 \times 3^2 \times 5$ , so $(3 + 1)(2 + 1)(1 + 1) = 24$ factors.

(b) $1{,}000 = 10^3 = (2 \times 5)^3 = 2^3 \times 5^3$ , so $(3 + 1)(3 + 1) = 16$ factors.

Check on (b): a table by the number of $2$ s ( $0$ to $3$ ) and the number of $5$ s ( $0$ to $3$ ) has $4 \times 4 = 16$ cells: $1, 2, 4, 8, 5, 10, 20, 40, 25, 50, 100, 200, 125, 250, 500, 1{,}000$ ✓.

문제Problem 7 핵심Core

소인수분해를 이용하여 $1{,}444$ 와 $600$ 이 제곱수인지 판정하여라. 제곱수이면 어떤 수의 제곱인지 밝혀라.

Use prime factorization to decide whether $1{,}444$ and $600$ are perfect squares. If one is, say which number it is the square of.

정답과 풀이Answer & solution

정답 ·

1{,}444 = 2^2 \times 19^2 = 38^2

는 제곱수.

600 = 2^3 \times 3 \times 5^2

는 제곱수가 아니다.

Answer ·

1{,}444 = 2^2 \times 19^2 = 38^2

is a perfect square.

600 = 2^3 \times 3 \times 5^2

is not.

$1{,}444 \div 2 = 722$ , $722 \div 2 = 361$ , $361 = 19 \times 19$ . 따라서 $1{,}444 = 2^2 \times 19^2$ . 지수가 모두 짝수이므로 제곱수이고, $1{,}444 = (2 \times 19)^2 = 38^2$ .

$600 = 6 \times 100 = 2 \times 3 \times 2^2 \times 5^2 = 2^3 \times 3 \times 5^2$ . $2$ 의 지수 $3$ 과 $3$ 의 지수 $1$ 이 홀수이므로 제곱수가 아니다.

검산: $38 \times 38 = 1{,}444$ ✓. $24 \times 24 = 576 < 600 < 625 = 25 \times 25$ 이므로 $600$ 은 두 제곱수 사이에 있다 ✓.

$1{,}444 \div 2 = 722$ , $722 \div 2 = 361$ , and $361 = 19 \times 19$ . So $1{,}444 = 2^2 \times 19^2$ . Every exponent is even, so it is a square: $1{,}444 = (2 \times 19)^2 = 38^2$ .

$600 = 6 \times 100 = 2 \times 3 \times 2^2 \times 5^2 = 2^3 \times 3 \times 5^2$ . The exponents of $2$ and $3$ are odd, so it is not a square.

Check: $38 \times 38 = 1{,}444$ ✓. And $24 \times 24 = 576 < 600 < 625 = 25 \times 25$ , so $600$ falls between two consecutive squares ✓.

문제Problem 8 핵심Core

$40 = 2^3 \times 5$ 의 약수를 표로 빠짐없이 나열하고, 개수가 공식과 맞는지 확인하여라.

List all factors of $40 = 2^3 \times 5$ in a table, and confirm that the count agrees with the formula.

정답과 풀이Answer & solution

정답 ·

1, 2, 4, 8, 5, 10, 20, 40

—

8

개, 공식

(3 + 1)(1 + 1) = 8

과 일치

Answer ·

1, 2, 4, 8, 5, 10, 20, 40

— eight factors, matching

(3 + 1)(1 + 1) = 8

$2$ 를 $0, 1, 2, 3$ 개, $5$ 를 $0, 1$ 개 고른다.

	$5^0 = 1$	$5^1 = 5$
$2^0 = 1$	$1$	$5$
$2^1 = 2$	$2$	$10$
$2^2 = 4$	$4$	$20$
$2^3 = 8$	$8$	$40$

칸이 $4 \times 2 = 8$ 개이고 공식 $(3 + 1)(1 + 1) = 8$ 과 맞는다.

검산: 짝짓기로 — $6 \times 6 = 36 \le 40 < 49$ 이므로 $6$ 까지 확인하면 $1 \times 40, 2 \times 20, 4 \times 10, 5 \times 8$ 의 네 짝, $8$ 개 ✓.

Choose $0, 1, 2$ , or $3$ copies of $2$ and $0$ or $1$ copy of $5$ .

	$5^0 = 1$	$5^1 = 5$
$2^0 = 1$	$1$	$5$
$2^1 = 2$	$2$	$10$
$2^2 = 4$	$4$	$20$
$2^3 = 8$	$8$	$40$

There are $4 \times 2 = 8$ cells, matching the formula $(3 + 1)(1 + 1) = 8$ .

Check by pairing: since $6 \times 6 = 36 \le 40 < 49$ , test up to $6$ : the pairs $1 \times 40, 2 \times 20, 4 \times 10, 5 \times 8$ give eight factors ✓.

문제Problem 9 핵심Core

$120$ 이하의 수가 소수인지 판정하려면 어떤 소수들로만 나누어 보면 충분한가? 그 소수들로 $101, 111, 119$ 를 판정하여라.

To test whether a number up to $120$ is prime, which primes suffice as trial divisors? Use them to test $101, 111, 119$ .

정답과 풀이Answer & solution

정답 ·

2, 3, 5, 7

101

은 소수,

111 = 3 \times 37

119 = 7 \times 17

Answer ·

2, 3, 5, 7

101

is prime;

111 = 3 \times 37

;

119 = 7 \times 17

$11 \times 11 = 121 > 120$ 이므로 $11$ 미만의 소수 $2, 3, 5, 7$ 이면 충분하다. $120$ 이하의 합성수는 반드시 $7$ 이하의 소인수를 갖기 때문이다.

$101$ : 홀수, 자릿수 합 $2$ , 끝자리 $1$ , $101 = 7 \times 14 + 3$ . 소수.
$111$ : 자릿수 합 $3$ 이 $3$ 의 배수, $111 = 3 \times 37$ . 합성수.
$119$ : $2, 3, 5$ 는 안 되고 $119 = 7 \times 17$ . 합성수.

검산: $3 \times 37 = 111$ ✓, $7 \times 17 = 119$ ✓. $37$ 과 $17$ 이 소수인지도 확인 — 각각 $2, 3, 5$ 와 $2, 3$ 으로 나누어떨어지지 않는다 ✓.

Since $11 \times 11 = 121 > 120$ , the primes below $11$ , namely $2, 3, 5, 7$ , suffice: every composite up to $120$ must have a prime factor of at most $7$ .

$101$ : odd, digit sum $2$ , ends in $1$ , and $101 = 7 \times 14 + 3$ . Prime.
$111$ : digit sum $3$ is a multiple of $3$ , and $111 = 3 \times 37$ . Composite.
$119$ : $2, 3, 5$ fail, but $119 = 7 \times 17$ . Composite.

Check: $3 \times 37 = 111$ ✓ and $7 \times 17 = 119$ ✓. Also $37$ and $17$ are prime: neither is divisible by $2, 3, 5$ (for $37$ ) or $2, 3$ (for $17$ ) ✓.

도전Challenge

아이디어를 결합해야 풀리는 문제problems that take more than one idea

문제Problem 10 도전Challenge

약수가 정확히 $6$ 개인 가장 작은 자연수를 구하여라.

Find the smallest whole number with exactly $6$ factors.

힌트Hint

약수의 개수 공식에서 $(a + 1)(b + 1)\cdots = 6$ 이 되는 지수 조합은 두 가지뿐이다.

In the factor-count formula, there are only two ways for $(a + 1)(b + 1)\cdots$ to equal $6$ .

정답과 풀이Answer & solution

정답 ·

12

Answer ·

12

약수 개수는 $(\text{지수} + 1)$ 들의 곱이다. 이 곱이 $6$ 이 되는 방법은 $6$ 하나이거나 $2 \times 3$ 뿐이다.

소인수가 하나, 지수 $5$ : $p^5$ 꼴. 가장 작은 것은 $2^5 = 32$ .
소인수가 둘, 지수 $1$ 과 $2$ : $p \times q^2$ 꼴. 가장 작은 것은 큰 지수에 작은 소수를 주어 $2^2 \times 3 = 12$ . ( $2 \times 3^2 = 18$ 은 더 크다.)

둘 중 작은 것은 $12$ .

검산: $12$ 의 약수는 $1, 2, 3, 4, 6, 12$ 의 $6$ 개 ✓. $12$ 보다 작은 수들의 약수 개수는 $11$ : $2$ 개, $10$ : $4$ 개, $9$ : $3$ 개, $8$ : $4$ 개, $7$ : $2$ 개, $6$ : $4$ 개, $5$ 이하: $3$ 개 이하 — $6$ 개인 것이 없다 ✓.

The number of factors is the product of the $(\text{exponent} + 1)$ terms. That product equals $6$ either as a single $6$ or as $2 \times 3$ .

One prime with exponent $5$ : the form $p^5$ , smallest $2^5 = 32$ .
Two primes with exponents $1$ and $2$ : the form $p \times q^2$ , smallest when the larger exponent goes to the smaller prime, $2^2 \times 3 = 12$ (while $2 \times 3^2 = 18$ is larger).

The smaller of the two is $12$ .

Check: the factors of $12$ are $1, 2, 3, 4, 6, 12$ , six of them ✓. Below $12$ , the factor counts are $11$ : $2$ , $10$ : $4$ , $9$ : $3$ , $8$ : $4$ , $7$ : $2$ , $6$ : $4$ , and at most $3$ for $5$ and below; none has six ✓.

문제Problem 11 도전Challenge

$100$ 이하의 자연수 중 약수가 정확히 $12$ 개인 수를 모두 구하여라.

Find every whole number up to $100$ that has exactly $12$ factors.

힌트Hint

$(\text{지수} + 1)$ 들의 곱이 $12$ 가 되는 방법은 $12$ , $6 \times 2$ , $4 \times 3$ , $3 \times 2 \times 2$ 의 네 가지다. 각 경우가 어떤 소인수분해 꼴에 해당하는지 쓰고, $100$ 이하인 것만 골라라.

The product of the $(\text{exponent} + 1)$ terms can equal $12$ in four ways: $12$ , $6 \times 2$ , $4 \times 3$ , $3 \times 2 \times 2$ . Write the prime-factorization shape for each case and keep only the numbers up to $100$ .

정답과 풀이Answer & solution

정답 ·

60, 72, 84, 90, 96

Answer ·

60, 72, 84, 90, 96

$(\text{지수} + 1)$ 들의 곱이 $12$ 가 되는 방법은 네 가지다.

$12$ : $p^{11}$ 꼴. $2^{11} = 2{,}048 > 100$ . 없음.
$6 \times 2$ : $p^5 \times q$ 꼴. $2^5 \times 3 = 96$ ✓, $2^5 \times 5 = 160$ ✗, $3^5 = 243$ 부터는 ✗. → $96$ .
$4 \times 3$ : $p^3 \times q^2$ 꼴. $2^3 \times 3^2 = 72$ ✓, $3^3 \times 2^2 = 108$ ✗, $2^3 \times 5^2 = 200$ ✗. → $72$ .
$3 \times 2 \times 2$ : $p^2 \times q \times r$ 꼴. $2^2 \times 3 \times 5 = 60$ ✓, $2^2 \times 3 \times 7 = 84$ ✓, $3^2 \times 2 \times 5 = 90$ ✓, $2^2 \times 3 \times 11 = 132$ ✗, $2^2 \times 5 \times 7 = 140$ ✗, $5^2 \times 2 \times 3 = 150$ ✗. → $60, 84, 90$ .

모두 $60, 72, 84, 90, 96$ 의 $5$ 개다.

검산: $60$ 의 약수 $1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60$ — $12$ 개 ✓. $96 = 2^5 \times 3$ → $(5 + 1)(1 + 1) = 12$ ✓.

There are four ways for the product of the $(\text{exponent} + 1)$ terms to equal $12$ .

$12$ : the shape $p^{11}$ . $2^{11} = 2{,}048 > 100$ . None.
$6 \times 2$ : the shape $p^5 \times q$ . $2^5 \times 3 = 96$ ✓, $2^5 \times 5 = 160$ ✗, and $3^5 = 243$ onward ✗. → $96$ .
$4 \times 3$ : the shape $p^3 \times q^2$ . $2^3 \times 3^2 = 72$ ✓, $3^3 \times 2^2 = 108$ ✗, $2^3 \times 5^2 = 200$ ✗. → $72$ .
$3 \times 2 \times 2$ : the shape $p^2 \times q \times r$ . $2^2 \times 3 \times 5 = 60$ ✓, $2^2 \times 3 \times 7 = 84$ ✓, $3^2 \times 2 \times 5 = 90$ ✓, $2^2 \times 3 \times 11 = 132$ ✗, $2^2 \times 5 \times 7 = 140$ ✗, $5^2 \times 2 \times 3 = 150$ ✗. → $60, 84, 90$ .

Altogether: $60, 72, 84, 90, 96$ , five numbers.

Check: the factors of $60$ are $1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60$ , twelve ✓. And $96 = 2^5 \times 3$ gives $(5 + 1)(1 + 1) = 12$ ✓.

문제Problem 12 도전Challenge 서술형written response

소수가 무한히 많다는 유클리드의 증명을 자신의 말로 다시 써라. 그리고 $2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30{,}031 = 59 \times 509$ 가 소수가 아니라는 사실이 증명을 무너뜨리지 않는 이유를 설명하여라.

Rewrite Euclid's proof that there are infinitely many primes in your own words. Then explain why the fact that $2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30{,}031 = 59 \times 509$ is not prime does not break the proof.

풀이와 채점 기준Solution & grading notes

증명. 소수가 유한 개뿐이라고 가정하고 그 목록을 전부 적는다. 목록의 소수를 모두 곱하고 $1$ 을 더한 수를 $N$ 이라 하자. 목록의 어떤 소수 $p$ 로 $N$ 을 나누어도, 곱한 부분은 $p$ 의 배수이고 $1$ 이 남으므로 나머지가 $1$ 이다. 즉 $N$ 은 목록의 어느 소수로도 나누어떨어지지 않는다. 그런데 $1$ 보다 큰 자연수 $N$ 은 소수이거나 소수인 약수를 갖는다. 그 소수는 $N$ 을 나누므로 목록에 있을 수 없다. 목록에 없는 소수가 존재하니, "목록이 전부"라는 가정이 틀렸다. 따라서 소수는 유한 개일 수 없다.

$30{,}031$ 의 경우. 증명은 " $N$ 이 소수"라고 주장하지 않는다. " $N$ 의 소인수는 목록에 없는 새 소수"라고 주장한다. $30{,}031 = 59 \times 509$ 의 소인수 $59$ 와 $509$ 는 곱한 목록 $2, 3, 5, 7, 11, 13$ 에 없는 소수이므로 증명이 약속한 그대로다. $N$ 이 합성수여도 새 소수를 내놓는다는 점에는 변함이 없다.

채점 기준 (논리가 맞는 다른 풀이도 만점). ① 목록의 곱에 $1$ 을 더한 $N$ 이 목록의 어느 소수로도 나누어떨어지지 않음(나머지 $1$ )을 밝히면 기본 점수. ② $N$ 의 소인수가 목록 밖의 소수라서 모순임을 밝히면 추가 점수. ③ 증명이 " $N$ 이 소수"가 아니라 " $N$ 의 소인수가 새 소수"를 주장한다는 점을 $30{,}031$ 로 설명하면 만점.

Proof. Suppose there are only finitely many primes, and write the complete list. Let $N$ be the product of every prime on the list, plus $1$ . Dividing $N$ by any prime $p$ on the list leaves remainder $1$ , since the product part is a multiple of $p$ and the extra $1$ is left over. So no prime on the list divides $N$ . But $N$ is a whole number greater than $1$ , so it is prime or has a prime factor. That prime divides $N$ , so it cannot be on the list. A prime not on the list exists, contradicting the assumption that the list was complete. Hence the primes cannot be finite in number.

The case of $30{,}031$ . The proof never claims that $N$ is prime. It claims that the prime factors of $N$ are new primes missing from the list. The prime factors of $30{,}031 = 59 \times 509$ , namely $59$ and $509$ , are indeed absent from the list $2, 3, 5, 7, 11, 13$ , exactly as promised. Whether $N$ is prime or composite, it produces a new prime.

Rubric (any logically correct solution earns full credit). ① Showing that $N$ , the product of the listed primes plus $1$ , is divisible by none of them (remainder $1$ ): base credit. ② Showing that a prime factor of $N$ lies outside the list, giving the contradiction: more credit. ③ Explaining through $30{,}031$ that the proof asserts "the prime factors of $N$ are new," not " $N$ is prime": full credit.

경시Contest

대회 스타일competition style

문제Problem 13 경시Contest

$1 \times 2 \times 3 \times \cdots \times 99 \times 100$ 을 계산하면 끝에 $0$ 이 연달아 몇 개 붙는가?

How many zeros are at the end of $1 \times 2 \times 3 \times \cdots \times 99 \times 100$ ?

힌트Hint

끝의 $0$ 하나는 소인수 $2$ 와 $5$ 의 짝 하나에서 나온다. $2$ 는 넉넉하니 $5$ 의 개수를 세면 된다. 소인수분해에서 $5$ 가 몇 번 나오는지, 수 하나하나에 대해 정직하게 세어 보라.

Each trailing zero comes from one pair of prime factors $2$ and $5$ . There are plenty of $2$ s, so count the $5$ s. Count honestly, number by number, how many times $5$ appears in each factorization.

정답과 풀이Answer & solution

정답 ·

24

개

Answer ·

24

곱의 끝에 붙는 $0$ 의 개수는 곱을 소인수분해했을 때 $2$ 와 $5$ 의 짝의 개수, 즉 $2$ 의 개수와 $5$ 의 개수 중 작은 쪽이다. $1$ 부터 $100$ 까지에는 짝수가 $50$ 개나 있어 $2$ 는 $5$ 보다 훨씬 많으므로 $5$ 의 개수만 세면 된다.

$5$ 의 배수 $5, 10, 15, \ldots, 100$ 은 $100 \div 5 = 20$ 개이고, 각각 $5$ 를 적어도 하나씩 준다. 그중 $25, 50, 75, 100$ 은 $25 = 5^2$ 의 배수라서 $5$ 를 하나씩 더 준다. $100 \div 25 = 4$ 개. $125 = 5^3$ 의 배수는 $100$ 이하에 없다.

5\text{의 개수} = 20 + 4 = 24.

따라서 끝에 $0$ 이 $24$ 개 붙는다.

검산: $1$ 부터 $10$ 까지의 곱은 $5$ 가 두 개( $5, 10$ )라서 $0$ 이 두 개였다( $3{,}628{,}800$ ). 같은 셈법이다 ✓. $25$ 를 한 번만 세면 $20$ 개로 틀린다 — $25 = 5 \times 5$ 가 $5$ 를 두 개 낸다는 점이 이 문제의 핵심이다.

The number of trailing zeros is the number of $2$ – $5$ pairs in the prime factorization of the product, that is, the smaller of the number of $2$ s and the number of $5$ s. From $1$ to $100$ there are $50$ even numbers, so the $2$ s vastly outnumber the $5$ s, and only the $5$ s need counting.

The multiples of $5$ , namely $5, 10, 15, \ldots, 100$ , number $100 \div 5 = 20$ , and each contributes at least one $5$ . Among them, $25, 50, 75, 100$ are multiples of $25 = 5^2$ and contribute one extra $5$ each: $100 \div 25 = 4$ . No multiple of $125 = 5^3$ lies within $100$ .

\text{number of } 5\text{s} = 20 + 4 = 24.

So the product ends in $24$ zeros.

Check: the product $1$ through $10$ had two $5$ s ( $5$ and $10$ ) and ended in two zeros ( $3{,}628{,}800$ ), by the same count ✓. Counting $25$ only once would give $20$ , which is wrong; that $25 = 5 \times 5$ supplies two $5$ s is the heart of the problem.