[정수론](9)[ϕ(m) 계산 & 중국인의 나머지 정리]

오일러 ϕ 함수와 중국인의 나머지 정리

ϕ(m) 계산하기

m = 소수 p

• ϕ(m) = m-1
• 증명
  m을 제외한 모든 수가 서로소임

m = p^k

• ϕ(m) = ϕ(p^k) = p^(k-1)*(p-1)
• 증명
  1~p^k 중 p의 배수를 뺴면 된다.
  즉, p^k - p^(k-1)이다.

m = p^i * q^j (p, q는 소수)

• ϕ(m) = ϕ(p^i * q^j) = ϕ(p^i) * ϕ(q^j)
• 증명

-> m이 합성수라면 각 인수의 ϕ의 곱으로 계산할 수 있다.

중국인의 나머지 정리

m, n이 정수일 때 gcd(m, n) = 1이라면
임의의 정수 b, c에 대해 연립합동방정식
x ≡ b (mod m), x ≡ c (mod n)은 0 <= x <mn 사이에서 정확히 1개의 해를 가진다.

• 증명
  x ≡ b (mod m)의 해는 x = mk + b꼴, 이걸 다시 x ≡ c (mod n)에 대입해
  mk + b ≡ c (mod n) = mk ≡ c - b (mod n)
  선형합동방정식의 정리에 의해 0<=k<n을 만족하는 유일한 해가 존재한다.
  따라서 x = mk + b는 0<=x<=mn 사이에서 유일한 해를 가진다.
• 응용
  연립합동방정식의 최소 해를 구할 때 사용 가능하다.
  어느 한 합동방정식에 대해 풀고, 그 꼴의 식을 다시 대입하고...
  그리고 구한 해를 mn... 에 대한 합동으로 구해 그 범위 내의 식을 구하고
  그게 해당 범위의 유일한 해이므로 가장 작은 수가 된다.