Problem 961: Repunit Divisibility

Mathematical Foundation

Theorem 1 (Divisibility Criterion). Let $\gcd(n, 10) = 1$. Then $n \mid R_n$ if and only if $10^n \equiv 1 \pmod{9n}$.

Proof. We have $R_n = (10^n - 1)/9$. Since $\gcd(n, 10) = 1$ implies $\gcd(n, 9) \mid 9$, we compute:

The second equivalence holds because $9 \mid (10^n - 1)$ is always true (since $10 \equiv 1 \pmod{9}$, so $10^n \equiv 1 \pmod{9}$), hence $n \mid (10^n - 1)/9$ if and only if $9n \mid (10^n - 1)$. $\square$

Lemma 1 (Even and 5-divisible exclusion). If $n > 1$ and $2 \mid n$ or $5 \mid n$, then $n \nmid R_n$.

Proof. Every repunit consists entirely of the digit 1, so $R_n$ is odd for all $n \ge 1$ (since $R_n = \underbrace{11\ldots1}_{n}$ and the last digit is 1). Similarly, $R_n \equiv 1 \pmod{5}$ for all $n \ge 1$. Therefore $2 \nmid R_n$ and $5 \nmid R_n$, which means if $2 \mid n$ or $5 \mid n$ (with $n > 1$), then $n \nmid R_n$. $\square$

Theorem 2 (Powers of 3). For all $k \ge 1$, $3^k \mid R_{3^k}$.

Proof. By induction on $k$.

Base case ($k = 1$): $R_3 = 111 = 3 \times 37$, so $3 \mid R_3$.

Inductive step: Assume $3^{k-1} \mid R_{3^{k-1}}$. Using the factorization identity for repunits:

set $m = 3^{k-1}$, so $R_{3^k} = R_{3^{k-1}} \cdot (10^{2 \cdot 3^{k-1}} + 10^{3^{k-1}} + 1)$.

Since $10 \equiv 1 \pmod{3}$, we have $10^{2 \cdot 3^{k-1}} + 10^{3^{k-1}} + 1 \equiv 1 + 1 + 1 = 3 \equiv 0 \pmod{3}$.

By the inductive hypothesis $3^{k-1} \mid R_{3^{k-1}}$, and the cofactor is divisible by 3, so $3^k \mid R_{3^k}$. $\square$

Lemma 2 (Multiplicative order characterization). For $\gcd(n, 10) = 1$, let $d = \operatorname{ord}_{9n}(10)$ be the multiplicative order of 10 modulo $9n$. Then $n \mid R_n$ if and only if $d \mid n$.

Proof. By Theorem 1, $n \mid R_n \iff 10^n \equiv 1 \pmod{9n}$. By definition of multiplicative order, $10^n \equiv 1 \pmod{9n}$ if and only if $d \mid n$. $\square$

Editorial

R_n = (10^n - 1) / 9 = 111…1 (n ones). Find sum of all n <= 1000 such that n | R_n. Equivalently: 9n | (10^n - 1), i.e., 10^n = 1 (mod 9n). Only possible when gcd(n, 10) = 1 (n odd, not divisible by 5). Complexity: O(N log N) with modular exponentiation.

Pseudocode

    total = 0
    For n from 1 to N:
        If gcd(n, 10) != 1 then
            continue
        If ModPow(10, n, 9*n) == 1 then
            total = total + n
    Return total

    result = 1
    base = base mod mod
    While exp > 0:
        if exp is odd:
            result = (result * base) mod mod
        exp = exp >> 1
        base = (base * base) mod mod
    Return result

Complexity Analysis

• Time: $O(N \log N)$. For each of the $O(N)$ candidate values of $n$, binary modular exponentiation computes $10^n \bmod 9n$ in $O(\log n)$ multiplications.
• Space: $O(1)$. Only a constant number of variables are maintained.

Answer

/*
 * Problem 961: Repunit Divisibility
 *
 * Find sum of n <= 1000 such that n | R_n where R_n = (10^n - 1)/9.
 * Equivalently: 10^n = 1 (mod 9n), for gcd(n, 10) = 1.
 *
 * Complexity: O(N log N) with binary exponentiation.
 */

#include <bits/stdc++.h>
using namespace std;

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

int main() {
    const int N = 1000;
    long long total = 0;

    for (int n = 1; n <= N; n++) {
        if (n % 2 == 0 || n % 5 == 0) continue;  // gcd(n,10) > 1
        long long mod = 9LL * n;
        if (power(10, n, mod) == 1) {
            total += n;
        }
    }

    // n=1 is special: R_1 = 1, 1|1
    // Already handled since gcd(1,10)=1 and 10^1 mod 9 = 1

    cout << total << endl;
    return 0;
}

"""
Problem 961: Repunit Divisibility

R_n = (10^n - 1) / 9 = 111...1 (n ones).
Find sum of all n <= 1000 such that n | R_n.

Equivalently: 9n | (10^n - 1), i.e., 10^n = 1 (mod 9n).
Only possible when gcd(n, 10) = 1 (n odd, not divisible by 5).

Complexity: O(N log N) with modular exponentiation.
"""

from math import gcd

def is_repunit_divisible(n: int) -> bool:
    """Check if n divides R_n = (10^n - 1) / 9."""
    if n == 1:
        return True
    if gcd(n, 10) > 1:
        return False
    return pow(10, n, 9 * n) == 1

def solve(N: int = 1000) -> tuple[int, list[int]]:
    """Find sum of all n <= N with n | R_n."""
    qualifying = [n for n in range(1, N + 1) if is_repunit_divisible(n)]
    return sum(qualifying), qualifying

# --- Compute answer ---
answer, qualifying = solve(1000)

# Verify small cases
assert is_repunit_divisible(1)  # R_1 = 1, 1|1
assert is_repunit_divisible(3)  # R_3 = 111 = 37*3
assert is_repunit_divisible(9)  # R_9 = 111111111 / 9 = 12345679... 9 | 111111111
assert not is_repunit_divisible(2)
assert not is_repunit_divisible(5)

print(f"Qualifying values: {qualifying}")
print(answer)