Posts Tagged ‘ 정수 ’

2010 JMO #2

2. k를 양의 정수, m을 홀수로 놓는다. 이 때, n^n - m2^k의 배수가 되게 하는 n이 존재함을 보여라.

수학적 귀납법. base case는 자명하고.. 1^1,3^3,\cdots,(2^k-1)^{2^k-1}가 mod 2^k1,3,\cdots,2^k-1이 됨을 가정하자. 임의의 홀수 1 \leq m \leq 2^k-1에 대해 (2^k+m)^{2^k+m} \equiv m^{2^k+m} \equiv m^m\text{ (mod }2^k\text{)}가 된다. (페르마의 정리나 오일러의 정리에 의해 임의의 홀수 x에 대해 x^{2^{k-1}} \equiv 1\text{ (mod }2^k\text{)}가 됨을 확인할 수 있다.) 한 편 (2^k+m)^{2^k+m} = m^{2^k+m} + \binom{2^k+m}{1} m^{2^k+m-1} 2^k + \binom{2^k+m}{2} m^{2^k+m-2} 2^{2k} + \cdots
\equiv m^{2^k+m} + (2^k+m)m^{2^k+m-1} 2^k \equiv m^m + 2^k\text{ (mod }2^{k+1}\text{)}가 되므로 mod 2^k에서 mod 2^{k+1}로 옮겨지는 과정에서 역시 모든 홀수가 나온다. 끝

귀납법 안쓰는 풀이 없을까나.. 한 방에 풀리는 풀이

Advertisements

2010 Iran NMO #1

2010 Iran NMO 풀이 마지막.

1. a,b는 두 양의 정수로 a > b이다. \gcd(a-b,ab+1)=1임과 \gcd(a+b,ab-1)=1이 알려져 있을 때. (a-b)^2+(ab+1)^2는 완전제곱수가 아님을 보여라.

(a-b)^2+(ab+1)^2=(a+b)^2+(ab-1)^2=(a^2+1)(b^2+1)임을 이용한다. 만약 완전제곱수라 가정하자. 이 때 소수 pa^2+1,b^2+1을 나눈다고 가정하자. 즉 a^2 \equiv b^2 \equiv -1\text{ (mod }p\text{)}가 된다. 따라서 a \equiv \pm b가 된다. 만약 a-b \equiv 0이라면 맨 위의 식에서 p^2(a-b)^2+(ab+1)^2를 나눔에서 pab+1도 나누는데 이는 a-b,ab+1이 서로 소임에 모순. 마찬가지로 a+b \equiv 0ab-1p의 배수가 되어 서로 소란 가정에 모순이 된다. 따라서 a^2+1,b^2+1은 서로 소인데 곱이 완전제곱수이므로 각각이 제곱수가 된다. 그런데 a^2+1이 제곱수인 양의 정수 a는 없으니까 모순. 끝

전반적으로 문제들이 쉬운 감이 없지 않았다. 적어도 KMO가 더 어려워보인다. ㅠ

2010 KMO #8

이차잉여인간과 함께하는 이차잉여 문제!

8. 원탁에 2010명의 사람이 둥글게 앉아 있다. 어떤 사람에게 과자를 주고, 그 사람으로부터 시계방향으로 1번째, 1+2번째, 1+2+3번째, …, 1+2+…+2009번째 사람에게 과자를 주었다. 이 때, 과자를 하나 이상 받은 사람의 수를 구하여라.

이런 문제도 예전에 어디선가 봤었는데..

각설 답은 408개. 사실 이런 문제는 2010 대신 더 작은 수를 대입해서 앞에 몇 개 좀 해보면 바로 감이 잡히기 마련. mod 2010으로 \frac{n(n+1)}{2}들이 총 몇 개 나오는지를 구하는 문제이다. 이들은 \frac{n(n+1)}{2} = \frac{(2n+1)^2-1}{8}이므로 홀수의 제곱수들과 연관이 깊다.

먼저 mod 1005로 이차잉여가 몇 개있는지를 본다. 이건 중국인의 나머지 정리가 해결해준다. 다행히도 1005는 홀수인 소수들의 곱으로 무승수이다. (3, 5, 67의 곱) 홀수의 소수에 대해선 이차잉여가 어떻게 나오는지 잘 안다. 구체적으로 p가 홀수인 소수이면 이차잉여\frac{p+1}{2}개가 나온다. 그러면 서로 다른 홀수 소수 p,q에 대해 mod pq이차잉여는 몇 개인가? \frac{p+1}{2}\frac{q+1}{2}가 된다. 왜냐면 먼저 pq에 대해 이차잉여인 것은 mod p나 mod q로 봐도 이차잉여가 되어야 하고, 역으로 mod p이차잉여 하나 택해 x라 하고 mod q이차잉여 하나 택해 y라 하면 a^2 \equiv x\text{ (mod }p\text{)}, b^2 \equiv y\text{ (mod }q\text{)}a,b를 찾을 수 있고, 그러면 c \equiv a\text{ (mod }p\text{)}, c \equiv b\text{ (mod }q\text{)}c를 mod pq에서 찾으면 x,y에 해당되는 mod pq의 이차잉여를 찾을 수 있기 때문이다. 마찬가지로 생각하면, mod 1005로 이차잉여의 개수는 2 \cdot 3 \cdot 34=204개가 된다.

한 편, 홀수 k에 대해 mod k이차잉여 개수를 q라 하자. (현재 k=1005, q=204) 그러면 우리가 관심있는 것은 홀수인 이차잉여 mod 2k이므로 x^2 \equiv 1\text{ (mod }2\text{)}x^2 \equiv 0^2,1^2,\cdots\text{ (mod }k\text{)}의 해를 찾으면 되는데 앞의 것의 해는 x \equiv 1\text{ (mod }2\text{)}밖에 없으므로 개수는 그냥 q가 된다. 그럼 이런 홀수 제곱수들에서 1을 뺀 후 8로 나눈 것들을 봐야하는데, 1로 빼면 짝수들 mod 2k이고, 2로 먼저 나누면 어떤 수들 mod k가 된다. (not 2k) 그러면 하나 더 확인해줘야할 사실은 임의의 a에 대해 \frac{a(a+1)}{2} \equiv k+ \frac{b(b+1)}{2}\text{ (mod }2k\text{)}b가 존재하겠냐는 것. 그런 b2k-a-1로 넣으면 된다.

즉, 각각의 홀수 이차잉여 mod 2k마다 1을 빼주고 2로 나누면 그 값들은 mod k로 총 q개가 나오고, 이를 mod 2k로 볼 때에 각각의 수들은 그 수와 그 수에 k를 더한 것 모두 나오게 되어 총 개수는 2q가 된다. 따라서 답은 2q=408.

깔끔하고 좋은 문제이긴 한데, 어디서 봤던 것 같은데 흠..

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개 이상의 소인수를 갖는다.

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

2010 USA TST #9

얼마 전에 Zuming Feng에게서 올해 미국 TST 문제를 받았다. 이번 TST에는 꽤 흥미로운 문제들이 많았는데, 다음 문제가 그 중 하나였다.

p=6k+1이면서 \binom{3k}{k} \equiv 1 (\text{mod } p)인 소수 p는 존재하는가?

이 문제가 생각보다 어렵다. 사실 넘버링에서 알 수 있듯이, 9번이라 함은 세 번째 날의 3번, 즉 어려운 포지션에 해당되는 문제인데, 평소 알고 있는 접근법으로 시도하면 많은 방법으론 실패함을 깨달을 수 있다. 이 문제의 풀이는 나중에 공개하도록 하겠다. 한 번 직접 고민해보고 풀이를 찾아보자. 임금님 귀는 당나귀 귀!!!!

키 포인트는 뿌리근이다. 특히 뿌리근이 x^N=1을 만족하는 복소수, 즉 primitive roots of unity들과 비슷한 존재라는 것에 포인트가 있다. 그런데 이걸 어떻게 써먹어야 하는가?

경시 문제를 풀다가 생성함수에서 복소수를 이용하는 경우 가끔 이런 경험이 있을 것이다. f(x)란 생성함수 (혹은 무한급수) 가 주어져 있을 때, f(1)+f(\omega)+f(\omega^2)+\cdots+f(\omega^{N-1})을 계산하면 N의 배수에 해당하는 항들만 남고 나머지는 사라지는 것을 이용하는 것 말이다. 이 아이디어를 조금 확장하여 이 문제에서 응용하기로 한다.

먼저 \text{mod }p의 뿌리근 g를 잡는다. 그리고 \displaystyle \sum_{i=1}^{k} (g^{6i}+1)^{3k}를 계산한다. 페르마의 소정리에 의해 임의의 0이 아닌 수 a에 대해 a^{6k} \equiv 1 (\text{mod }p)이므로 a^{3k} \equiv \pm 1 (\text{mod }p)을 얻는다. 따라서 위의 값은 (\text{mod }6k+1)로 볼 때 -k,-k+1,\cdots,-1,0,1,\cdots,k-1,k가 되어야 한다.

하지만 \displaystyle \sum_{i=1}^{k} (g^{6i}+1)^{3k}을 전개하면, (g^{6i}+1)^{3k}에서 0,k,2k,3k번째를 제외한 나머지 항들은 전부 없어지며 이 네 개의 항들은 k번 더해진다. 곧, \equiv k(\binom{3k}{0}+\binom{3k}{k}+\binom{3k}{2k}+\binom{3k}{3k})가 된다. 따라서 귀류법을 써 \binom{3k}{k} \equiv 1(\text{mod }p)라고 가정하면, 이 값은 (\text{mod }6k+1)4k가 되어야 한다. 이는 앞에서 이 값이 -k,-k+1,\cdots,-1,0,1,\cdots,k-1,k가 되어야 한다고 했으므로, 모순이 나온다.

위에선 담담한 문체로 썼지만, 사실 이 문제 꽤 어렵다. 이 방법을 찾아내는 것이 어려워서. 실제로 이번 2010년 IMO 대표애들과 같이 푸는데 대략 사흘 정도를 아무도 해결하지 못한 채로 넘겼다. 사실은 이 풀이도 누군가가 풀어서 알게된 것이 아니라 오피셜을 주워 들은 것이라..