[정수론](5)[산술의 기본정리]

인수분해와 산술의 기본정리

소수 p가 p|ab이면, p|a 또는 p|b여야 한다

• 증명
  만약 p|a 이면 참이므로 증명 끝
  만약 p|a가 아니면
      gcd(p, a)|p이므로, gcd(a, p) = 1 or p
      gcd(p, a)|a이므로 gcd(a, p) = 1
      선형방정식의 정리에 의해 ax+py=1을 만족하는 x, y존재.
      양변에 b를 곱하면, bax+bpy=b
      p|pb, p|ab이므로 방정식의 우변인 b에 대해서도 p|b다.

소수의 가약성: p|a1*a2*...*an 이면 p는 a중 적어도 1개를 나눈다

• 증명
  p|a1이라면 참이므로 증명 끝
  만약 p|a1가 아니면
      앞에서 증명한 정리에 따라, p|a1(a2a3...ar)에서 p|a2a3...ar을 만족해야 한다.
  이걸 r번 반복해 p가 a중 적어도 1개를 나눈다는 걸 알 수 있다.

모든 자연수는 소수들의 곱으로 유일하게 표현될 수 있다.

• 모든 자연수는 소수의 곱으로 표현 가능 증명
  강한 수학적 귀납법으로 증명해보자~
  1. 초기값: 2
     2 = 2이므로 참
  2. N보다 작거나 같은 모든 양의 정수 n에 대해 모두 성립한다 가정할 때, N+1에서 성립?
     만약 N+1 = 소수라면
         N+1 = N+1이므로 참
     만약 N+1 = 합성수라면
         N+1 = n1*n2일때 2 <= n1, n2 <= N인 n1, n2가 존재
         이떄 n1, n2 <= N이므로 가정에 의해 n1, n2도 소수의 곱으로 표현된다.
     따라서 강한 수학적 귀납법으로 참이다.
• 모든 자연수를 소수의 곱으로 표현한 것이 유일 증명
  (즉, 재배열하면 무조건 같은 형식으로 표현된다.)
  n이 2가지 방법의 소수의 곱으로 표현된다 가정
  n = p1p2p3...pr = q1q2q3...qs
  따라서 p1|n = p1|q1q2q3...qs
  소수의 가약성에 의해 p1|qi인 qi 존재, p, q는 소수이므로 p1 = qi
  이후 p1, qi를 약분하고 이 논리를 계속 적용한다면,
  1 = q(r+1)q(r+2)...qs 에서 남는 q가 소수라면 모순이므로
  r = s, q들은 p를 재배열한 것과 같다.

우리가 잘 아는 자연수 집합 N에서는 유일한 소인수분해 표현이 있다.
그러나, 짝수들만 모인 짝수집합 E에서는 성립하지 않는다.

• 짝수집합 소인수분해 비유일성 예시
  짝소수: 어떤 p가 짝약수로 나누어지지 않음 (6, 12... 등 홀수도 섞여있는 수)
  180 = 6*30 = 18*10
  180은 여러가지의 짝소수의 소인수분해로 표현할 수 있다.

산술의 기본 정리

n>=2인 모든 정수 n은
n = p1*p2*...*p (p = 소수)로 표현되며 그 표현은 재배열을 제외하면 유일하다.
(단, pi 는 중복 가능하다)