귀류법

소수가 전부 p1,…,pkp_1, \ldots, p_k뿐이라 가정해 보자 — 칩 위에 그 목록, P=p1⋯pkP = p_1 \cdots p_k, 그리고 N=P+1N = P+1이 놓인다. 어떤 목록의 소수로도 나누어떨어지지 않지만(나머지 1) 소인수를 가지는 NN — 그 소인수는 목록 밖에 있다. 모순이다. k=6k = 6에서는 N=30031=59×509N = 30031 = 59 \times 509처럼 합성수여도 증명이 온전함을 보여, 귀류법의 모양(¬P\lnot P 가정 → 모순 → PP)을 익힌다.

N=p1p2⋯pk+1≡1(modpi)N = p_1 p_2 \cdots p_k + 1 \equiv 1 \pmod{p_i}
¬P  ⇒  ⊥  ⊢  P\lnot P \;\Rightarrow\; \bot \;\vdash\; P
30031=59×50930031 = 59 \times 509

예제

유클리드의 정리를 완전히 증명하세요: 소수는 무한히 많다. 귀류법으로 — 소수가 p1,…,pkp_1, \ldots, p_k뿐이라 가정하고, N=p1⋯pk+1N = p_1 \cdots p_k + 1이 (i) N≥2N \ge 2이므로 소인수를 가지고, (ii) 그 소인수가 어떤 pip_i와도 같을 수 없음을 보여 모순을 이끌어내세요. 특히 "NN 자체는 소수일 필요가 없다"는 미묘한 점(k=6k = 6에서는 N=30031=59×509N = 30031 = 59 \times 509)을 다루세요.

N=p1p2⋯pk+1,N≡1(modpi) for all iN = p_1 p_2 \cdots p_k + 1, \qquad N \equiv 1 \pmod{p_i} \ \text{for all } i
k=6:N=30031=59×509k = 6:\quad N = 30031 = 59 \times 509
k=6k = 6: P=30030P = 30030, N=30031=59×509N = 30031 = 59 \times 509 — NN은 합성수지만 소인수 5959와 509509는 모두 목록 {2,3,5,7,11,13}\{2, 3, 5, 7, 11, 13\} 밖에 있는 새 소수.
증명 보기
  1. 귀류법으로 증명합니다. 소수가 유한하다 — 즉 소수의 전체 목록이 p1,…,pkp_1, \ldots, p_k뿐이라 가정하세요 (k≥1k \ge 1). P=p1⋯pkP = p_1 \cdots p_k라 두고 N=P+1N = P + 1로 두면 N≥2⋅1+1=3≥2N \ge 2 \cdot 1 + 1 = 3 \ge 2입니다.
  2. 보조 결과: 2 이상의 모든 정수는 소인수를 가집니다. 증명 (강한 귀납법): n=2n = 2이면 nn 자체가 소수입니다. n>2n > 2이면 nn이 소수이거나 n=abn = ab, 1<a,b<n1 < a, b < n입니다; 합성수인 경우 귀납 가정에 의해 aa가 소인수 qq를 가지고, q∣a∣nq \mid a \mid n이므로 qq가 nn의 소인수입니다. 이를 NN에 적용하면 NN의 소인수 qq가 존재합니다.
  3. qq는 어떤 pip_i와도 다릅니다. 실제로 각 ii에 대해 pi∣Pp_i \mid P이므로 N=P+1≡1(modpi)N = P + 1 \equiv 1 \pmod{p_i}, 즉 pip_i는 NN을 나누지 못합니다. 그런데 q∣Nq \mid N이므로 q≠piq \ne p_i — 모든 ii에 대해 성립합니다. 즉 qq는 목록에 없는 소수이고, "목록이 완전하다"는 가정과 모순입니다. 따라서 소수는 무한히 많습니다. ∎
  4. 미묘한 점: NN 자체가 소수일 필요는 없습니다. k=6k = 6이면 P=2⋅3⋅5⋅7⋅11⋅13=30030P = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 = 30030이고 N=30031=59×509N = 30031 = 59 \times 509는 합성수입니다. 그래도 증명은 온전합니다 — 핵심은 "NN의 소인수는 모두 새 소수"이지 "NN이 새 소수"가 아니기 때문입니다. 한편 이 증명은 새 소수가 NN의 소인수 중 하나라는 것까지는 말해 주지만, 어떤 것인지는 소인수분해를 해야 알 수 있습니다.

귀류법으로 log⁡25\log_2 5가 무리수임을 증명하세요. 힌트: log⁡25=pq\log_2 5 = \frac{p}{q} (p,qp, q는 양의 정수)라 가정하면 2p=5q2^p = 5^q를 얻습니다 — 왼쪽은 짝수이고 오른쪽은 홀수입니다.

log⁡25=pq  ⇒  5=2p/q  ⇒  5q=2p\log_2 5 = \frac{p}{q} \;\Rightarrow\; 5 = 2^{p/q} \;\Rightarrow\; 5^q = 2^p
2p is even (p≥1),5q is odd2^p \text{ is even } (p \ge 1), \qquad 5^q \text{ is odd}
씬 프리셋은 기본값 k=4k = 4 (P=210P = 210, N=211N = 211)입니다 — 이 문제는 씬의 수치가 아니라 귀류법의 구조 자체에 대한 문제입니다.
증명 보기
  1. 귀류법으로 증명합니다. log⁡25\log_2 5가 유리수라 가정하세요. log⁡25>log⁡24=2>0\log_2 5 > \log_2 4 = 2 > 0이므로 log⁡25=pq\log_2 5 = \frac{p}{q} (p,qp, q는 양의 정수)로 쓸 수 있습니다 — 특히 p≥1p \ge 1입니다.
  2. 로그의 정의에서 5=2p/q5 = 2^{p/q}이고, 양변을 qq제곱하면 5q=2p5^q = 2^p입니다. 그런데 p≥1p \ge 1이므로 왼쪽 2p=2⋅2p−12^p = 2 \cdot 2^{p-1}은 짝수이고, 오른쪽 5q5^q는 홀수들의 곱이라 홀수입니다. 짝수와 홀수가 같을 수는 없으므로 모순입니다. 따라서 log⁡25\log_2 5는 무리수입니다. ∎
  3. 참고: pq\frac{p}{q}를 기약분수로 둘 필요는 없습니다 — 짝·홀수 논증만으로 충분합니다. 더 깊은 이유: 산술의 기본정리(소인수분해의 유일성)에 의해 2p2^p의 소인수는 2뿐이고 5q5^q의 소인수는 5뿐이라, 양의 지수를 가진 두 거듭제곱은 결코 같아질 수 없습니다.

귀류법으로 증명하세요: rr이 유리수이고 xx가 무리수이면 r+xr + x도 무리수입니다.

r+x=s∈Q  ⇒  x=s−r∈Qr + x = s \in \mathbb{Q} \;\Rightarrow\; x = s - r \in \mathbb{Q}
씬 프리셋은 기본값 k=4k = 4 (P=210P = 210, N=211N = 211)입니다 — 이 문제는 씬의 수치가 아니라 귀류법의 구조 자체에 대한 문제입니다.
증명 보기
  1. 귀류법으로 증명합니다. r+xr + x가 유리수라 가정하고 s=r+x∈Qs = r + x \in \mathbb{Q}라 두세요. 그러면 x=s−rx = s - r입니다.
  2. 유리수들의 차는 유리수입니다: r=abr = \frac{a}{b}, s=cds = \frac{c}{d} (a,c∈Za, c \in \mathbb{Z}, b,d∈Zb, d \in \mathbb{Z}, b,d≠0b, d \ne 0)이면 x=s−r=cb−adbdx = s - r = \frac{cb - ad}{bd}이고, cb−ad∈Zcb - ad \in \mathbb{Z}, bd≠0bd \ne 0이므로 x∈Qx \in \mathbb{Q}입니다.
  3. 이는 xx가 무리수라는 가정과 모순입니다. 따라서 r+xr + x는 유리수일 수 없고, 즉 무리수입니다. ∎ (같은 논증으로 r≠0r \ne 0인 유리수 rr과 무리수 xx에 대해 rxrx도 무리수임을 보일 수 있습니다: rx=srx = s이면 x=s/rx = s/r은 유리수들의 몫이기 때문입니다.)

1. 증명의 기초