Question

numbers of form \( 1111111\ldots \)

Answer 1

rare primes party xD

Answer 2

There was one question a while back that was like prove 343434343... are composite, I'd really like to figure that one out still, I don't know, I don't want to hijack this we can do that one some other time though maybe?

Answer 3

working on this proof :

a)
say \(n\) = number of \(1\)'s in that number.
next consider the smallest such number whose prime factor is \(p \)
prove that \(p-1\) is divisible by \(n\) for all \(p \ge 5\)

b)
using part a, find the smallest such number which is divisible by \(13\)

Answer 4

i gave up on that 34343... problem kai, its very hard to prove that with the elementary number theory tricks it seems

Answer 5

but this problem is fairly simple.. i dont have a proof yet though

Answer 6

Ok wait I was assuming this was base 2, but this is really base 10 right @ganeshie8 ?

Answer 7

Ahh yes yes...

Answer 8

In short :
we need to find the smallest integer divisible by \(13\) of form \(111\ldots\)

Answer 9

Example: \[\Large 111=10^0+10^1+10^2 \\ \Large 111... = \sum_{k=0}^{n-1}10^k\]

Answer 10

Not sure if that helps us, but maybe

Answer 11

i don't think we can get a better start than that xD
\[\large 111\ldots (\text{n times}) = \dfrac{10^n-1}{10-1}\]

Answer 12

xD
will i was like
n mod 9 is the same as keep summing digits

Answer 13

Always has something to do with mods, haha.

Answer 14

looks there was a mistake in problem statement
\(p=5\) doesn't make sense, this only works for \(p \color{Red}{\gt} 5\)

Answer 15

ok i dont really get what the questions is like what do u mean by
next consider the smallest such number whose prime factor is p

Answer 16

like
111.....1=p^k ?

Answer 17

if possible im lookong for a proof with out mods and other fancy stuff @Jhannybean but most likely i wont get it ;)

Answer 18

yeah what ever :P

Answer 19

yeah ANYTHING is fine for a first proof :)
il give an example @Marki

Answer 20

Yeah I'm lost with @Marki on this one, that didn't make sense to me either haha

Answer 21

@Michele_Laino any ideas?

Answer 22

consider \(n = 8\) case :
\[\large 11111111 = 73\times 152207\]

\(73-1\) is divisible by \(8\) as desired
also \(11111111 \) is the smallest number thats divisible by \(73\)

Answer 23

want another example ?

Answer 24

seems nice !
yeah continue

Answer 25

basically that theorem helps in finding the prime factors of numbers of form \(111\ldots \) easily

Answer 26

yep yep, i wonder how did u get it :O

Answer 27

idk how to prove it other than the trivial observation that these numbers are of form \(\dfrac{10^n-1}{9}\)

Answer 28

http://mathworld.wolfram.com/Repunit.html

Answer 29

@Marki I did that same thing earlier and laughed at myself XD

Answer 30

\(\large \dfrac{10^{n+1}-1}{9}=(10-1)(10^{n-1}+2.10^{n-2}+3.10^{n-3}+.....+n )+(n+1)\)

Answer 31

i remember it from a question u solved before @Kainui
lol was a good time :3

Answer 32

Oh woah! Interesting apparently "Every prime repunit is a circular prime."

Answer 33

Oh wait no nevermind that's obvious and stupid... X_X

Answer 34

now lets try what possibles we have

Answer 35

circle in mod 9 xD
but ppl here gone crazy when i speak of it i'll try something different

Answer 36

this one
https://www.wolframalpha.com/input/?i=%5Cdfrac%7B10%5E%7B1038%7D-1%7D%7B9%7D+mod+13

Answer 37

circular primes look interesting xD
@mathmath333 so the number with 1038 ones is divisible by 13, but that need not be the smallest number right ?

Answer 38

u mean the 1038 is not the smallest one ?

Answer 39

so let n+1 be our prime
then
\((10-1)(10^{n-1}+2.10^{n-2}+3.10^{n-3}+.....+n ) =1 \mod n\)
hmm idk if this is work

Answer 40

https://www.wolframalpha.com/input/?i=Table%5B%2810%5En-1%29%2F9+mod+13%2C+%7Bn%2C5%2C20%7D%5D

it turns out that the smallest number divisible by 13 is \((10^6-1)/9\)

Answer 41

by the 13 is a prime so u can apply the fermat u think

Answer 42

Yes!

Answer 43

thats why 13-1 should be the smallest

Answer 44

\[ \Large 111... = \sum_{k=0}^{n-1}10^k \equiv \dfrac{10^n-1}{9} \pmod {p}\]

Answer 45

nice

Answer 46

i don't get it

Answer 47

Oh wait, since \(p \nmid 9\), we can use fermat theorem directly on \(\large 10^n-1 \equiv 0 \pmod {p}\)

Answer 48

are you saying \(n \) must be multiple of \(p-1\) for this to hold ?
thats a very interesting observation, let me think a bit more...

Answer 49

```
n=1, 1 = 1
n=2, 11 = 1011
n=3, 111 = 1101111
n=4, 1111 = 10001010111
n=5, 11111 = 10101101100111
n=6, 111111 = 11011001000000111
n=7, 1111111 = 100001111010001000111
n=8, 11111111 = 101010011000101011000111
n=9, 111111111 = 110100111110110101111000111
n=10, 1111111111 = 1000010001110100011010111000111
n=11, 11111111111 = 1010010110010001100001100111000111
n=12, 111111111111 = 1100111011110101111010000000111000111
n=13, 1111111111111 = 10000001010110011011000100001000111000111
n=14, 11111111111111 = 10100001101100000001110101001011000111000111
n=15, 111111111111111 = 11001010000111000010010010011101111000111000111
n=16, 1111111111111111 = 11111100101000110010110111000101010111000111000111
n=17, 11111111111111111 = 100111011110010111111100100110110101100111000111000111
n=18, 111111111111111111 = 110001010101111101111011110000100011000000111000111000111
```
Some data to play with I just made a Java program if you want to mess with it:

```
public class PlayingAround {
public static void main(String... args) {
for (long i = 1; i < 19; i++) {
System.out.println("n="+ i + ", " +repunit(i) + " = " + Long.toBinaryString(repunit(i)) );
}
}

public static long repunit(long n) {
return (pow(10, n) - 1) / 9;
}

public static long pow(long a, long b) {
long c = 1;
for (long i = 0; i < b; i++) {
c *= a;
}
return c;
}
}
```

Answer 50

Oh you're converting it to binary

Answer 51

Oh yeah I forgot to mention I was interested in that and base 5, thanks for reminding me lol.

Answer 52

Hey you want to prove it or looking for some numbers?

Answer 53

its more or less proved by now @Catch.me :) let me put the proof in one reply quick

Answer 54

What's interesting me is the last digits converge to a repeating pattern ...000111000111 so I'm trying to see if there's some kind of pattern we can take from that to apply here.

Answer 55

By fermat's little thm we have (suggested by @mathmath333 earlier)
\[10^{p-1}-1\equiv 0 \pmod {p}\]

and we're searching for a prime \(p\) that satisfies
\[10^{n}-1\equiv 0 \pmod {p}\]

combining both we can conclude \(\large n | (p-1)\)
\(\blacksquare \)

Answer 56

by fermat we can say it is true for table of 12 ...

but why it true for table of 6 though

Answer 57

although table of 6 will cover the table of 12..

Answer 58

last digits for these reptunits in binary are \(\ldots 111000111000111\)

when n = 2,19,23 we get prime repunits
@Kainui could you generate a few more numbers xD

Answer 59

there cannot be any special pattern for primes just by changing the base.. but just wondering how the prime repunits look in binary overall

Answer 60

@mathmath333 once we find that \( n | (13-1)\), we keep testing all the factors of \(12\)

Answer 61

factors of 12 are {1,2,3,4,6,12}
By testing them from least factor, we can conclude n=6 gives the smallest number divisible by 13

Answer 62

i was wondering it generates a new problem

to prove

\(\large\tt \begin{align} \color{black}{

\dfrac{10^{6n}-1}{9} (mod~13) \equiv 0 \hspace{.33em}\\~\\
}\end{align}\)

Answer 63

did i miss too much xD

Answer 64

are you suggesting every 6th repunit is a multiple of 13 ?

Answer 65

that looks pretty interesting xD

Answer 66

yes :)

Answer 67

i was like amazed by this
\(\Large 111... = \sum_{k=0}^{n-1}10^k \equiv \dfrac{10^n-1}{9} \pmod {p} \)
now let n|p-1
then by fermat this holds
\(\Large 111... = \sum_{k=0}^{n-1}10^k \equiv \dfrac{10^{p-1} -1}{9} \pmod {p} \)

Answer 68

yes i feel bit down for not thinking that lol, i had no clue about it till @mathmath333 suggested >.<

Answer 69

the funny thing im trying to review primitive roots and it dint come into my mind :P

Answer 70

it was obvious by looking 13 which is prime

Answer 71

xD im idiot lol

Answer 72

ok so now what are u trying to find ?

Answer 73

I think I fell asleep at my keyboard, I'm out! Try wolfram alpha for more binaries, unfortunately the long data type breaks down after that point, not enough digits in memory. You need to use BigInteger or something I think to do that. Ok goodnight, have fun. XD

Answer 74

why binary :O
what have i missed :(

Answer 75

Maybe we should try working on project euler questions some time? This might interest you https://projecteuler.net/problem=35

Answer 76

looks we have proved more than what the problem is asking for :

can we conclude if \(R_n\) is the least repunit number thats divisible by \(p \gt 5\), then every \(nk\)'th repunit is also divisible by \(p\) ?

(\(k \in \mathbb{N}\))

Answer 77

yep indeed!

Answer 78

evidence :
https://www.wolframalpha.com/input/?i=Table%5B%2810%5E%286n%29-1%29%2F9+mod+13%2C+%7Bn%2C1%2C100%7D%5D

im still bit unsure if it works in general though

Answer 79

@Kainui that question looks more like programming xD i remember working it with @dan815 couple of years ago

Answer 80

ok since n|p-1
from fermat
10^p-1 =1 mod p
so this hold (n is order of 10 from pattern )
10^n=1 mod p
\(\Large \dfrac{10^n-1}{9}=0 \pmod {p}\)

thus
\(\Large \dfrac{10^nk-1}{9}=0 \pmod {p}\)

Answer 81

\(\Large \dfrac{10^{nk}-1}{9}=0 \pmod {p}\)*

Answer 82

how do you know \(n\) is the order of \(10\) for all primes ?

Answer 83

from pattern we got( order only for p's that the pattern divide)

\(\Large 111... = \sum_{k=0}^{n-1}10^k \equiv \dfrac{10^n-1}{9} \pmod {p}\)

right ?
gcd(9,p)=1 since p>5
thus
\( 10^n-1 =0 \pmod {p}\)
\( 10^n =1 \pmod {p}\)

Answer 84

i might been late xD

Answer 85

yes \(10^n \equiv 1 \pmod p \) part is clear
how do you know there is not true for any other integer less than \(n\) ?

Answer 86

thats the definition of order right ?

Answer 87

any other integer less than n have the order let be k
then k=vn done :P

Answer 88

yeah but u got what im saying right ?

Answer 89

not yet, let me read again

Answer 90

order of \(a\) in \(\mod~n\) is the smallest positive integer \(k\) satisfying \(a^k \equiv 1\pmod n\)

Answer 91

\( a^k\equiv a^v \equiv 1\pmod n \)
and k<v
then k|v

Answer 92

OMG! okay i got it xD

Answer 93

there cannot be any integers less than \(n\) satisfying the given congruence because \(R_n\) is the smallest repunit thats divisible by \(p\)

that makes \(n\), the order of 10 in mod p

pretty neat xD

Answer 94

Very Interesting

Answer 95

that gives me an idea for our main lovely problem

Answer 96

oh ur enjoying it @marylou004