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
  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: