Hi,

Just solved problem 026 which was the only obstacle to my flawless-fifty.

I know this has been dimly mentioned in problem clarification section, but I can't suppress the excitement of discovering this:

For some prime number P below 1000, 1/P gives repeating decimal where the length of repeating sequence is (P-1). It is this discovery lead me to the answer for 026.

Not all prime displays such property, e.g. 2, 3, 5...etc which is obvious. Some positive examples include: 59, 61, 109, 113, and answer to 026 of course.

Prime numbers are always fascinating me.

Jim

## Repeating Decimal and Prime Number

### Re: Repeating Decimal and Prime Number

It's a directly follows fermat's little theorem:

10^(p-1) == 1 (mod p)

10^(p-1) == 1 (mod p)

### Re: Repeating Decimal and Prime Number

I feel embarrassed to admit: I could not see / understand why 10^(p-1) == 1 (mod p) is the reason, even after reading about introductory number theory in these day. I encounterd some congruences such as "Wilson's theorem" but yet this one.

Even if I take the above as fact, if p stands for prime numbers in general, why does it not apply to 2, 3, 5 etc? And how does it relate to length of repeating digit sequence of 1/p?

Thanks if you don't mind to elaborate again.

### Re: Repeating Decimal and Prime Number

10^n = 2^n * 5^n

So for n>=1, it is divisible by 2 and 5

For 3 the statement is true: 10^2 = 100 = 99+1 == 1 (mod 3)

It say only, that 10^(p-1) == 1 (mod p) (for other p than 2 or 5)

It does not say that there is no k<p-1 for which 10^k == 1 (mod p) can also be true.

The group theory says, apply the group operator (* for multiplicative groups) n times on any group element (for a group of group size n), the result is the neutral element of that group.

As all numbers between 1 and p-1 belong to the multiplicative group (mod p), the size is n.

And using the statement above, we got the result.

Interestingly, there exist non-prime-numbers which follow this sentence (except for their divisors!): e.g. 561

So for n>=1, it is divisible by 2 and 5

For 3 the statement is true: 10^2 = 100 = 99+1 == 1 (mod 3)

It say only, that 10^(p-1) == 1 (mod p) (for other p than 2 or 5)

It does not say that there is no k<p-1 for which 10^k == 1 (mod p) can also be true.

The group theory says, apply the group operator (* for multiplicative groups) n times on any group element (for a group of group size n), the result is the neutral element of that group.

As all numbers between 1 and p-1 belong to the multiplicative group (mod p), the size is n.

And using the statement above, we got the result.

Interestingly, there exist non-prime-numbers which follow this sentence (except for their divisors!): e.g. 561

### Re: Repeating Decimal and Prime Number

Do you remember how to do long division with pen and paper?jimfan wrote: ↑Fri Dec 15, 2017 4:59 pmI feel embarrassed to admit: I could not see / understand why 10^(p-1) == 1 (mod p) is the reason, even after reading about introductory number theory in these day. I encounterd some congruences such as "Wilson's theorem" but yet this one.

Even if I take the above as fact, if p stands for prime numbers in general, why does it not apply to 2, 3, 5 etc? And how does it relate to length of repeating digit sequence of 1/p?

Thanks if you don't mind to elaborate again.

For example, a long division of 1.0000 by 7.

Code: Select all

```
7 / 1.00000 \ 0.1
7
--
3
```

Code: Select all

```
7 / 1.00000 \ 0.14
7
--
30
28
--
2
```

Code: Select all

```
7 / 1.00000 \ 0.142
7
--
30
28
--
20
14
--
6
```

If at any point the remaining number at the bottom is the one we have already seen before, then everything will begin to repeat.

In the case of 1 dividing by n, there are only n possible remainders (0 to n-1). So either the division ends (with a 0 remainder) or the division repeats after at most n-1 steps.

Dividing 1 by a prime (other than 2 or 5) is a bit special, because then it is guaranteed to repeat from 1, and the period (the length of repeated part) will not just be p-1 or less, it will actually divide p-1. The remainder after k steps is 10^k (mod p), and it will repeat when this is 1 again, so the period is the smallest strictly positive number for which 10^k==1 (mod p). This is the order or 10 in the multiplicative group of integers mod p. This is a group of size p-1, and the order of each element (such as 10) divides the order of the group, p-1.

_{Jaap's Puzzle Page}

### Re: Repeating Decimal and Prime Number

Hello jaap,

Thank you for the great reminder: Long division! With input from you and v6ph1, plus two more hours of pencil and paper calculation, I finally get it. This is how I can reason about the phenomenon:

1. Let's visualise 10^N in form of 10^N = P * Quotient + Reminder. Consider P = 7 which is prime:

10^0 = 7 * 0 + 1 (true for any prime number, not just 7)

10^1 = 7 * 1 + 3

10^2 = 7 * 14 + 2

10^3 = 7 * 142 + 6

10^4 = 7 * 1428 + 4

10^5 = 7 * 14285 + 5

10^6 = 7 * 142857 + 1 (by Fermat's Little Theorem, 10^(P-1) == 1 (mod P)

2. By simple modular arithmetic, remainder R[N+1] can be derived as 10 * R[N] % 7. So the remainder for 10^7 will be 10 * 1 % 7 = 3. It is due to this nature, remainder sequence will repeat once it hits 1.

3. As for quotient, Q[N+1] can be derived as 10 * Q[N] + floor(10 * R[N] / 7):

10^0 = 7 * 0 + 1; Q = 0

10^1 = 7 * 1 + 3; Q = 0 * 10 + floor(10 * 1 / 7) = 1

10^2 = 7 * 14 + 2; Q = 1 * 10 + floor(10 * 3 / 7) = 14

10^3 = 7 * 142 + 6; Q = 14 * 10 + floor(10 * 2 / 7) = 142

...etc. Less formally, quotient of each row is created by appending new digit D to previous one, where D is floor(10 * R / 7).

4. And thus by Fermat's Little Theorem, period for Q is P-1

5. 2 and 5 are not co-prime to 10, the above relationship does not stand for P = 2 or P = 5, because remainder for every row would be zero. Fermat's Little Theorem also requiries P to be co-prime to 10.

6. However, I don't have any idea about group theory (yet!). Later on I might be able to do that.

All these are so amazing.

Jim

Thank you for the great reminder: Long division! With input from you and v6ph1, plus two more hours of pencil and paper calculation, I finally get it. This is how I can reason about the phenomenon:

1. Let's visualise 10^N in form of 10^N = P * Quotient + Reminder. Consider P = 7 which is prime:

10^0 = 7 * 0 + 1 (true for any prime number, not just 7)

10^1 = 7 * 1 + 3

10^2 = 7 * 14 + 2

10^3 = 7 * 142 + 6

10^4 = 7 * 1428 + 4

10^5 = 7 * 14285 + 5

10^6 = 7 * 142857 + 1 (by Fermat's Little Theorem, 10^(P-1) == 1 (mod P)

2. By simple modular arithmetic, remainder R[N+1] can be derived as 10 * R[N] % 7. So the remainder for 10^7 will be 10 * 1 % 7 = 3. It is due to this nature, remainder sequence will repeat once it hits 1.

**Now the answer to my very inquiry:**3. As for quotient, Q[N+1] can be derived as 10 * Q[N] + floor(10 * R[N] / 7):

10^0 = 7 * 0 + 1; Q = 0

10^1 = 7 * 1 + 3; Q = 0 * 10 + floor(10 * 1 / 7) = 1

10^2 = 7 * 14 + 2; Q = 1 * 10 + floor(10 * 3 / 7) = 14

10^3 = 7 * 142 + 6; Q = 14 * 10 + floor(10 * 2 / 7) = 142

...etc. Less formally, quotient of each row is created by appending new digit D to previous one, where D is floor(10 * R / 7).

**This explains why there is repeating sequence in quotient: As R recurs, D also recurs!**4. And thus by Fermat's Little Theorem, period for Q is P-1

5. 2 and 5 are not co-prime to 10, the above relationship does not stand for P = 2 or P = 5, because remainder for every row would be zero. Fermat's Little Theorem also requiries P to be co-prime to 10.

6. However, I don't have any idea about group theory (yet!). Later on I might be able to do that.

All these are so amazing.

Jim