르장드르의 정리(Legendre's theorem)와 쿠머의 정리(Kummer's theorem)

      Comments Off on 르장드르의 정리(Legendre's theorem)와 쿠머의 정리(Kummer's theorem)

소수 p가 주어졌다고 하자. 0이 아닌 임의의 정수 n에 대하여, np진 값매김(p-adic valuation)νp(n)pνn를 나누게 하는 양의 정수 ν 중 가장 큰 수로 정의한다. 또한 νp(0)=로 정의한다. 즉,

νp(n)={max{νN:pνn}ifn0ifn=0

으로 정의된다. 따라서 정의에 의해서 νp(n)n을 소인수분해 했을 때 p의 지수와 같음을 알 수 있다.

르장드르의 정리(Legendre's theorem)
정리. 르장드르의 공식(Legendre's formula)

소수 p가 주어졌다고 하자. 그러면 양의 정수 n에 대하여 νp(n!)은 다음 식을 통해 구할 수 있다.

νp(n!)=i=1npi

증명. 생략..

한 편, 주어진 양의 정수 n에 대한 p진 전개(p-adic expansion)를 생각해 보자. 다시 말해 적당한 a0,,ak{0,1,,p1}가 유일하게 존재하여

n=a0+a1p+a2p2+akpk

와 같이 나타낼 수 있다. 이 때, sp(n)=a0+a1++ak로 정의하자. 즉, sp(n)np진전개 했을 때, 각 자릿수의 합과 같음을 알 수 있다. 일반적으로 νp(n)sp(n) 사이에는 큰 관련이 없지만, νp(n!)sp(n) 사이에는 다음과 같이 밀접한 관련이 있음을 보일 수 있다.

정리. 르장드르의 정리(Legendre's theorem)

소수 p가 주어졌다고 하자. 그러면 양의 정수 n에 대하여 νp(n!)은 다음 식을 통해 구할 수 있다.

νp(n!)=nsp(n)p1

증명. 먼저 np진 전개가 다음과 같이 주어졌다고 하자.

n=a0+a1p+a2p2+akpk

그러면 각각의 1ik에 대하여

npi=ai+ai+1p+ai+2p2++akpki=j=ikajpji

가 성립한다. 따라서 르장드르의 공식에 의해 다음을 얻는다.

νp(n!)=i=1knpi=i=1kj=ikajpji=j=1ki=1jajpji=j=1kajpj1p1=j=0kajpj1p1=1p1(j=0kajpjj=0kaj)◼=1p1(nsp(n))

위 르장드르의 정리에서 p=2인 경우, 특별히 아래와 같이 재미있는 결론을 얻는다. 예를 들어 n=100이라 하면, 100=1100100(2)이므로 s2(100)=3임을 알 수 있다. 따라서 100!의 소인수분해에서의 2의 지수는 ν2(100!)=100s2(100)=1003=97임을 알 수 있다.

따름정리.

임의의 양의 정수 n에 대하여, n!을 소인수분해 했을 때 2의 지수와 n을 이진전개 했을 때 각 자릿수의 합을 더하면 n과 같다. 즉, 다음이 성립한다.

n=ν2(n!)+s2(n)

쿠머의 정리(Kummer's theorem)

소수 p와 두 양의 정수 m,n이 주어졌다고 하자. 이제 mn의 소인수분해에서의 p의 지수는 m의 소인수분해에서의 p의 지수와 n의 소인수분해에서의 p의 지수의 합과 같다. 또한 nm의 소인수분해에서의 p의 지수는 n의 소인수분해에서의 p의 지수에 m을 곱한 값과 같다. 즉,

  1. νp(mn)=νp(m)+νp(n)
  2. νp(nm)=mνp(n)

이 성립한다.

이제 이 사실들을 바탕으로 p진 값매김을 정수에서 유리수로 확장해 보자. 우선 (b)에서 m=1를 대입하면, νp(1n)=νp(n)를 얻는다. 따라서 임의의 두 정수 m,n에 대하여 (단, m0)

νp(mn)=νp(n)νp(n)

으로 정의하는 것이 자연스럽다. 실제로 유리수에 대한 p진 값매김을 위와 같이 정의하면 정수에 대한 p진 값매김의 자연스러운 확장이 된다.

위와 같이 유리수로 확장한 p진 값매김과 르장드르의 정리를 이용하면 다음 쿠머의 정리(Kummer's theorem)를 간단히 보일 수 있다.

정리. 쿠머의 정리(Kummer's theorem)

소수 p가 주어졌다고 하자. 그러면 두 양의 정수 m,n에 대하여 다음 식이 성립한다.

νp((m+nn))=sp(m)+sp(n)sp(m+n)p1

여기서 위 식의 우변은, p진법에서 mn을 더할 때의 '자리 올림'의 횟수와 같다.

증명. 르장드르의 정리에 의해,

νp((m+nn))=νp((m+n)!m!n!)=νp((m+n)!)νp(m!)νp(n!)=(m+n)sp(m+n)p1msp(m)p1nsp(n)p1=sp(m)+sp(n)sp(m+n)p1

이 성립한다..

위 정리를 적용하기 위하여 p=2이고 m=n=100인 경우를 생각해 보자. 100=1100100(2)이고

1100100(2)+1100100(2)=11001000(2)

의 계산 과정에서 3번의 '자리 올림'이 발생하므로 ν2((200100))3임을 알 수 있다.

정리.

임의의 양의 정수 n에 대하여, 다음과 같이 정의되는 카탈란 수(Catalan number)

Cn=1n+1(2nn)

은 언제나 정수값을 가진다. (즉, n+1(2nn)을 나눈다.)

증명. 소수 pn+1의 소인수 중 하나라 하자. 또한 적당한 양의 정수 k에 대하여 νp(n+1)=k라 하자. 그러면 n+1p진전개를

n+1=ala1a000k-times

와 같이 나타낼 수 있다. 여기서 a00이다. 그러므로 np진전개는

ala1(a01)(p1)(p1)k-times

와 같다. 따라서 p진법에서 n+n을 계산할 때, 적어도 k번의 '자리 올림'이 발생한다. 즉,

νp(n+1)=kνp((2nn))

이 성립한다. 이는 n+1의 모든 소인수가 (2nn)의 소인수임을 뜻하므로 n+1(2nn)을 나눈다..