Question

Let \(R_n=111\ldots\text{n 1's}\) be the number with \(n\) ones in decimal number system.

Find the smallest \(R_n\) that is divisible by \(83\).

Answer 1

.

Answer 2

Correction:
\[R_n=\sum_{k=0}^{\color{red}{n-1}}10^k=\frac{10^{\color{red}n}-1}{9}\]
so find \(n\) such that
\[\frac{10^{\color{red}n}-1}{9}\equiv0\mod83\]

Answer 3

I suppose this can be simplified a bit... \(n\) should also satisfy this, no?
\[10^n\equiv1\mod83\]

Answer 4

from fermats little theorem we have this bount atleast 10^(82)-1=0 mod 83

Answer 5

oh we can reduce the ones we have left to check by looking at the divisors of 82 apparently

Answer 6

acording to this http://prntscr.com/8834ha

Answer 7

82 = 2*41
therefore all we have left to check is 2,41
10^2-1 =/=0mod83
10^41-1 = 0 mod 83

Answer 8

41, 1s

Answer 9

I'm getting the same result with Mathematica, checks out

Answer 10

the 2nd statement that there msut exist some lower exponent d that divides p-1, if p does not divide a looks interesting

Answer 11

i has same method finding the first n which satisfy
10^n=1 mod 83

Answer 12

so we know
10^82 satisfy, now we check its divisors 1,2,41,82 the end xD

Answer 13

Awesome! so it seems, given a prime, \(p\), we can always find the smallest \(R_n\) divisible by \(p\), by looking at the divisors of \(p-1\)

Answer 14

.

Answer 15

@ganeshie8 are you saying that R_n always composite ?

Answer 16

11 isn't composite

Answer 17

i know it has some primes im trying to understand what u have said :)

Answer 18

fix a prime \(p\) and form the set of all \(R_n\)'s that are divisible by \(p\).

then we can find the least element in that set using the earlier trick

Answer 19

got it!

Answer 20

:O its awesome isnt it ?

Answer 21

so baiscally all \(\large R_{p-1}\)'s are composite because they are trivially divisible by \(p\)

Answer 22

yeah with even number of digits hmmm

Answer 23

Oh, all \(\large R_{2k}\) are composite is it ?

Answer 24

Easy to see that all \(\large R_{3k}\) are composite because they are divisible by \(3\)..

Answer 25

yeah for this one, i think we have proved this earlier

Answer 26

the 1010101 stuff

Answer 27

let me remember how it was like exactly

Answer 28

Ah, right, its easy one sec

Answer 29

\[\large R_{2k}=\sum_{k=0}^{\color{red}{2k-1}}10^k=\frac{10^{\color{red}{2k}}-1}{9} = \dfrac{(10^k-1)(10^k+1)}{9}\]

Answer 30

for \(k\gt 1\),
we have \(10^k-1 = 9l\) such that \(l\gt 1\)

Answer 31

so ovs what l was whole number stays composite :3

Answer 32

for \(k\gt 1\),
\[\large R_{2k}=\sum_{k=0}^{\color{red}{2k-1}}10^k=\frac{10^{\color{red}{2k}}-1}{9} = \dfrac{(10^k-1)(10^k+1)}{9} = l(10^k+1)\]

which cannot be a prime as it is product of two factors that are > 1

Answer 33

haha sweet !

Answer 34

that also shows :
if \(n\) is composite, then \(R_n\) is composite

Answer 35

correct!