2010 KMO #1

1. 양의 정수 7^{2^{20}}+7^{2^{19}}+1은 소수인 약수를 21개 이상 가짐을 보여라.

인수분해를 이용한 정수 문제. 기본 키 포인트는 x^4+x^2+1=(x^2+x+1)(x^2-x+1). 이를 이용하면 7^{2^{n+1}} - 7^{2^{n}}+1=A_n이라 할 때 주어진 값은 A_{18} A_{17} \cdots A_0 (7^{2^1} + 7^{2^0}+1)이 된다.

먼저 A_i,A_j가 서로 소임을 보인다. ij보다 작다고 하자. 소수 p가 둘을 나눈다고 하자. 그러면 p|7^{3 \cdot 2^i}+1p|7^{3 \cdot 2^j}+1이 되는데 이는 곧 7^{3 \cdot 2^i} \equiv -17^{3 \cdot 2^j} \equiv -1을 의미한다. 그런데 두 번째 식을 j-i번 제곱하면 7^{3 \cdot 2^i} \equiv 1이 되어 mod p1 \equiv -1이 되어 p=2가 된다. 그런데 저 값들은 홀수이므로 모순. 따라서 A_i,A_j는 서로 소이다.

이와 비슷하게 A_i7^{2^1} + 7^{2^0}+1가 서로 소임을 보일 수 있다. (7^{3 \cdot 2^0} \equiv 1이므로 7^{3 \cdot 2^i} \equiv 1가 됨. 이는 7^{3 \cdot 2^i} \equiv -1에 모순.) 따라서 이들을 나누는 소인수들은 전부 다른데 A_i들은 총 19개 있고 마지막 수는 57로 두 개의 소인수를 가져 총 21개 이상의 소인수를 갖는다.

비슷한 유형은 많았는데 그런 종류의 아이디어를 쓰면 된다. 깔끔한 문제.

Advertisements
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: