zenith82114   1년 전

옛날에 어느 질문 글에 답변할 때 작성했던 시간 복잡도 증명에 오류가 있음을 깨달아 다시 작성해 봅니다.

아래 Proposition에 의해서, 최대 $n$자리 수까지만 확인하면 됩니다.

**Proposition.**

숫자 $1$을 $k$개 나열해서 만든 수를 $R_k$라고 합시다.

$2, 5$와 서로소인 모든 자연수 $n$에 대하여, $R_k$가 $n$의 배수가 되게 하는 $k$가 $n$ 이하에서 적어도 하나 존재합니다.

**Proof.**

$n=1$일 때는 $k=1$로 정하면 됩니다. 이제 $n \ge 3$만 고려합시다.

등비수열의 합을 이용하면 $R_k = (10^k - 1) / 9$라고 쓸 수 있습니다.

여기서 $k=0$도 허용해서 $R_0 = 0$이라고 정의하고, $R_i$를 $n$으로 나눈 나머지를 $r_i$라 합시다.

모든 $0 \le i \le n$에 대하여 $r_i \in \{ 0, 1, \cdots, n-1 \}$이므로, 비둘기집 원리에 의하여 $r_a = r_b$인 두 정수 $a, b\ (0 \le a \lt b \le n)$가 존재합니다.

모듈로 연산의 성질에 의하여

$$
\begin{align}
0 = r_b - r_a &= (R_b \mod n) - (R_a \mod n) \\
&\equiv R_b - R_a \mod n \\
&\equiv (10^b - 10^a) / 9 \mod n\\
&\equiv 10^a \times (10^{b-a} - 1)/9 \mod n\\
&\equiv 10^a \times R_{b-a} \mod n
\end{align}
$$

가 성립합니다.

여기서 $10^a$는 $10$의 배수 또는 $1$이므로 $n$의 배수일 수 없습니다. ($\because n \ge 3,$ $n$은 $2, 5$와 서로소)

따라서 $R_{b-a} \equiv 0 \mod n$이 성립하며, $k = b-a$로 정하면 $1 \le k \le n$을 만족하므로 증명이 완료됩니다.

댓글을 작성하려면 로그인해야 합니다.