# Project Euler Problem 132 - Solved

Solution to ProjectEuler's problem 132 in Python using an efficient way to represent a repunit and modular exponentiation.

The statement of this problem can be found here.

In order to solve this problem the first important thing to notice is how a *repunit* can be represented: \[ R(k) = \frac{10^k - 1}{9} \]

Therefore, we can express if a *repunit* is divisible by *p* like:

\[ \begin{aligned} \\ \frac{10^k - 1}{9} & \equiv & 0 \mod p \\ {10^k - 1} & \equiv & 0 \mod 9p \\ {10^k} & \equiv & 1 \mod 9p \\ \end{aligned} \]

So if \(10^k \mod 9p = 1 \), then *p* divides \( R(10^k) \).

The problem now is how to calculate the remainder in an efficient way as it is impossible to calculate the remainder to a number of a thousand million digits.

Here we can use Modular exponentiation as what we need to calculate is the remainder of a number than can be expressed as a power with base 10 and exponent 9.

The solution for this code in Python (problem132.py) is really simple (the `CommonFunctions`

file can be found here):

```
from CommonFunctions import *
from itertools import *
if __name__ == '__main__':
primes = find_primes_less_than(10 ** 6)
base = 10
exp = 10 ** 9
result = sum(islice((p for p in primes if mod_pow(base, exp, 9 * p) == 1), 0, 40))
print("The result is:", result)
```

Comments powered by Talkyard.