프로젝트 오일러 129번

A number consisting entirely of ones is called a repunit. We shall define \(R(k)\) to be a repunit of length \(k\); for example \(R(6)=111111\).

Given that \(n\) is positive integer and \({\rm GCD}(n, \;10) =1\), it cane be shown that there always exists a value, \(k\), for which \(R(k)\) is divisible by \(n\), and let \(A(n)\) be the least such value of \(k\); for example, \(A(7)=6\) and \(A(41)=5\).

The least value of \(n\) for which \(A(n)\) first exceeds ten is \(17\).

Find the least value of \(n\) for which \(A(n)\) first exceeds one-million.

---

숫자 \(1\) 로만 만들어진 자연수를 repunit 이라 부르고, \(R(k)\) 는 \(1\) 이 \(k\) 개 나열된 자연수라고 하자. 예를 들어, \(R(6)=111111\) 이 된다.

또한 \(10\) 과의 최대공약수가 \(1\) 인 어떤 수 \(n\) 이 있을 때, \(R(k)\) 가 \(n\) 으로 나누어 떨어지는 \(k\) 가 항상 존재한다는 사실이 알려져 있다. 이 사실로 부터 \(A(n)\) 을 \(R(k)\) 가 \(n\) 으로 나누어 떨어지는 자연수 \(k\) 의 최솟값으로 정의할 수 있다. 예를 들어, \(A(7)=6\) 이고, \(A(41)=5\) 이다.

이런식으로 자연수 \(n\) 에 대하여 \(A(n)\) 을 구해나가보면 \(A(n)\) 이 \(10\) 을 넘어가게 되는 최소의 자연수 \(n\) 은 \(17\) 임을 알 수 있다.

\(A(n)\)이 \(10^6\) 을 넘어가게 되는 최소의 자연수 \(n\) 을 구하시오.

이 문제를 풀기 위해서는 두 가지를 알고 있어야 한다. 글로 풀어 쓰기가 귀찮아서 그냥 동영상으로 만들었다.