어려운 정수론 문제 2개

 

 

문제1: 소수 \(p\)와 양의 정수 \(a_1, a_2, ... , a_p\)에 대하여 다음 조건을 만족하는 양의 정수 \(k\)가 존재함을 보여라. 

    $$ a_1+k, a_2+2k, ... , a_p+pk $$

            를 \(p\)로 나눈 나머지들이 적어도 \(p/2\)개 이상의 서로 다른 값를 갖는다. 

[2018 USAMO P4]

 

(sol)

\(k=1, 2, ... , p\)에 대해 무향그래프 \(G=G_1, G_2, ... , G_p\) 를 구성하자.

\(a_i\)에 해당하는 점을 \(i\)로 둔다. 

 

\(a_i+ik\equiv a_j+jk \quad(\textup{mod} \; p) \)를 만족하면 점 \(i\)와 \(j\)를 잇는다. (단, \(i < j\))

이 때,

$$ a_i+ik\equiv a_j+jk \;(\textup{mod} \; p)\; \Leftrightarrow \quad k\equiv (a_i-a_j)(j-i)^{-1}\; (\textup{mod} \; p) $$

이므로, 고정된 \(a_i, a_j\)에 대해 선분 \(ij\)는 그래프 \(G_1, G_2, ..., G_p\)에서 정확히 1번만 등장한다. 

(\(j-i\)값은 \(1\)이상 \(p-1\)이하의 값이고, 이 값들은 모두 \(p\)와 서로소이므로, 유일한 역원이 존재한다.)

 

따라서 모든 \((a_i, a_j)\)쌍에 대해 선분 개수는 정확히  \(\binom{p}{2}\)개 존재한다. 

 

따라서 비둘기집 원리에 의해, 어떤 그래프 \(G_x\)는 최대 \( \binom{p}{2}/p=(p-1)/2 \)개의 선분을 갖는다.

 

즉, 최대 \((p-1)/2\)개의 같은 쌍들이 존재하므로, 나머지 부분들은 총 \((p+1)/2\)개 이상이 되고,

이들의 나머지는 모두 다르게 된다. 

 

 

문제2: 모든 양의 정수 \(s\)에 대해 각자리 숫자의 합이 \(s\)이고 원래 값이 \(s\)의 배수가 되는 

            양의 정수 \(n\)이 반드시 존재함을 증명하여라.  

 

 

(hint)

\(10^{\phi(s)}\equiv 1 \;(\textup{mod} \; s) \) 단, \((s, 10)=1 \)

 

(sol)

\(s=2^a5^b\times C \)로 쓰자. 이 때, \(gcd(10, C)=1\)이다.

이제 \(N=10^{a+b}(10^{\phi(C)}+10^{2\phi(C)}+...+10^{C\phi(C)})\)가 문제조건에 맞음을 보이자. 

우선, \(2^a5^b | 10^{a+b}\)이다. 또한 \(10^{\phi(C)}\equiv 1 \;(\textup{mod} \; C) \)이므로, 

$$ 10^{\phi(C)}+10^{2\phi(C)}+...+10^{C\phi(C)}\equiv C\equiv 0 \;(\textup{mod} \; C) $$

이다. 따라서 두 식을 곱하면, \(s|N\)이 되어 문제 조건을 만족한다.