dorasainath955's blog

Why does the remainder of a number whose digits are all same keep repeating?
By dorasainath955, history, 22 hours 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
  • +6
  • Vote: I do not like it

»
22 hours ago, # |
← 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 hours ago, # |
← Rev. 2   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^7 \equiv 10 \pmod{7}\implies d\left(10^{7k + r} - 1\right) \equiv 10^{r+1}d\pmod{7} \text{ where } 0\le r < 7 $$$

Hence we'll get a repetition modulo 7.

→ Reply
  • »
    »
    70 minutes ago, # ^ |
      Vote: I like it 0 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 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

think like d*(1111..n times), now after every 6 "1" the number would be divisible by 7, because 111111 is completely divisible by 7, so the number would be divisible by 7 if n is a multiple of 6.

→ Reply
»
21 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

See I have a proof

Cyclic Remainder of N Divisible by 7

Any number N=dddddd....d can be written as

(Say (6k+x) times) ,where x<6

N= ddddd....d = 11111....1*d

Now we break this number into k blocks of 6 numbers each and one block with x number

N = dddddd*10^(6(k-1)+x) + dddddd*10^(6(k-2)+x) + .... + dddddd + dd..d (x times,x<6).

And there's a fact that dddddd%7==0. d can be any(1-9).

as dddddd=111111*d , and 111111%7==0 So from the above equation we can see that

N%7 =dd..d (only x times)

This suggests that the remainder we get will repeat in cycles of 6(the d=7 case is obvious ig)

*(Sorry for the wrong alignment, I am new that's why I don't have much idea)

→ Reply
»
21 hour(s) ago, # |
← Rev. 5   Vote: I like it 0 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
»
19 hours ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

One of the ways to solve this problem is compute $$$10^x \, mod \, p$$$ for example for $$$p = 7$$$ the sequence of the answers of this expression is:

$$$[1, 3, 2, 6, 4, 5]$$$ (sequence of answers is a periodic with this period)

so $$$6$$$ should count $$$n!$$$

it means $$$3 \le n$$$

→ Reply
»
48 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply