Posts Tagged ‘ Hensel’s Lemma ’

Hensel’s Lemma

Hensel’s Lemma, 헨젤의 보조정리(혹은 Lifting Lemma)라는 것이 잘 알려져 있다. 그 내용은 다음과 같다.

다항식 f(x)와 소수 p에 대해, 어떤 정수 a가 있어 만약 f(a) \equiv 0\text{ (mod }p\text{)}이고 f'(a) \not\equiv 0\text{ (mod }p\text{)}이면 임의의 양의 정수 n에 대해 f(x) \equiv 0\text{ (mod }p^n\text{)}x\text{mod }p^n에서 유일하게 찾을 수 있다.

Proof. 증명 자체는 간단하다. 수학적 귀납법으로, 그런 x가 존재하며 동시에 x \equiv a\text{ (mod }p\text{)}임을 증명한다. n=1인 경우는 자명하고, n일 때의 성립을 가정하자. 즉 f(b) \equiv 0\text{ (mod }p^{n}\text{)}b가 유일하게 존재함을 가정한다. 그러면 f(b+kp^n)을 계산하자. 그를 위해 f(x)=c_nx^n+\cdots+c_1x+c_0이라 하자. 그러면 f(b+kp)-f(b) \equiv p^n f'(b)\text{ (mod }kp^{n+1}\text{)}임을 쉽게 알 수 있다. f'(b) \equiv f'(a)\text{ (mod }p\text{)}는 0이 아니므로 이 값은 k가 변함에 따라 p개의 서로 다른 값을 내놓는다. 그 중 하나는 반드시 \text{(mod }p^{n+1}\text{)}로 0이어야 하므로, 증명이 끝난다.

p^n에서 p^{n+1}로 ‘올린’다는 의미로 ‘Lifting’ Lemma로 불린다. 참고로 lifting은 여기에서뿐만이 아닌 Algebraic Number Theory에서도 나오는데 (사실 거의 똑같은 의미) 아마 이 개념의 일반화가 아닐지. (아니면 원래 저 개념이 있은 뒤에 간단한 경우로 specialization한 것일수도 있겠는데.. 자세한 이야기는 잘 모르겠다.)

이것을 직접적으로 이용하는 문제들도 있지만, 아이디어만을 이용해서 간접적으로 쓰는 문제들도 많다. 다음은 그런 문제들 중 (극히) 일부.

1. (2010 USA TST #1) 정수계수 다항식 P(x)P(0)=0\gcd(P(0),P(1),P(2),\cdots)=1을 만족한다고 하자. 이 때 다음을 만족시키는 양의 정수 n이 무수히 많음을 보여라.

\gcd(P(n)-P(0),P(n+1)-P(1),P(n+2)-P(2),\cdots)=n

2. (2008 Putnam) p는 소수이며, h(x)는 정계수 다항식으로 h(0),h(1),\cdots,h(p^2-1)\text{(mod }p^2\text{)}으로 서로 다르다고 한다. 이 때 h(0),h(1),\cdots,h(p^3-1) 역시 \text{(mod }p^3\text{)}으로 서로 다름을 보여라.

Advertisements