일단 규칙을 찾아봅시다. 1이 a개 있는 수는 어떻게 표현이 될까요?

10^(a-1) + 10^(a-2) + ... + 10 + 1

이렇게 표현이 되겠죠?

1이 b개 있는 수는 10^(b-1) + 10^(b-2) + ... + 10 + 1

이렇게 표현이 될 거고요.

1이 a개 있는 수의 배수가 될려면 어떤 조건을 만족해야 할까요?

(10^(a-1) + 10^(a-2) + ... + 10 + 1) * Q 꼴로 표현이 가능해야겠지요.

적절하게 변형을 먼저 해 봅시다.

(10^(a-1) + 10^(a-2) + ... + 10 + 1) * (10^a) + (10^(a-1) + 10^(a-2) + ... + 10 + 1)

= 10^(2a-1) + ... + 10 + 1

이런 꼴로 되어야 하지 않을까요?

1이 a개 있는 수와 1이 2a개 있는 수의 약수겠네요.

1이 a개 있는 수와 1이 b개 있는 수가 있습니다.

a<b라고 가정해 봅시다. a와 b가 서로소 관계라면 어떻게 될까요?

a와 b가 서로소라면 b=aQ+r (단 r은 1보다는 크거나 같고 a보다는 작은 어느 수이고 Q는 정수)

꼴이 될 수 있겠죠. 아. 물론 a, b 둘다 1이 아니고요.

1이 b개 있는 수는 10^(b-1) + ... + 10 + 1로 쓸 수 있는데요. b=aQ+r꼴로 쓸 수 있기 때문에

10^(b-1) + ... + 10^(aQ) + 10^(aQ-1) + ... 10 + 1

에서 밑줄 친 부분은 1이 a개 있는 수로 떨어집니다. 이건 윗 댓글에서 이야기를 했지요.

그렇다면 나머지 부분은 이렇게 쓸 수 있습니다.

10^(aQ) + ... + 10^(aQ+r-1)

= 10^(aQ) * (1+...+10^(r-1))

이 중에서 10^(aQ)는 볼 필요가 없고요.

우리가 주목해야 할 것은 오른쪽에 있는 것이죠.

1+...+10^(r-1)

이건 1이 r개 있는 수입니다. 이것은 1이 a개 있는 수로 나누어 떨어질까요?

한 가지 자명한 건 r<a라는 겁니다.

2가 4로 나누어 떨어진다는 소리는 안 하죠. 2가 5로 나누어 떨어진다는 소리 또한 안 하고요.

작은 수가 큰 수로 나누어 떨어지지는 않습니다.

따라서 a와 b가 서로소 관계이고 a<b일 때

1이 b개 연속해서 있는 수는 1이 a개 연속해서 있는 수로 떨어지지 않지요. a가 1이 아닌 이상 말이죠..

이 사실만 간파하시면, 나머진 유클리드 알고리즘으로 쉽게 구현 가능하십니다.