[FEATURE]: The Repunit theorem #13999
Description
Feature description
Motivation
Numbers formed by repeating digits or repeating blocks—such as 111111, 424424, or structures like 10ⁿ + 1 (e.g., 100000001)—follow predictable patterns in number theory. These patterns are not random; they arise from the multiplicative order of 10 modulo a prime.
Right now, we treat these numbers as arbitrary integers, which leads to three core problems:
- Missing mathematical behavior
Repeated-digit numbers have a very specific factorization rule (e.g., 100000001 being divisible by 17). Without modeling the underlying theorem, our current logic either:
- gives no insight into why the divisibility works,
- or forces us to compute divisibility using naive methods that scale poorly.
- Inconsistent patterns in code
Because these numbers are treated on a case-by-case basis, any function that needs to handle:
- repunits (111…1),
- repeated digits (777777),
- repeated blocks (XYZXYZ),
- or cyclotomic structures (10ⁿ ± 1),
ends up re-implementing partial logic, often incorrectly or inefficiently. Bringing this into a unified mathematical rule improves maintainability and correctness.
- Huge performance waste for large repeated patterns
Repeated-digit integers can be extremely large (sometimes more than a million digits long).
Using the multiplicative-order approach lets us compute divisibility using O(log n) modular arithmetic and without building the actual number at all.
With this algorithm in place, once the multiplicative order is part of the system, it unlocks:
- fast repunit divisibility checks,
- systematic analysis of repeated-digit numbers,
- handling of cyclotomic expressions,
- better support for prime testing involving decimal periodic.
I believe this will be a good one to tackle, given that it's an unresolved problem in number theory.
Examples
These examples show actual numbers, their patterns, and the mathematical reason they’re divisible by certain primes.
1. Classic example: 100000001 is divisible by 17
100000001 ÷ 17 = 5882353
Why?
100000001 = 10⁸ + 1
The multiplicative order of 10 modulo 17 is 8, meaning:
10⁸ ≡ 1 (mod 17)
So:
10⁸ + 1 ≡ 2 (mod 17)? No → but 10⁸ ≡ -1 (mod 17)
Actually:
10⁸ ≡ -1 (mod 17)
Therefore:
10⁸ + 1 ≡ 0 (mod 17)
2. Repeated block example: 424424
Block: 424
Repeated twice → total structure: 424424
Divisible by:
7, 11, 13 → because 1001 = 7 × 11 × 13
Why?
424424 = 424 × 1001, and:
1001 = 10³ + 1 = (10³ - 1)/9 × 9
The fact that 1001 factors into 7, 11, and 13 comes from the multiplicative order of 10 modulo those primes.
3. Repunit example: 111111
111111 is 6 repeated digits of 1.
It equals:
111111 = (10⁶ − 1) / 9
Divisible by:
3
7
11
13
37
Why these primes?
Because the multiplicative order of 10 modulo each of those primes divides 6.
For example:
- ord₁₁(10) = 2 → and 2 divides 6
- ord₃₇(10) = 3 → and 3 divides 6
- ord₇(10) = 6 → and 6 divides 6
So all of them divide 111111.
4. Repeated digit example: 999999999 (9 repeated 9 times)
This is:
999,999,999 = 9 × 111,111,111
And 111,111,111 has divisors:
3
37
333667
Again, it is determined by which primes have multiplicative order dividing 9.
5. Three-block repeated pattern: XYZXYZXYZ
Example: 123123123
This is:
123 × 1,001,001
Prime factors of 1,001,001:
1,001,001 = 7 × 11 × 13 × 101 × 109
All these primes divide the repeated-block number because their orders divide 3×3.
6. Palindromic power example: 10⁶ − 1 = 999999
Divisible by:
9 → trivial because it's 9 repeated digits
37
3
27
The factor 37 is the famous one here because:
999 = 27 × 37
which again is tied to the order of 10 modulo 37 (which is 3).
7. Full reptend prime example
A prime is "full reptend" in base 10 if the order of 10 mod p is p−1.
Example:
7 is a full reptend prime.
10 has order 6 mod 7.
This is why:
1/7 = 0.142857142857… (repeats every 6 digits)
and why repunit length = 6.
Possible workarounds
No response
Additional information
No response