프로젝트 오일러 130번

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 a positive integer and \({\rm GCD}(n, \;10)=1\), it can 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\).

You are given that for all primes, \(p>5\), that \(p-1\) is divisible by \(A(p)\). For example, when \(p=41\), \(A(41)=5\), and \(40\) is divisible by \(5\).

However, there are rare composite values for which this is also true; the first five examples being \(91\), \(259, \; 451, \; 481,\) and \(703\).

Find the sum of the first twenty-five composite values of \(n\) for which \({\rm GCD}(n, \;10)=1\)  and \(n-1\) is divisible by \(A(n)\).

---

숫자 \(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\) 이다.

이제 \(5\) 보다 큰 소수 \(p\) 를 생각해보자. \(p>5\) 인 모든 소수 \(p\) 는 \(p-1\) 이 \(A(p)\) 로 나누어 떨어진다는 특징이 있다. 예를 들어, \(p=41\) 일 때, \(A(41)=5\) 이므로 \(41-1=40\) 은 \(5\) 로 나누어 떨어진다.

그렇지만 아주 드물게 합성수 중에도 이런 특징을 보이는 숫자들이 있다. 이런 특징을 갖는 합성수를 오름차순으로 나열하면 처음 \(5\)개는 \(91, \; 259,\; 451, \; 481,\; 703\) 이 된다.

\({\rm GCD}(n,\; 10)=1\) 이고 \(n-1\) 이 \(A(n)\) 으로 나누어 떨어지는 합성수를 오름차순으로 나열했을 때, 처음 \(25\)개의 합을 구하시오.  

이 문제는 129번 문제를 풀고 왔다면 거저 먹을 수 있는 문제다.

129번 문제에서 꼭 알아야 한다고 했던 첫 번째 내용을 알고, 소수 판정법만 알면 쉽게 풀 수 있을 것이다.