Project Euler #133: Repunit nonfactors

  • + 0 comments

    I have found two methods for solving this. Both build upon the same principle. From previous problems we know that a repunit can be written on the form

    \displaystyle R(k) = \frac{10^k - 1}{9}

    We will use this in our solution. The next thing we need is to know that if we have a number k = am, where k, a and m are positive integers, then R(a) divides R(k). We can show that since we have

    \displaystyle R(a) = \frac{10^a - 1}{9}

    and

    \displaystyle R(k) = \frac{10^k - 1}{9} = \frac{10^{am} - 1}{9}

    Therefore if we divide the two we get

    \displaystyle \frac{R(am)}{R(a)} = \frac{\frac{10^{am} - 1}{9}}{R(a)}

    Then for a little trick since the first part 10^{am} can be rewritten as an expression of R(a), since we have that 10^a = 9R(a) 1 (simple rewrite of the definition of R(a). Using this we get that 10^{am} =(9R(a) 1)^m. This can be inserted into the previous equation

    \displaystyle \frac{\frac{(9R(a) 1)^m - 1}{9}}{R(a)}

    The upper part where we have that (9R(a) 1)^m can be expanded such that it will yield a whole lot of terms containing some power and multiplum of 9R(a) and then one term which will be a one. As an example if m = 2 we get (9R(a) 1)^2 = 9^2R(a)^2 2(9R(a)) 1. Thus if we expand the power the ones will cancel out and we can divide all the terms by 9, such that we are left with terms which contains R(a), therefore R(a) is divisible by this numbers.

    What this means is that if p divides R(10^n) for some n then p also divides R(10^m) if n < m, since R(10^n) divides R(10^m) as we have just shown since we can write R(10^m) = R(10^a10^{n}) where a = m – n.