์ฝ์ ๊ณ์ฐ๊ธฐ๋ก ๋ฌด์์ ํ ์ ์๋์?
์ด ์ฝ์ ๊ณ์ฐ๊ธฐ๋ ์ ์ ํ๋๋ฅผ ์ ๋ ฅํ๋ฉด ๋ ๊ฐ์ง ๊ฒฐ๊ณผ๋ฅผ ์ฆ์ ๋ณด์ฌ ์ค๋๋ค. ๋ฐ๋ก ๊ทธ ์์ ๋ชจ๋ ์ฝ์์ ์์ธ์๋ถํด ๊ฒฐ๊ณผ์ ๋๋ค. ์ฝ์๋ ์ด๋ค ์๋ฅผ ๋๋์ด๋จ์ด์ง๊ฒ ํ๋, ์ฆ ๋๋จธ์ง๊ฐ 0์ด ๋๋ ์ ์๋ฅผ ๋งํฉ๋๋ค. ์์ธ์๋ ๊ณฑํ์ ๋ ์๋์ ์๊ฐ ๋๋ ์์(prime number)๋ค๋ก, ๊ทธ ์๋ฅผ ์ด๋ฃจ๋ ๊ฐ์ฅ ๊ธฐ๋ณธ์ ์ธ ๊ตฌ์ฑ ์์๋ผ๊ณ ํ ์ ์์ต๋๋ค. ์์ ๋ฅผ ํ ๋, ๋ถ์๋ฅผ ์ฝ๋ถํ ๋, ์ต๋๊ณต์ฝ์๋ฅผ ์ฐพ์ ๋, ๋๋ ์์ ์ฑ์ง์ ์ดํด๋ณผ ๋ ๋๋ฃจ ์ธ ์ ์๋ ํธ๋ฆฌํ ๋๊ตฌ์ ๋๋ค.
์ฌ์ฉ ๋ฐฉ๋ฒ
์ ๋ ฅ๋์ ๋จ ํ๋, "์ฝ์๋ฅผ ๊ตฌํ ์:" ํญ๋ชฉ๋ฟ์ ๋๋ค. ์ ์(์์๋ ์์๋ )๋ฅผ ์ ๋ ฅํ๋ฉด ๋๋จธ์ง ๊ณ์ฐ์ ๊ณ์ฐ๊ธฐ๊ฐ ์์์ ์ฒ๋ฆฌํฉ๋๋ค. ์ด ๋๊ตฌ๋ ์ ๋๊ฐ์ ๊ธฐ์ค์ผ๋ก ๊ณ์ฐํ๋ฏ๋ก ๊ฒฐ๊ณผ๋ก ๋์ค๋ ์ฝ์๋ ํญ์ ์์์ ๋๋ค. ์ฒ๋ฆฌ ๊ฐ๋ฅํ ๋ฒ์๋ ์ต๋ 18์๋ฆฌ์ ์ ์(์์ ๋๋ ์์)์ด๋ฉฐ, ๊ทธ๋ณด๋ค ๊ธด ์๋ ๊ณ์ฐ๋์ง ์์ต๋๋ค.
- 0์ ํน์ํ ๊ฒฝ์ฐ๋ก ์ฒ๋ฆฌ๋์ด 0์ ๋ฐํํฉ๋๋ค.
- ์์๋ ์ ๋๊ฐ์ ์ฌ์ฉํฉ๋๋ค(์: -12๋ 12์ ๋์ผํ ์ฝ์๋ฅผ ๊ฐ์ง๋๋ค).
๊ณ์ฐ ์๋ฆฌ
์ด ๊ณ์ฐ๊ธฐ๋ ์ ๋ ฅํ ์๊น์ง ๋ชจ๋ ์ซ์๋ฅผ ์ผ์ผ์ด ํ์ธํ๋ ๋์ , 1๋ถํฐ ๊ทธ ์์ ์ ๊ณฑ๊ทผ๊น์ง๋ง ๋ฐ๋ณตํฉ๋๋ค. ๋๋์ด๋จ์ด์ง๋ ๊ฐ ๊ฐ i๋ง๋ค i์ ๊ทธ ์ง์ด ๋๋ ๋ชซ(์ รท i)์ ํจ๊ป ๊ธฐ๋กํฉ๋๋ค. ์ด ์ ๊ณฑ๊ทผ ๋ฐฉ์์ ์ฝ์๋ฅผ ์์ผ๋ก ์ฐพ๊ธฐ ๋๋ฌธ์ ํฐ ์์ผ์๋ก ํจ์ฌ ๋น ๋ฆ ๋๋ค. ๊ฒฐ๊ณผ๋ ์ค๋ณต์ ์ ๊ฑฐํ ๋ค ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ๋ฉ๋๋ค. ์์ธ์๋ถํด์๋ ๊ฒ์ฆ๋ ์์ ์ฒ๋ฆฌ ์๊ณ ๋ฆฌ์ฆ(Apache Commons Math)์ ์ฌ์ฉํด ์ ๋๊ฐ์ ์์ธ์๋ค๋ก ๋ถํดํฉ๋๋ค.
$$\text{Factors} = \left\{\, d \in \mathbb{Z}^{+} : \text{Number} \bmod d = 0 \,\right\}$$
์ค์ ์์
36์ ์ ๋ ฅํด ๋ด ์๋ค. ๋ฐ๋ณต์ 1๋ถํฐ 7๊น์ง ์งํ๋ฉ๋๋ค(\(\sqrt{36} = 6\)์ ๋ง ๋๋ ์ง์ ๊น์ง):
- 1์ 36์ ๋๋์ด๋จ์ด์ง๊ฒ ํจ โ 1๊ณผ 36 ๊ธฐ๋ก
- 2๋ 36์ ๋๋์ด๋จ์ด์ง๊ฒ ํจ โ 2์ 18 ๊ธฐ๋ก
- 3์ 36์ ๋๋์ด๋จ์ด์ง๊ฒ ํจ โ 3๊ณผ 12 ๊ธฐ๋ก
- 4๋ 36์ ๋๋์ด๋จ์ด์ง๊ฒ ํจ โ 4์ 9 ๊ธฐ๋ก
- 6์ 36์ ๋๋์ด๋จ์ด์ง๊ฒ ํจ โ 6 ๊ธฐ๋ก(์ง๋ 6์ด๋ฏ๋ก ํ ๋ฒ๋ง)
์ ๋ ฌํ๋ฉด ์ฝ์๋ 1, 2, 3, 4, 6, 9, 12, 18, 36 ์ ๋๋ค. ์์ธ์๋ 2, 2, 3, 3 ์ ๋๋ค(\(2 \times 2 \times 3 \times 3 = 36\)์ด๊ธฐ ๋๋ฌธ).
์ถ๊ฐ ํ์ด ์์
์์ 1: ์์ ์ ๋ ฅ๊ฐ(29)
๊ณ์ฐ๊ธฐ๋ ์์ ์ ๊ณฑ๊ทผ๊น์ง์ ์ฝ์๋ง ๊ฒ์ฌํฉ๋๋ค. ์ฌ๊ธฐ์ \(\sqrt{29} \approx 5.39\)์ด๋ฏ๋ก ๋ฐ๋ณต๋ฌธ์ i = 1, 2, 3, 4, 5๋ก ์คํ๋ฉ๋๋ค.
- \(29 \bmod 1 = 0\)์ด๋ฏ๋ก 1์ ์ฝ์์ด๋ฉฐ (1, 29) ์์ ๋ง๋ญ๋๋ค.
- \(29 \bmod 2 = 1\), \(29 \bmod 3 = 2\), \(29 \bmod 4 = 1\), \(29 \bmod 5 = 4\)์ ๋๋ค. ๋ชจ๋ 0์ด ์๋๋ฏ๋ก 2โ5๋ ์ฝ์๊ฐ ์๋๋๋ค.
29์ ์ฝ์: 1, 29. ์ฝ์๊ฐ ์ ํํ ๋ ๊ฐ์ด๋ฏ๋ก 29๋ ์์์ด๋ฉฐ, ์์ธ์๋ถํด๋ ๊ทธ๋ฅ \(29\)์ ๋๋ค.
์์ 2: ์์ ์ ๋ ฅ๊ฐ(โ60)
์ฝ์๋ ์์ ์ฝ์๋ก ์ ์๋๋ฏ๋ก ๊ณ์ฐ๊ธฐ๋ ์ ๋๊ฐ์ ์ฌ์ฉํฉ๋๋ค: \(|-60| = 60\). \(\sqrt{60} \approx 7.75\)์ด๋ฏ๋ก ๋ฐ๋ณต๋ฌธ์ i = 1๋ถํฐ 7๊น์ง ์คํ๋ฉ๋๋ค.
| i | 60 mod i | ์ฐพ์ ์ |
|---|---|---|
| 1 | 0 | (1, 60) |
| 2 | 0 | (2, 30) |
| 3 | 0 | (3, 20) |
| 4 | 0 | (4, 15) |
| 5 | 0 | (5, 12) |
| 6 | 0 | (6, 10) |
| 7 | 4 | โ |
์ ๋ ฌ๋ ์ฝ์: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60 (12๊ฐ). ์์ธ์: 2, 2, 3, 5์ด๋ฏ๋ก
$$60 = 2 \times 2 \times 3 \times 5 = 2^2 \times 3 \times 5$$ํ์ธ: \(2 \times 2 = 4\), \(4 \times 3 = 12\), \(12 \times 5 = 60\). ์์ ์ฝ์(โ1, โ2, โฆ , โ60)๋ โ60์ ๋๋์ง๋ง, ๊ณ์ฐ๊ธฐ๋ ์์ ์ฝ์๋ง ๋์ดํฉ๋๋ค.
์์ 3: ํฐ ๋น์ ๊ณฑ์ ์ ๋ ฅ๊ฐ(210)
\(\sqrt{210} \approx 14.49\)์ด๋ฏ๋ก ๋ฐ๋ณต๋ฌธ์ i = 1๋ถํฐ 14๊น์ง ๊ฒ์ฌํฉ๋๋ค. 210์ ์ ํํ ๋๋๋ ๊ฐ๋ค์ ๋ค์๊ณผ ๊ฐ์ ์์ ๋ง๋ญ๋๋ค:
| i(์์ ์ฝ์) | 210 รท i(์ง์ ์ด๋ฃจ๋ ์ฝ์) |
|---|---|
| 1 | 210 |
| 2 | 105 |
| 3 | 70 |
| 5 | 42 |
| 6 | 35 |
| 7 | 30 |
| 10 | 21 |
| 14 | 15 |
4, 8, 9, 11, 12, 13์ ๋๋จธ์ง๊ฐ ๋จ์ผ๋ฏ๋ก ์ฝ์๊ฐ ์๋๋๋ค. ์์ ์ฝ์์ ์ง์ ์ด๋ฃจ๋ ์ฝ์๋ฅผ ์์๋๋ก ํฉ์น๋ฉด ์ ์ฒด ๋ชฉ๋ก์ด ๋ฉ๋๋ค:
1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 70, 105, 210 (16๊ฐ).
์์ธ์๋ถํด: \(210 = 2 \times 3 \times 5 \times 7\). ๋ค์ ๊ณฑํด ๋ณด๋ฉด: \(2 \times 3 = 6\), \(6 \times 5 = 30\), \(30 \times 7 = 210\). ๊ฒ์ฐ์ผ๋ก, ์ฝ์ ๊ฐ์ ๊ณต์ \((1+1)(1+1)(1+1)(1+1) = 16\)์ ๋ชฉ๋ก๊ณผ ์ผ์นํฉ๋๋ค.
๊ฒฐ๊ณผ ํด์ํ๊ธฐ
์์, ํฉ์ฑ์ ๋๋ ๋ ๋ค ์๋
- ์ฝ์๊ฐ ์ ํํ ๋ ๊ฐ(1๊ณผ ๊ทธ ์ ์์ )์ด๋ฉด ๊ทธ ์๋ ์์์ ๋๋ค. ์: 29 โ 1, 29.
- ์ฝ์๊ฐ ๋ ๊ฐ๋ณด๋ค ๋ง์ผ๋ฉด ๊ทธ ์๋ ํฉ์ฑ์์ ๋๋ค. ์: 12 โ 1, 2, 3, 4, 6, 12.
- 1์ ์ฝ์๊ฐ ํ๋(์๊ธฐ ์์ )๋ฟ์ด๋ฏ๋ก ์์๋ ํฉ์ฑ์๋ ์๋๋๋ค.
์ฝ์์ ๊ฐ์๊ฐ ํ์์ด๋ฉด ์์ ์ ๊ณฑ์
์ฝ์๋ ๋ณดํต \((d, n/d)\) ์์ผ๋ก ๋ํ๋ฉ๋๋ค. ๊ฐ์๊ฐ ํ์๊ฐ ๋๋ ค๋ฉด ์ด๋ค ์ฝ์ ํ๋๊ฐ ์๊ธฐ ์์ ๊ณผ ์ง์ ์ด๋ค์ผ ํ๋ฉฐ, ์ด๋ \(d = n/d\), ์ฆ \(d^2 = n\)์ผ ๋ ์ผ์ด๋ฉ๋๋ค. ์๋ฅผ ๋ค์ด 36์ ์ (1, 36), (2, 18), (3, 12), (4, 9), (6, 6)์ ๊ฐ์ง๋๋ค. 6์ ํ ๋ฒ๋ง ์ธ๋ฏ๋ก 36์ ์ฝ์๋ 9๊ฐ์ ๋๋ค. ๊ฐ์๊ฐ ํ์์ด๋ฉด ๊ทธ ์๋ ์์ ์ ๊ณฑ์์ด๊ณ , ์ง์์ด๋ฉด ์๋๋๋ค.
์์ธ์๋ถํด๋ก ์ฝ์ ๊ฐ์ ์ธ๊ธฐ
\(n = p^a \times q^b \times \dots\)์ด๊ณ \(p, q, \dots\)๊ฐ ์๋ก ๋ค๋ฅธ ์์์ด๋ฉด, ์ฝ์์ ๊ฐ์๋
$$d(n) = (a+1)(b+1)\cdots$$\(36 = 2^2 \times 3^2\)์ ๊ฒฝ์ฐ: \(d(36) = (2+1)(2+1) = 3 \times 3 = 9\). ์ด๋ฅผ ํตํด ์ฝ์ ๋ชฉ๋ก์ด ์์ ํ์ง ํ์ธํ ์ ์์ต๋๋ค.
์์ ์
์๊ธฐ ์์ ์ ์ ์ธํ ์ง์ฝ์(๋ชจ๋ ์ฝ์์์ ๊ทธ ์ ์์ ์ ๋บ ๊ฒ)์ ํฉ์ด ๊ทธ ์์ ๊ฐ์ ๋, ๊ทธ ์๋ฅผ ์์ ์๋ผ๊ณ ํฉ๋๋ค:
- 6: \(1 + 2 + 3 = 6\)
- 28: \(1 + 2 + 4 + 7 + 14 = 28\)
- 496: \(1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248 = 496\)
์ง์ฝ์์ ํฉ์ด ๊ทธ ์๋ณด๋ค ์์ผ๋ฉด ๋ถ์กฑ์, ๋ ํฌ๋ฉด ๊ณผ์์๋ผ๊ณ ํฉ๋๋ค(12๋ ๊ณผ์์์ ๋๋ค: \(1+2+3+4+6 = 16\)).
๋ ์ฝ์ ๋ชฉ๋ก ํ์ฉ: ์ต๋๊ณต์ฝ์์ ๋ถ์ ์ฝ๋ถ
๋ ์์ ์ฝ์๋ฅผ ๊ฐ๊ฐ ๊ตฌํฉ๋๋ค. ๋ ์๊ฐ ๊ณต์ ํ๋ ๊ฐ์ฅ ํฐ ์ฝ์๊ฐ ์ต๋๊ณต์ฝ์(GCD)์ ๋๋ค. 36๊ณผ 48์ ๊ฒฝ์ฐ:
- 36: 1, 2, 3, 4, 6, 9, 12, 18, 36
- 48: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48
๊ณตํต ์ฝ์๋ 1, 2, 3, 4, 6, 12์ด๋ฏ๋ก GCD(36, 48) = 12์ ๋๋ค. ๋ถ์๋ฅผ ์ฝ๋ถํ๋ ค๋ฉด ๋ถ์์ ๋ถ๋ชจ๋ฅผ ์ต๋๊ณต์ฝ์๋ก ๋๋๋๋ค:
$$\frac{36}{48} = \frac{36 \div 12}{48 \div 12} = \frac{3}{4}$$๊ณตํต ์ฝ์๊ฐ 1๋ฟ์ด๋ฉด ๋ ์๋ ์๋ก์์ด๋ฉฐ, ๊ทธ ๋ถ์๋ ์ด๋ฏธ ๊ธฐ์ฝ๋ถ์์ ๋๋ค.
๊ณตํต ์์ ์ฝ์ (1โ30)
์ฝ์์ ๊ฐ์๋ ํญ์ ์์ธ์๋ถํด์์ (์ง์ + 1)์ ๊ณฑ๊ณผ ๊ฐ์ต๋๋ค. ์ฝ์์ ๊ฐ์๊ฐ ํ์์ธ ์๋ ์์ ์ ๊ณฑ์์ ๋๋ค.
| n | ๋ชจ๋ ์ฝ์ | ์ฝ์์ ๊ฐ์ | ์์ธ์๋ถํด | ์ ํ |
|---|---|---|---|---|
| 1 | 1 | 1 | โ (๋น ๊ณฑ) | ์์๋ ํฉ์ฑ์๋ ์๋; ์์ ์ ๊ณฑ์ |
| 2 | 1, 2 | 2 | 2 | ์์ |
| 3 | 1, 3 | 2 | 3 | ์์ |
| 4 | 1, 2, 4 | 3 | 2ยฒ | ํฉ์ฑ์; ์์ ์ ๊ณฑ์ |
| 5 | 1, 5 | 2 | 5 | ์์ |
| 6 | 1, 2, 3, 6 | 4 | 2 ร 3 | ํฉ์ฑ์(์์ ์) |
| 7 | 1, 7 | 2 | 7 | ์์ |
| 8 | 1, 2, 4, 8 | 4 | 2ยณ | ํฉ์ฑ์ |
| 9 | 1, 3, 9 | 3 | 3ยฒ | ํฉ์ฑ์; ์์ ์ ๊ณฑ์ |
| 10 | 1, 2, 5, 10 | 4 | 2 ร 5 | ํฉ์ฑ์ |
| 11 | 1, 11 | 2 | 11 | ์์ |
| 12 | 1, 2, 3, 4, 6, 12 | 6 | 2ยฒ ร 3 | ํฉ์ฑ์ |
| 13 | 1, 13 | 2 | 13 | ์์ |
| 14 | 1, 2, 7, 14 | 4 | 2 ร 7 | ํฉ์ฑ์ |
| 15 | 1, 3, 5, 15 | 4 | 3 ร 5 | ํฉ์ฑ์ |
| 16 | 1, 2, 4, 8, 16 | 5 | 2โด | ํฉ์ฑ์; ์์ ์ ๊ณฑ์ |
| 17 | 1, 17 | 2 | 17 | ์์ |
| 18 | 1, 2, 3, 6, 9, 18 | 6 | 2 ร 3ยฒ | ํฉ์ฑ์ |
| 19 | 1, 19 | 2 | 19 | ์์ |
| 20 | 1, 2, 4, 5, 10, 20 | 6 | 2ยฒ ร 5 | ํฉ์ฑ์ |
| 21 | 1, 3, 7, 21 | 4 | 3 ร 7 | ํฉ์ฑ์ |
| 22 | 1, 2, 11, 22 | 4 | 2 ร 11 | ํฉ์ฑ์ |
| 23 | 1, 23 | 2 | 23 | ์์ |
| 24 | 1, 2, 3, 4, 6, 8, 12, 24 | 8 | 2ยณ ร 3 | ํฉ์ฑ์ |
| 25 | 1, 5, 25 | 3 | 5ยฒ | ํฉ์ฑ์; ์์ ์ ๊ณฑ์ |
| 26 | 1, 2, 13, 26 | 4 | 2 ร 13 | ํฉ์ฑ์ |
| 27 | 1, 3, 9, 27 | 4 | 3ยณ | ํฉ์ฑ์ |
| 28 | 1, 2, 4, 7, 14, 28 | 6 | 2ยฒ ร 7 | ํฉ์ฑ์(์์ ์) |
| 29 | 1, 29 | 2 | 29 | ์์ |
| 30 | 1, 2, 3, 5, 6, 10, 15, 30 | 8 | 2 ร 3 ร 5 | ํฉ์ฑ์ |
1๋ถํฐ 30 ์ฌ์ด์ ์์๋ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29์ด๊ณ , ์์ ์ ๊ณฑ์๋ 1, 4, 9, 16, 25์ ๋๋ค. ์ฝ์๊ฐ ๊ฐ์ฅ ๋ง์ ์๋ 24์ 30์ผ๋ก, ๊ฐ๊ฐ 8๊ฐ์ ๋๋ค.
์์ฃผ ๋ฌป๋ ์ง๋ฌธ
์ฝ์์ ์์ธ์๋ ์ด๋ป๊ฒ ๋ค๋ฅธ๊ฐ์? ์ฝ์๋ ์ ๋ ฅํ ์๋ฅผ ๋๋์ด๋จ์ด์ง๊ฒ ํ๋ ๋ชจ๋ ์์ ๋๋ค. ๋ฐ๋ฉด ์์ธ์๋ ๊ณฑํ์ ๋ ๊ทธ ์๊ฐ ๋๋ ์์๋ค๋ง์ ๊ฐ๋ฆฌํต๋๋ค. 36์ ๊ฒฝ์ฐ ์ฝ์์๋ 12, 18 ๊ฐ์ ํฉ์ฑ์๋ ํฌํจ๋์ง๋ง, ์์ธ์๋ 2, 2, 3, 3๋ฟ์ ๋๋ค.
์์๋ฅผ ์ ๋ ฅํ๋ฉด ์ ์์ ์ฝ์๊ฐ ๋์ค๋์? ๊ณ์ฐ๊ธฐ๊ฐ ์ ๋๊ฐ์ ๊ธฐ์ค์ผ๋ก ๋์ํ๊ธฐ ๋๋ฌธ์ -12์ 12๋ ๋์ผํ ์์ ์ฝ์ ๋ชฉ๋ก์ ๋ณด์ฌ ์ค๋๋ค.
์ ๋ ฅํ ์ ์๋ ์์ ํฌ๊ธฐ์ ์ ํ์ด ์๋์? ๋ค, ์์ต๋๋ค. ์ซ์๋ ์ต๋ 18์๋ฆฌ(์์ ๋๋ ์์)๊น์ง ์ ๋ ฅํ ์ ์์ต๋๋ค.