수학 문제 훈련 1

23 Jun 2026

여기 있는 일부 문제들을 조금 변형해서 풀어보려고 한다.

좀 틀리는 법을 알아야할 것 같다, 나는.

1

소수는, 자연수에서 약수를 1과 자신만 갖는 수라 하자.
소수가 무한히 많음을 증명하시오

prooof.

우선, 1도 아니고, 소수도 아니라면, 1이 아닌 두 수로의 분해가 가능하다.

유한하다고 가정하고, $p_1, \cdots p_k$

$N_1: p_1, \cdots p_k + 1$은 소수가 아니며, $p_i$로 나눌 수 없다.

$N_1$의 약수는 모두 소수로 나눌 수 없음, 나눌수 있다면 모순.

$N$은 무한히 쪼개서 , 무한히 줄일수 있는데, 이는 모순.

역으로 이야기를 해보면, 임의의 수 N에 대해서, 1~N까지의 소수를 싸그리 곱하고, 위 개짓거리를 하면? 새로운 소수를 갖습니다. 아니 애당초, p_1, p_2,… p_k + 1은 이전까지의 약수에선 소수를 가질수 엇ㅄ음..

아니, 이건 ,분해를 할때, 반드시 소수에 도달할수 밖에 없다는걸 논하는게 맞는거같다.

2

산술의 기본 정리. 모든 자연수가 유일한 소수들의 조합으로 인수분해됨을 보이시오.

• 귀납법 사용 금지.
• 즉 보이는건, 임의의 모든 숫자가 소수들의 곱으로써 표현될 수 있다는것

인수분해의 존재성과, 유일성.

일단 제일 간단한 통찰은, n은 스스로가 1이나 소수면 끝, 합성수면 쪼개자. n에서 숫자를 쪼개고 내려가는 함수. 그리고, 함수는 감소열. 소수를 만나는 순간, 정지. 그리고 , 합성수는, 최솟값인 4가 있다.

즉, 하강열은, 결국, 끝이 온다.

정수 n에서, 다음과 같은 알고리즘을 생각해보자.

S에서, 제일 큰 숫자대로 정렬-유지.

숫자가 1이나 소수면, 추출

숫자가 합성수면, 분해, 즉 하나를 숫자 2개로.

중요한건, 다음 스텝 이후에, 남아있다면, 최댓값은, 언제나 반드시, 감소.

그래서, 프로그램이 무한히 반복될순 없고, n번이면 무조건 끝남.

그리고, 추출되는 수는 언제나 소수들이고

이들의 곱은 불변량.

따라서, 소인수분해가 됩니다.

그리고 소인수분해한 소수 리스트를 오름차순으로 나열했다.

제일 작은 두 소수. a, b.

a | b1~bn이니까, b<=a b | a1~bn이니까, a>=b a= b, 양쪽 날리고, 소수 리스트 길이는 줄었고, 곱은 같다는 사실은 그대로. 감소는 반복되며, 결국 언젠가는 끝남.

그리고, 프로그램이 이렇게 끝난 순간에, 두 곱이 라는 개념이 같다라는건, 둘중 하나는 1이고, 같으니 둘다 1. 즉, 동시종료. 여태까지 다 같았다. 따라서, 리스트 같음,. 소인수분해는 유일함.

3

p

ab -> p

a or p

b, p는 소수 a, b는 자연수

이거 생각보다 까다로움. a=kp+r, b =lp+s

p가 둘다 안나누고 곱한건 나눈다고 치자.

ab = xp + rs = kp tp = rs. 중요한거, t는 정수. 0< r,s < p, p|rs 라는거다.

rs = tp니까, p|rm이 되는 최소의 자연수 m을 잡자. m<=s < p 이며, p-qm = a 라 하면 r(p-qm)=ra, 둘다 p로 나뉜다. p|rm이 되는 최소 자연수 m, a< m이라 a=0. m|p이다. 근데, r < p 라 m != 1. 근데 1 < m < p. 즉 p는 합성수-> 모순.

이건 ai 도움 받았음, 생각보다 존나 어려운 문제엿따.

뭔가, 구조적으로 하한을 잡는 테크닉이 되게 도움이될때가 많다는 느낌이네.

3-1.

gcd(a,b) 를 둘을 동시에 나누는 애라 할때, gcd(a, ka + b) = gcd(a, b)인거 보이기.

음, 한쪽 나누면 , a’+kb’이고, 반대편도 딱 똑같이 대칭적으로 해서 되는듯?

이게 제일 간단한 풀이. 더 좋은 풀이는 모르겠다-대칭적인 구조를 논하는거 외에는.

A := { n in N: a=na’, b=nb’인 a’, b’존재.} B := { n in N: a=na’, b+ka=nc’인 a’, c’존재.}

a	n이면 b랑 b+ka를 n으로 나눈 나머지는 동일함, 둘다 0이 아니면 포함 안됨, 0이면 포함이라 동치조건.

4.

램지 정리 R(3,3)=6 증명, n-완전 그래프에서 색 2^n가지 칠하면 무조건 파랑이나 빨강 삼각형. 존재하는 최소숫자.

이거 결국 당일날은 못품, 다음날로.