SainathDora's blog

Why does the remainder of a number whose digits are all same keep repeating?
By SainathDora, history, 22 months ago, In English

Imagine a number N which is made of digits d repeating n times
eg:

$$$N = dddddd.....d$$$
(n times)
if we keep taking modulo of $$$N$$$(increase the number of digits) with some number $$$p$$$ at one point the modulo keeps on repeating eg: $$$d = 3$$$ and $$$p = 7$$$
Row Number N N mod 7
1 3 3
2 33 5
3 333 4
4 3333 1
5 33333 6
6 333333 0
7 3333333 3
8 33333333 5
9 333333333 4
10 3333333333 1
11 33333333333 6

From row 7 it keeps repeating
The reason i am asking this question due to this Problem

Is there any proof to this or is it just that I have to remember this.


It my first time encountering this pattern

  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
22 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

$$$10^6 \equiv 1 \,\, \text{mod} \,7$$$ and $$$\frac{111111}{7} = 15873$$$.
$$$1111111 \equiv \,\, 1\cdot 10^6 + 111111 \equiv 1 + 111111\,\, \text{mod} \,7$$$
$$$11111111 \equiv \,\, 11 \cdot 10^6 + 111111 \equiv 11 + 111111\,\, \text{mod} \,7$$$
$$$11111111 \equiv \,\, 111 \cdot 10^6 + 111111 \equiv 111 + 111111\,\, \text{mod} \,7$$$
So we can spit number into blocks of $$$6$$$ and one block of $$$n \,\,\text{mod} \, 6$$$ ones (where $$$n$$$ number of digits), and all blocks of $$$6$$$ are divisible by $$$7$$$, so it repeats each $$$6$$$.

→ Reply
»
22 months ago, hide # |
← Rev. 3  
Vote: I like it +13 Vote: I do not like it

Note that, $$$\gcd(10, 7) = \gcd(9, 7) = 1$$$. Now, we have

$$$N=\overline{ddd\dots d}_{10}= \displaystyle\sum_{i=0}^n \left(10^i\cdot d\right)=\dfrac{d\cdot \left(10^n - 1\right)}{9} $$$

By Fermet's Little Theorem we have,

$$$10^6 \equiv 1 \pmod{7}\implies d\left(10^{6k + r} - 1\right) \equiv d\dfrac{\left(10^{r}-1\right)}{9}\pmod{7} \text{ where } 0\le r \lt 6 $$$

Hence we'll get a repetition modulo 7.

→ Reply
  • »
    »
    22 months ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    could you please elaborate on how you managed to reduce

    $$$10^7 \equiv 1 (mod 7) \Rightarrow d(10^{7k+r}-1) \equiv 10^{r+1}d (mod\ 7)$$$

    Here's what I've understood

    Let the number

    $$$n = 7k +r$$$
    From fermat theoram we can write
    $$$10^7 \equiv 10 (mod 7)$$$
    $$$10^{7k} \equiv 10^{k} (mod 7) \Rightarrow 10^{7k+r} \equiv 10^{k+r} (mod\ 7)$$$

    subtract one from both sides

    $$$10^{7k+r}-1 \equiv 10^{k+r}-1 (mod\ 7)$$$

    We can stop here

    as dividing on both sides with d/9 will only scale.
    How to proceed from here
    → Reply
»
22 months ago, hide # |
← Rev. 5  
Vote: I like it +8 Vote: I do not like it

let's say the number is $$$n$$$

then adding the next digit, the number would be $$$10n+d$$$

if $$$n \equiv k \space (mod \space p)$$$ then the next modulo would be $$$10k+d \space (mod \space p)$$$

one way to visualize this is with a graph with an directed edge between node $$$k$$$ and node $$$10k+d \space (mod \space p)$$$

if $$$p$$$ is coprime to $$$10$$$, then the following graph would have $$$p$$$ nodes, $$$p$$$ edges and will contain multiple components, each of them containing a cycle and some paths leading to a cycle (since there are no unique a,b that maps to the same node)

if there are:

$$$10a+d \equiv 10b+d \space (mod \space p)$$$

$$$10a \equiv 10b \space (mod \space p)$$$

since $$$p$$$ and $$$10$$$ are coprime:

$$$a \equiv b \space (mod \space p)$$$

if $$$p$$$ and $$$10$$$ aren't coprime then

$$$10k+d \equiv d \space (mod \space p)$$$ which means every edge will connect to d, which will make it a single cycle of size 1

this could also be extended to ANY base/digit and modulo

→ Reply
»
22 months ago, hide # |
 
Vote: I like it +23 Vote: I do not like it

When you do long division, you will eventually get the same remainder twice, after which you repeat.

→ Reply
»
22 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

I think, I have an intuitive way of understanding "mod repeating things" in general. Any number n mod p will be always repeating because there is maximum (p-1) of different possible values of mod.

For example, let's think there is an imaginary case where d mod p = 1 , (dd) mod p = 2,...( (p-1)d) mod p = (p-1). Then finally it is confirmed that after p case it will always be between 0 to (d-1). If it is somewhere between it can go to some specific mod then it will start from that mod and repeating that cycle from that point. That's why there is always a repeating mod pattern.

Note: ((p-1)d) means basically (p-1) amount of d concatenated.

Sorry for my bad English.

→ Reply