Question

show that every odd integer is either divisible by \(5\) or divides some integer of form \(111\ldots\)

Answer 1

\(111\ldots\) is an integer with all \(1\)'s

Answer 2

what grade is that, it looks complex

Answer 3

12?

Answer 4

if the odd integer ends with 5 it will be divided by 5
or else it can end with 1 or 3 or 7 or 9
now we have to prove that any odd integer which does not end in 5 will divide 111....

the prime factorization of the that odd integer will be like this-\[n=3^a7^b9^c\]
where a,b,c>=0

now if we prove that 111..... is divisible by 3, 7, 9 we are done

111 is divisible by 3 so 111..... is also divisible by 3^a
111111 is divisible by 7 and also by 9 so 111... is also divisible by 7^b and 9^c as well

Answer 5

what about prime numbers that end with those digits..
23, 19 ...

Answer 6

so we just need to prove that 111.. is divisible by all odd primes

Answer 7

The condition is strange. when you say an integer with 111's, are you meaning that it should also be divisible by 1111, 11111, 11, 1? or just specifically the number 111? or a combination of 111's such as 111, 111111, 111111111?

Answer 8

looks @mom. has a great start...

@LanHikari22 , some examples... consider few odd numbers

3 divides 111111111111111111

7 divides 111111111111111111111111111111111111

9 divides 111111111111111111111111111111111111111111111111111111

11 divdes 111111111111111111111111111111111111111111111111111111111111

13 divides 111111111111111111111111111111111111111111111111111111111111111111111111

Answer 9

Other than multiples of 5,
we need to show that for every odd integer there exists a multiple with all 1's

Answer 10

let me know if the question is still not clear...

Answer 11

Umm. If the number of 1's is unimportant then:
We already covered 2 cases.
If the digital root of a number that has 1111's is 3,6, or 9: it's always divisible by 3.
If the digital root of the number is 9, then it's a multiple of 9.
Digital root is always the sum of the value of all bits.
Now you need to see the case in which you prove a number is mul7
does that work?

Answer 12

The rule allows us to have any number of 11's so, that enables us to create a digital root that ranges from 0 to 9, which in return proves that any mul3 and mul9 can be divisible by such numbers that have similar digital roots, or at least I'd say so. Correct me if I'm wrong

Answer 13

for 7, I found on the internet this weird check:
Take the last digit of the number you're testing and double it. Subtract this number from the rest of the digits in the original number. If this new number is either 0 or if it's a number that's divisible by 7, then you know that the original number is also divisible by 7.
I guess it can also be proved that 1111's can produce any said combination. It's precisely because the digital root produced of these 1's is any number that actually allows us to do this!

Answer 14

this wont work, you will have to prove case by case for every odd prime number

Answer 15

hmm. yeah that's true

Answer 16

yeah that is a dead end..

Answer 17

i've tried playing around with remainders,

if 'n' us our odd number, it has to end with 1,3,7,9

and n * x=1111....

we can easily tell the last digit of x ( 1,7,3,9 correspondingly), and we can tell the remainder just before the division 1111.../n terminates

for example if 73 was our number, x would have to end with the digit 7,
and the last remainder before division terminates would have to be ((73*7)-1)/10
=51

Answer 18

thats all ive got

Answer 19

i cant prove that such a remainder is guaranteed to occur at some point

Answer 20

73 divides a number with 432 ones

Answer 21

and yes, last digit of x here is 7

Answer 22

DL(73) = 10, while DL(432) = 9. I wonder if this pattern has any meaning or is a coincidence?

Answer 23

i will read that as a clue, you have found some correlation between number n and and the number of 1's it will take

Answer 24

yes, if you give me any odd integer, i can give you a multiple with all 1's
the proof i have is based on the construction...

Answer 25

that is intereting @LanHikari22

Answer 26

for example if 73 was our number, x would have to end with the digit 7,
and the last remainder before division terminates would have to be ((73*7)-1)/10
=51

@baru i see why the last digit has to be 7
but i don't see how you figured out the last remainder before division terminates is 51...

Answer 27

when 7 is the last digit, it means 7 is the last digit of the quotient,

quotient * divisor = 7* 73 =511

so at the last step of division we get 511-511,

which would mean that the previous remainder had to be 51

Answer 28

Ahh okay, you're doing long division of 111... by 73 and looking at the last remainders, nice

Answer 29

i saw a few theorems on prime numbers can came across this-
to prove that 111.... is divisible by all odd primes
we can use fermats little theorem which says that if p is a prime and a is some number such that p does not divide a then
\[a^{p-1}=1(modp)\]

any odd prime number will not divide 10
so let the odd prime be p

and we can write 111.... as [10^(p-1)-1]/9
so
when we divide 10^(p-1) by p the remainder will be 1 and when we divide 1 by p remainder will be 1
so 1-1=0
this means that p will divide 11......

Answer 30

Awesome!

does that that prove :
an odd prime, \(p\gt 5\), divides \(\dfrac{10^{p-1}-1}{9}\), which is an integer with \(p-1\) ones.

?

Answer 31

Now, what about the odd numbers that are not primes ?

Answer 32

hmm i made some errors in my 1st comment
yes we should take it to be greater than 5
or can we say odd prime number except 5? because 3 can be acceptable

Answer 33

your proof fails for p = 3, 5

Answer 34

p = 3 case has to be worked separately

Answer 35

but why can't we apply the theorem to p=3?
when p=3
10 is not divisible by 3
so it should work fine?

Answer 36

Let me give you a detailed version of your proof, then you will see why p=3 case fails

Answer 37

any prime \(p\gt 5\) divides \(\dfrac{10^{p-1}-1}{9}\)

proof :
Whenever \((10,p)=1 \), from little fermat we have
\[10^{p-1}\equiv 1\pmod{p}\]

which is same as
\[10^{p-1}-1\equiv 0 \pmod{p}\]
factoring the left hand side gives
\[(10-1)(10^{p-2}+10^{p-3}+\cdots+10+1)\equiv 0 \pmod{p}\]

which is same as
\[\color{red}{9}(111\ldots (\text{p-1 times}))\equiv 0 \pmod{p}\]

that means
\(p\) divides \(\color{red}{9}(111\ldots (\text{p-1 times})) \)

from euclid lemma, it follows
\(p\) divides \(\color{red}{9}\) or \(111\ldots (\text{p-1 times}) \)

Answer 38

when \(p\) is \(3\), it divides \(\color{red}{9}\).
so there is no guarantee that it divides \(111\ldots (\text{p-1 times})\) too.

Answer 39

well u can always pick a multiple of 9 1s so