Number made up of 1's

If f(n)=111...11, where there are 'n' 1s, then what is the minimum value of n so that f(n) is divisible by 9, 13, and 17?

(Just in case you were confused, f(1)=1, f(2)=11, f(3)=111, f(4)=1111, f(5)=11111...)


The answer is 144.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Nick Lee
Oct 7, 2014

First, in order for f(n) to be divisible by 9, n has to be multiple of 9 by the divisibility rule. Now, rewrite f(n) as following: f ( n ) = 111...11 = 999...99 9 = 10 n 1 9 f(n)=111...11=\frac { 999...99 }{ 9 } =\frac { { 10 }^{ n }-1 }{ 9 } Since f(n) also has to be divisible by 13 and 17, f ( n ) = 10 n 1 9 0 ( m o d 13 ) 10 n 1 ( m o d 13 ) N o w , t h e F e r m a t s L i t t l e T h e o r e m s t a t e s t h a t a p a ( m o d p ) o r a p 1 1 ( m o d p ) w h e r e p i s p r i m e . S i n c e 13 i s p r i m e , 10 13 1 1 ( m o d 13 ) . n h a s t o b e a m u l t i p l e o f 12 S i m i l a r l y , s i n c e 17 i s a l s o p r i m e , 10 17 1 1 ( m o d 17 ) n h a s t o b e a m u l t i p l e o f 16 f(n)=\frac { { 10 }^{ n }-1 }{ 9 } \equiv 0\quad (mod\quad 13)\rightarrow { 10 }^{ n }\equiv 1\quad (mod\quad 13)\\ Now,\quad the\quad Fermat's\quad Little\quad Theorem\quad states\quad that\\ { a }^{ p }\equiv a\quad (mod\quad p)\quad or\quad { a }^{ p-1 }\equiv 1\quad (mod\quad p)\quad where\quad p\quad is\quad prime.\\ Since\quad 13\quad is\quad prime,\quad { 10 }^{ 13-1 }\equiv 1\quad (mod\quad 13).\\ \therefore \quad n\quad has\quad to\quad be\quad a\quad multiple\quad of\quad 12\\ Similarly,\quad since\quad 17\quad is\quad also\quad prime,\quad { 10 }^{ 17-1 }\equiv 1\quad (mod\quad 17)\\ \therefore \quad n\quad has\quad to\quad be\quad a\quad multiple\quad of\quad 16

In conclusion, n has to be a multiple of 9, 12, and 16. Therefore, the minimum value of n is the least common multiple of 9, 12, and 16, which is 144.

very nice!!

satyendra kumar - 6 years, 7 months ago

This solution is not totally correct. Note that 1 0 6 1 10^6 \equiv 1 mod 13 13 , so n n actually only has to be a multiple of 6 6 in order for f ( n ) f(n) to be divisible by 13 13 . You need to find the multiplicative orders of 10 10 mod 9 , 13 , 17 9,13,17 and then take the LCM. (In this case, the answer is still 144 144 .)

Patrick Corn - 6 years, 7 months ago

This is such an intricate problem. It was under-rated. I've boosted it to level 4.

Krishna Ar - 6 years, 7 months ago

did the same! nice!

Kartik Sharma - 6 years, 7 months ago

Uncorrect f(17) is divisible by 9, 13, 17 Therefore the answer is wrong. Or I didn't understand the question

Humberto Bento - 6 years, 7 months ago

Log in to reply

f(17) is not divisible by 9,13,17. Clearly that f(17) is not divisible by 3.

Samuraiwarm Tsunayoshi - 6 years, 7 months ago

Log in to reply

yup.My calculation had a mistake

Humberto Bento - 6 years, 7 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...