The length of the repetend of the reciprocal of a prime number \(p\) in any number base \(b\), such that \(b\) is not multiple of \(p\), will always divide \(p-1\).
Over the course of this page, you will learn what that actually means, how to prove it, and why that's a slightly useful property.
In decimal, one seventh is written 0.142857. (By the way, over the course of this page, overlines mean repetends.) This repetend is 10 (6) symbols long. What my theorem says is that this length can only be 1, 2, 3 or 10 (6), as those divide 11-1 (7-1=6).
This can be shown in the extensions of one over seven in various bases:
Like predicted, no 1② (4) or 1① (5)-long repetends.
Here's a bigger table (in decimal for ease of generation and reading) with the first ten primes and bases up to 1①① (29) to show extensively the point:
Base
2
3
5
7
11
13
17
19
23
29
B
0
2
4
3
10
12
8
18
11
28
T
1
0
4
6
5
3
16
18
11
28
Q
0
1
2
3
5
6
4
9
11
14
P
1
2
0
6
5
4
16
9
22
14
H
0
0
1
2
10
12
16
9
11
14
S
1
1
4
0
10
12
16
3
22
7
O
0
2
4
1
10
4
8
6
11
28
E
1
0
2
3
5
3
8
9
11
14
D
0
1
0
6
2
6
16
18
22
28
UD
1
2
1
3
0
12
16
3
22
28
Z
0
0
4
6
1
2
16
6
11
4
UZ
1
1
4
2
10
0
4
18
11
14
BS
0
2
2
0
5
1
16
18
22
28
TP
1
0
0
1
5
12
8
18
22
28
X
0
1
1
3
5
3
2
9
11
7
UX
1
2
4
6
10
6
0
9
22
4
TH
0
0
4
3
10
4
1
2
11
28
UTH
1
1
2
6
10
12
8
0
22
28
V
0
2
0
2
5
12
16
1
22
7
TS
1
0
1
0
2
4
4
18
22
28
BUD
0
1
4
1
0
3
16
18
2
14
UBUD
1
2
4
3
1
6
16
9
0
7
QH
0
0
2
6
10
12
16
9
1
7
PP
1
1
0
3
5
2
8
9
11
7
BUZ
0
2
1
6
5
0
8
3
11
28
TE
1
0
4
2
5
1
16
6
11
28
QS
0
1
4
0
10
12
16
9
22
2
UQS
1
2
2
1
10
3
16
18
11
0
As you can see, all of the numbers follow the pattern! This is enough to conjecture my initial statement, but how do we go about proving it?
The way you find the length of the reciprocal of the prime \(p\) in the base \(b\) can be given by the smallest \(l\) that satisfies the following:
Imagine a number \(\frac{1}{p} = x\) of the form \(0.\overline{a}\), where \(a\) is the \(l\)-digit long extension.
\begin{align}
x &= 0.\overline{a}\\
b^l x &= a.\overline{a}\\
b^l x - x &= a.\overline{a} - 0.\overline{a}\\
(b^l - 1)x &= a\\
x &= \dfrac{a}{b^l - 1}\\
\dfrac{1}{p} &= \dfrac{a}{b^l - 1}
\end{align}
Now, this isn't a very easy formula to work with. Especially with the pesky \(a\) hanging on. However, we can get rid of it with a little rearranging and modular arithmetic:
\[ b^l-1 = a \cdot p \]
\(a\) must be an integer, so \(b^l-1\) must be a multiple of \(p\).
\[ b^l-1 \equiv 0 \pmod p \]
\[ b^l \equiv 1 \]
This means that to find out what \(l\) is, we can simply raise \(b\) to consecutive powers until it becomes equivalent to 1. This clearly shows that the pattern of reciprocal lengths must be cyclic across bases with a period of \(p\), but also is fundamental to where the proof goes next.
Yeah, I was pretty surprised that group theory is helpful here. But a theorem from it is key to explaining why \(l\) divides \(p-1\).
However, we first must prove that modular arithmetic is a group under multiplication.
The set is closed, as the product of two numbers is always a number in the set;
Multiplication retains its associativity, so that's easy;
1 is the multiplicative neutral element, since 1 times any number is the original number.
Every number except 0 has an inverse: a number that times the target results in the identity, 1. (Removing 0 doesn't mess with the other three rules, so that is still safe)
All of these are obvious, except for the last one. How do you prove that? Turns out... the pigeonhole principle, and contradiction.
Every multiplication sends you to a number, but we only have limited numbers. This means that, eventually, something will repeat in the sequence \((1,b,b^2,b^3,...)\).
If 1 repeats, you have \(b^l \equiv 1 \), so \(b^{l-1}\) is our inverse.
If another power repeats, then we have a situation where one result is reached by two different multiplications.
\[b^s \cdot b \equiv b^t \cdot b\]
\[b^s \cdot b - b^t \cdot b \equiv 0\]
\[b(b^s - b^t) \equiv 0\]
Now, how can that be true?
If \(b \equiv 0\), it is a multiple of \(p\), so it does not have a repetend to measure (and breaks the coprime requirement).
If \(b^s - b^t \equiv 0\), we have that \(b^s \equiv b^t \), so can go back to the first case by having \(b^{s-t} \cdot b^t \equiv b^t \implies 1 \equiv b^{s-t}\).
If neither is 0, then both \(b\) and \(b^s-b^t\) contain a factor of \(p\). That is only possible if \(gcd(b, p) > 1 \), so that contradicts our setup.
So, under multiplication mod \(p\), if \(p\) is prime, the numbers from 1 to \(p-1\) are always a group, called \(\mathbb{Z}^*_p\). Now, how do you use this?
There's this theorem called Lagrange's theorem, which states that for any subgroup \(H\) of a group \(G\), \(H\)'s size is a divisor of \(G\)'s size.
And repeatedly multiplying by \(b\) generates a cyclic subgroup \((1,b,b^2,b^3,...)\) inside of \(\mathbb{Z}^*_p\), which means that this must apply! And since the subgroup has order \(l\), \(l\) must divide \(p-1\)! How cool is that?
This is an extremely niche property (even if we stumbled across cooler properties along the way), but it is kind of useful when you are comparing number bases. Instead of looking through every possible denominator to find the size of a reciprocal, you can simply check the divisors of \(p-1\) to speed up the search!
This also showcases a few interesting things about the length of extensions.
Every base can write the reciprocal of the number one below itself with a single repeating digit: \[b^1 \equiv 1 \pmod p \implies l = 1\]
Every base can write the reciprocal of the number one above itself with two repeating digits: \[b^1 \equiv -1 \pmod p \implies \]
\[ \implies b^2 \equiv 1 \implies l = 2\]
The maximum length of a reciprocal is the prime minus 1 (yes, everyone already knows that, but it is important to reiterate)
Every even-length repetend can be written in the double overlined form in a balanced base: \[l = 2n \implies b^n \equiv -1\]
Remember that, when you hit -1, you are doomed to repeat the path you just took but with flipped signs.
Lastly, every coset of the cyclical subgroup is a multiple of the subgroup. For example: \(\mathbb{Z}^*_{21(13)}\) has a subgroup (1, 3, 13), with cosets (2, 10, 1①), (1②, 20, 2②), (11, 12, 2①). [All in decimal: (1, 3, 9), (2, 6, 5), (4, 12, 10), (7, 8, 11).] Another subgroup is (1, 1①, 20, 12), with cosets (2, 2②, 2①, 3) and (1②, 11, 13, 10). [Decimal: (1, 5, 12, 8), (2, 10, 11, 3), (4, 7, 9, 6).]
