Claude Code 2.1.299 · Sonnet 5.5 · 생각 깊이 중간. 답과 파일 내용은 그대로 옮겼고, 컴퓨터 안 경로만 <작업 폴더>로 가렸습니다.
문제 1 (귀류법·거짓 명제)
problem.md
다음 두 문제를 풀어라. (1) √2 + √3 이 무리수임을 귀류법으로 증명하라. (√2, √3 이 무리수라는 사실은 증명 없이 써도 된다.) (2) 모든 자연수 n 에 대하여 n² + n + 41 이 소수임을 증명하라.
문제 1 · 플러그인 없이
대화 답
## (1) √2 + √3 은 무리수이다 **증명 (귀류법).** √2 + √3 = r 이 유리수라고 가정한다. √2 + √3 > 0 이므로 r > 0 이다. √3 = r − √2 의 양변을 제곱하면 3 = r² − 2r√2 + 2 이다. 이를 정리하면 √2 = (r² − 1) / (2r) 이다. r 이 0이 아닌 유리수이므로 우변은 유리수다. 그러면 √2 가 유리수가 되어 √2 가 무리수라는 사실에 모순이다. 따라서 √2 + √3 은 무리수이다. ∎ ## (2) 이 명제는 거짓이다 n² + n + 41 이 모든 자연수 n 에 대해 소수인 것은 아니므로, 증명할 수 없다. 반례가 있다. - **n = 40**: 40² + 40 + 41 = 1681 = 41² 이므로 합성수다. - **n = 41**: 41² + 41 + 41 = 41·(41 + 1 + 1) = 41·43 이므로 합성수다. n = 1, 2, …, 39 에서는 모두 소수가 나온다. 이 성질은 오일러가 발견한 것으로 유명하다. 그래서 n = 40 부터 깨진다는 점이 더 눈에 띈다. 소수가 나오는 구간이 길어도, 식이 모든 n 에 대해 소수를 준다는 증명은 되지 못한다. 참고로 비상수 정수계수 다항식이 모든 자연수에서 소수값만 갖는 경우는 없다. 일반적으로 f(n₀) = p 가 소수이면 f(n₀ + kp) 는 p 의 배수다. 이 값이 p 보다 크면 합성수다.
문제 1 · /math-proof:solo
대화 답
답안은 `<작업 폴더>/solo-1/math-proof-solo/proof.md`에 썼습니다. (1)은 증명했고, (2)는 명제가 거짓이라 증명이 불가능합니다. - **(1)** √2+√3 = r이 유리수라고 가정합니다. 그러면 √3 = r − √2의 양변을 제곱해 √2 = (r²−1)/(2r)을 얻습니다. 이 값은 유리수이므로 √2가 무리수라는 사실에 모순입니다. - **(2)** n = 40이면 n²+n+41 = 1681 = 41²이고, n = 41이면 41·43입니다. 둘 다 합성수라서, "모든 자연수 n에 대해 소수"라는 명제는 반례가 있어 거짓입니다. n = 0부터 39까지는 모두 소수입니다.
math-proof-solo/notes.md
# Notes (1) r=√2+√3 rational ⇒ √2=(r²−1)/(2r) rational, contradiction. (2) False as stated: n=40 gives 1681=41²; n=41 gives 41·43. Disprove. Status: proof.md written; complete.
math-proof-solo/proof.md
# 풀이 ## (1) √2 + √3 은 무리수이다 **증명 (귀류법).** √2 + √3 이 유리수라고 가정하고 r = √2 + √3 이라 하자. r > 0 이다. √3 = r − √2 의 양변을 제곱하면 3 = r² − 2r√2 + 2, 즉 2r√2 = r² − 1 이다. r > 0 이므로 √2 = (r² − 1) / (2r). r 이 유리수이므로 오른쪽 변도 유리수이다(유리수끼리의 사차연산, 분모 2r ≠ 0). 따라서 √2 가 유리수가 되어, √2 가 무리수라는 사실에 모순이다. 그러므로 √2 + √3 은 무리수이다. ∎ (√3 이 무리수라는 사실은 사용하지 않았다.) ## (2) 주어진 명제는 거짓이다 "모든 자연수 n 에 대하여 n² + n + 41 이 소수이다"는 **참이 아니므로 증명할 수 없다.** 반례가 있다. - n = 40: 40² + 40 + 41 = 1600 + 40 + 41 = 1681 = 41² (41 은 소수이므로 1681 은 합성수). - n = 41: 41² + 41 + 41 = 41·(41 + 1 + 1) = 41·43 (합성수). 일반적으로 n = 41k 형태의 수에서는 n² + n + 41 이 41 의 배수이면서 41 보다 크므로 합성수이다. 따라서 명제는 거짓이다. (참고: n = 0, 1, …, 39 에 대해서는 n² + n + 41 이 모두 소수이다(오일러의 소수 생성 다항식). 그러나 이것은 유한 번의 계산으로 확인되는 사실일 뿐, 모든 자연수로 확장되지 않는다.)
문제 2 (1990 국제수학올림피아드 3번)
problem.md
2ⁿ + 1 이 n² 으로 나누어떨어지는 양의 정수 n 을 모두 구하고, 그것 말고는 없음을 증명하라.
문제 2 · 플러그인 없이
대화 답
**답: n = 1, n = 3.** (이 문제는 IMO 1990 3번으로 알려진 문제입니다.)
**확인.** n=1이면 2¹+1=3이고 1²=1로 나누어떨어집니다. n=3이면 2³+1=9이고 3²=9로 나누어떨어집니다.
**다른 해가 없음의 증명.** n>1이고 n² | 2ⁿ+1이라 하겠습니다.
1. **n은 홀수입니다.** 2ⁿ+1은 홀수이므로 n도 홀수입니다.
2. **n의 가장 작은 소인수는 3입니다.**
- p를 n의 가장 작은 소인수라 하면 p는 홀수이고 p | 2ⁿ+1입니다.
- 따라서 2ⁿ ≡ −1이고 2²ⁿ ≡ 1 (mod p)입니다.
- p를 법으로 한 2의 위수를 d라 하면 d | 2n이고, 페르마의 소정리에 의해 d | p−1입니다.
- n의 모든 소인수는 p 이상이므로 gcd(n, p−1)=1이고, 따라서 gcd(2n, p−1) | 2입니다.
- 그러므로 d=1 또는 2이고, p는 2¹−1=1 또는 2²−1=3을 나눕니다. 따라서 p=3입니다.
3. **3은 n에 정확히 한 번만 들어갑니다.**
- n=3ᵏm (k≥1, 3∤m)이라 하겠습니다.
- n이 홀수이므로 LTE(지수 승 보조정리)에서 v₃(2ⁿ+1)=v₃(2+1)+v₃(n)=1+k입니다.
- n² | 2ⁿ+1이므로 2k ≤ 1+k, 즉 k=1입니다. 따라서 n=3m이고 3∤m입니다.
4. **m=1입니다.**
- m>1이라 가정하고, q를 m의 가장 작은 소인수라 하겠습니다. n은 홀수이고 3∤m이므로 q≥5입니다.
- 2번과 같은 논법으로, q를 법으로 한 2의 위수 d는 2n=6m과 q−1을 모두 나눕니다. m의 소인수는 모두 q 이상이므로 gcd(6m, q−1) | 6입니다.
- 따라서 d | 6이고 q | 2ᵈ−1 ∈ {1, 3, 7, 63}입니다. q≥5이므로 q=7입니다.
- 그런데 2의 거듭제곱은 mod 7에서 1, 2, 4만 나오고 −1≡6은 나오지 않습니다. 이는 7 | 2ⁿ+1에 모순입니다.
- 따라서 m=1이고 n=3입니다.
이상에서 조건을 만족하는 양의 정수는 n=1과 n=3뿐입니다. ∎문제 2 · /math-proof:solo
대화 답
증명을 `<작업 폴더>/h-solo-1/math-proof-solo/proof.md`에 썼습니다. 문제를 완전히 해결했고, 남은 부분은 없습니다. 답은 n = 1, 3입니다. 증명은 네 단계입니다. 1. 2ⁿ+1이 홀수이므로 n도 홀수입니다. 2. n의 최소 소인수 p는 2의 위수를 이용해 3임을 보입니다. 3. 지수 올림 보조정리(LTE)로 v₃(n) = 1을 얻습니다. 4. n = 3m이고 m > 1이면, m의 최소 소인수 q가 위수 논증으로 모순에 이릅니다. 따라서 m = 1이고 n = 3입니다. n = 1(2+1 = 3)과 n = 3(2³+1 = 9 = 3²)이 조건을 만족하는 것도 직접 확인했습니다.
math-proof-solo/notes.md
Answer n=1,3. Plan: smallest prime p|n is 3 (order argument), LTE gives v3(n)=1, then smallest prime q of n/3 impossible. Writing proof.md.
math-proof-solo/proof.md
# 답: n = 1, 3
**확인.** n=1: 2+1=3 은 1로 나누어떨어진다. n=3: 2³+1=9 는 3²=9 로 나누어떨어진다.
**다른 해가 없음.** n>1 이 n² | 2ⁿ+1 을 만족한다고 하자.
**(0) n은 홀수.** 2ⁿ+1 은 홀수이므로 n² 도 홀수, 따라서 n 도 홀수.
**기호.** 홀수 소수 r 에 대해 d_r = ord_r(2) 를 2 의 mod r 위수라 하자. r | 2ⁿ+1 이면 2ⁿ ≡ −1 이고 −1≢1 (r 홀수) 이므로 2²ⁿ ≡ 1, 즉 d_r | 2n. 또 d_r ∤ n (d_r | n 이면 2ⁿ≡1≢−1). 또한 페르마에 의해 d_r | r−1.
**(1) n의 최소 소인수 p 는 3.** p | n, p 는 홀수 소수. d_p 는 2n 과 p−1 을 모두 나눈다. n 의 모든 소인수는 ≥p 이고 p−1 의 소인수는 모두 <p 이므로 gcd(n, p−1)=1, 따라서 gcd(2n, p−1) | 2, 즉 d_p ∈ {1,2}. d_p=1 이면 p | 2−1=1 불가능. d_p=2 이면 p | 2²−1=3, 즉 p=3.
**(2) v₃(n)=1.** n 이 홀수이므로 LTE(지수 올림 보조정리)에 의해 v₃(2ⁿ+1)=v₃(2+1)+v₃(n)=1+v₃(n). n² | 2ⁿ+1 이므로 2v₃(n) ≤ 1+v₃(n), 즉 v₃(n) ≤ 1. (1)에서 v₃(n) ≥ 1 이므로 v₃(n)=1.
**(3) n=3.** n=3m, 3∤m 이라 쓰자. m>1 이라 가정하고 q 를 m 의 최소 소인수라 하면 q ≥ 5 (홀수이고 3 이 아님). q | 2ⁿ+1 이므로 d_q | gcd(2n, q−1). n=3m 의 소인수는 3 과 q 이상의 소수뿐이고 q−1 의 소인수는 모두 q 미만이므로 gcd(n, q−1) | 3, 따라서 d_q | 6. 그리고 d_q ∤ n.
- d_q=1, 3: d_q | n 이므로 모순.
- d_q=2: q | 3, 모순 (q≥5).
- d_q=6: q | 2⁶−1=63=3²·7, q≥5 이므로 q=7. 그러나 2³=8≡1 (mod 7) 이므로 d₇=3≠6, 모순.
따라서 m=1, 즉 n=3.
**결론.** 조건을 만족하는 양의 정수는 n=1 과 n=3 뿐이다. ∎