Repeating Decimal and Prime Number

Arithmetic, algebra, number theory, sequence and series, analysis, ...
Post Reply
jimfan
Posts: 13
Joined: Fri Sep 29, 2017 3:09 pm

Repeating Decimal and Prime Number

Post by jimfan » Fri Sep 29, 2017 3:22 pm

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
Image

v6ph1
Posts: 94
Joined: Mon Aug 25, 2014 6:14 pm

Re: Repeating Decimal and Prime Number

Post by v6ph1 » Sat Sep 30, 2017 1:06 pm

It's a directly follows fermat's little theorem:
10^(p-1) == 1 (mod p)
Image

jimfan
Posts: 13
Joined: Fri Sep 29, 2017 3:09 pm

Re: Repeating Decimal and Prime Number

Post by jimfan » Fri Dec 15, 2017 4:59 pm

v6ph1 wrote:
Sat Sep 30, 2017 1:06 pm
It's a directly follows fermat's little theorem:
10^(p-1) == 1 (mod p)
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.
Image

v6ph1
Posts: 94
Joined: Mon Aug 25, 2014 6:14 pm

Re: Repeating Decimal and Prime Number

Post by v6ph1 » Sat Dec 16, 2017 2:25 pm

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
Image

User avatar
jaap
Posts: 503
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Repeating Decimal and Prime Number

Post by jaap » Mon Dec 18, 2017 10:49 am

jimfan wrote:
Fri Dec 15, 2017 4:59 pm
v6ph1 wrote:
Sat Sep 30, 2017 1:06 pm
It's a directly follows fermat's little theorem:
10^(p-1) == 1 (mod p)
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.
Do you remember how to do long division with pen and paper?
For example, a long division of 1.0000 by 7.

Code: Select all

7 / 1.00000 \ 0.1
      7
     --
      3
The 3 at the bottom is the remainder we get when dividing 10 by 7.

Code: Select all

7 / 1.00000 \ 0.14
      7
     --
      30
      28
      --
       2
The 2 at the bottom now is really the remainder of dividing 100 by 7.

Code: Select all

7 / 1.00000 \ 0.142
      7
     --
      30
      28
      --
       20
       14
       --
        6
The 6 at the bottom now is really the remainder of dividing 1000 by 7.

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.

jimfan
Posts: 13
Joined: Fri Sep 29, 2017 3:09 pm

Re: Repeating Decimal and Prime Number

Post by jimfan » Sun Dec 24, 2017 12:57 pm

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.

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
Image

Post Reply