도쿄대 2021-4(문과, 이과)

 

 

 

 

(1) 양의 정수 $A, B$ 와 양의 홀수 $K, L$ 이 $KA=LB$를 만족한다. 그리고 $K$를 4로 나눈 나머지와 $L$을 4로 나눈 나머지가 같다. 이 때, $A$를 4로 나눈 나머지와 $B$를 4로 나눈 나머지가 같음을 보여라.

 

(2) 양의 정수 $a,b$ ($a> b$) 와 $A=_{4a+1} C_{4b+1}$,$B = _{a} C_{b}$에 대해  $KA=LB$ 를 만족하는 양의 홀수 $K, L$ 이 존재함을 보여라.

 

(3) 양의 정수 $a, b$ $(a> b)$ 에 대해 $a-b$가 2로 나누어 떨어지면, $_{4a+1} C_{4b+1}$ 을 4로 나눈 나머지와 $_aC_b$ 를 4로 나눈 나머지가 같음을 보여라.

 

(4) $_{2021} C_{37}$ 을 4로 나눈 나머지를 구하여라.

 

---

생각해보기)

 

정수론 파트가 약하다면 (1) 번부터 어렵게 느낄 수 있는데, (1)에서 나머지를 구하는 아이디어를 충분히 숙지하고 있어야 (3) 번 까지 완벽히 이해할 수 있을 것 같다. 자세히 말하자면 $AB$를 4로 나눈 나머지는 $A$를 4로 나눈 나머지와 $B$를 4로 나눈 나머지를 곱한 것을 다시 4로 나눈 나머지와 같다는 아이디어를 말하는 것이다. (문장력이 부족해서 죄송하지만 매우 중요한 포인트이다.)

 

 

 

풀이)

 

(1)

  $K, A, B$ 를 4로 나눈 나머지를 각각 $k, r_1, r_2$ 라고 하고, $r_1=r_2$ 를 증명하자. 문제의 가정에 의해 $L$ 을 4로 나눈 나머지도 $k$ 이고 $k$는 1 또는 3 이다. 그리고 $KA$ 와 $LB$ 를 4로 나눈 나머지는 $kr_1$ 와 $kr_2$ 를 4로 나눈 나머지와 각각 일치한다. ($K=4p+k, A=4q+r_1$ 로 놓고 곱해서 4로 묶어보면 쉽게 알 수 있다.)

  이제 $KA=LB$ 라는 가정으로부터 $kr_1$ 와 $kr_2$ 를 4로 나눈 나머지가 같다는 결론에 이르게 되고, 다시 말해 $k(r_1-r_2)$ 가 4의 배수라는 얘기가 된다. 그런데 $k$ 는 1 또는 3 이기 때문에 $r_1-r_2$ 가 4의 배수일 수밖에 없다. 따라서 $r_1=r_2$ 가 증명된다.

 

 

(2) 

 

  $A= \cfrac{(4a+1)(4a)\cdots(4a-4b+1)}{(4b+1)(4b)\cdots 2 \cdot 1}$

$= \cfrac{(4a+1)(4a-1)\cdots(4a-4b+1)}{(4b+1)(4b-1)\cdots 3 \cdot 1} \times \cfrac{(4a)(4a-2)\cdots(4a-4b+2)}{(4b)(4b-2)\cdots 4 \cdot 2}$ $= \cfrac{(4a+1)(4a-1)\cdots(4a-4b+1)}{(4b+1)(4b-1)\cdots 3 \cdot 1} \times \cfrac{(4a)(4a-4)\cdots(4a-4b+4)}{(4b)(4b-4)\cdots 8 \cdot 4} \times \cfrac{(4a-2)(4a-6)\cdots(4a-4b+2)}{(4b-2)(4b-6)\cdots 6 \cdot 2}$

$= \cfrac{(4a+1)(4a-1)\cdots(4a-4b+1)}{(4b+1)(4b-1)\cdots 3 \cdot 1} \times \cfrac {a(a-1)\cdots(a-b+1)}{b(b-1)\cdots 2\cdot 1} \times \cfrac{(2a-1)(2a-3)\cdots(2a-2b+1)}{(2b-1)(2b-3)\cdots 3 \cdot 1}$ $= \cfrac{(4a+1)(4a-1)\cdots(4a-4b+1)}{(4b+1)(4b-1)\cdots 3 \cdot 1} \times B \times \cfrac{(2a-1)(2a-3)\cdots(2a-2b+1)}{(2b-1)(2b-3)\cdots 3 \cdot 1}$

 

  즉, $K=(4b+1)(4b-1) \cdots 1 \cdot (2b-1)(2b-3) \cdots 1$, $L=(4a+1)(4a-1) \cdots (4a-4b+1) \cdot (2a-1)(2a-3) \cdots (2a-2b+1)$ 에 대하여 $KA=LB$ 이다.

 

 

(3) 

 

  (1)에 의해 우리는 (2)에서 구한 $K,L$을 4로 나눈 나머지가 서로 같음을 보이면 충분하다. 이제 앞에서 구한 $K,L$을 면밀히 살펴보자.

 

$K=(4b+1)(4b-1) \cdots 1 \cdot (2b-1)(2b-3) \cdots 1$

$L=(4a+1)(4a-1) \cdots (4a-4b+1) \cdot (2a-1)(2a-3) \cdots (2a-2b+1)$

 

  (2)번에서 $K,L$을 구하는 과정을 잘 따라왔다면 $K,L$이 $(2b+1)+b = 3b+1$ 개의 항의 곱이라는 걸 알 수 있다.

처음 $(2n+1)$ 개의 항은 4로 나눈 나머지가 $1,3,1,3, \cdots , 3,1$ 으로 일치한다. 

이제 뒤에 $b$ 개의 항들을 살펴보자.

$(2a-1)-(2b-1)=2(a-b)$ 인데 가정에 의해 $a-b$가 2의 배수 이므로 $2(a-b)$는 4의 배수가 된다. 다시 말해 $2a-1$과 $2b-1$을 4로 나눈 나머지가 일치한다. 완전히 똑같은 논리로 나머지 $b-1$ 개의 항에 대해서도 나머지가 일치한다고 할 수 있다.

 

  정리하면, $K,L$을 이루는 각 항들을 4로 나눈 나머지가 순서대로 일치하므로 $K,L$ 을 4로 나눈 나머지가 일치하고 (1)에 의해 $A,B$ 도 4로 나눈 나머지가 일치한다.

 

 

(4)

 

  이제 우리가 힘들게 증명한 (3)을 적용하기만 하면 된다.

$a=505, b=9$에 대해 $_{2021} C_{37}$을 4로 나눈 나머지는 $_{505} C_{9}$를 4로 나눈 나머지와 일치하고,

$a=126, b=2$에 대해 $_{505} C_{9}$를 4로 나눈 나머지는 $_{126} C_{2}$를 4로 나눈 나머지와 일치한다.

$_{126} C_{2}=63 \times 125$

              $=(60+3)(124+1)$

를 4로 나눈 나머지는 3이다.