Test your smartness

Number Theory Level 4

How many numbers of the form 30 a 0 b 03 ‾ \overline{30a0b03} , where a a and b b are single digits, are divisible by 13?


The answer is 7.

Shivam Agrawal by Shivam Agrawal , 21, India

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.

2 solutions

30 a 0 b 03 ‾ ≡ 3000003 + 10000 a + 100 b (mod 13) ≡ 6 + 3 a + 9 b (mod 13) ≡ 3 ( 2 + a + 3 b ) (mod 13) \begin{aligned} \overline{30a0b03} & \equiv 3000003 + 10000a + 100b \text{ (mod 13)} \\ & \equiv 6 + 3a + 9b \text{ (mod 13)} \\ & \equiv 3(2 + a + 3b) \text{ (mod 13)} \end{aligned}

Therefore, we have:

2 + a + 3 b = 13 n where n is non-negative integer. ⟹ 3 b = 13 n − 2 − a \begin{aligned} 2+a+3b & = 13\color{#3D99F6}n & \small \color{#3D99F6} \text{where }n \text{ is non-negative integer.} \\ \implies 3b & = 13n - 2 - a \end{aligned}

Since 0 ≤ b ≤ 9 0 \le b \le 9 ⟹ 0 ≤ 13 n − 2 − a ≤ 27 \implies 0 \le 13n - 2 - a \le 27 ⟹ 0 ≤ 13 n − 2 − 9 \implies 0 \le 13n - 2 - 9 ⟹ n ≥ 1 \implies n \ge 1 also 13 n − 2 − 0 ≤ 27 13n - 2 - 0 \le 27 ⟹ n ≤ 2 \implies n \le 2 . Therefore, n = 1 , 2 n = 1, 2 .

From 3 b = 13 n − 2 − a 3b = 13n - 2 - a ,

⟹ b = 13 n − 2 − a 3 = { n = 1 ⟹ b = 11 − a 3 ⟹ ( a , b ) = ( 2 , 3 ) , ( 5 , 2 ) , ( 8 , 1 ) n = 2 ⟹ b = 24 − a 3 ⟹ ( a , b ) = ( 0 , 8 ) , ( 3 , 7 ) , ( 6 , 6 ) , ( 9 , 5 ) \implies b = \dfrac {13n-2-a}3 = \begin{cases} n = 1 & \implies b = \dfrac {11-a}3 & \implies (a,b) = (2,3), (5,2), (8,1) \\ n = 2 & \implies b = \dfrac {24-a}3 & \implies (a,b) = (0,8), (3,7), (6,6), (9,5) \end{cases}

Therefore, there are 7 \boxed{7} such numbers.

2 Helpful 0 Interesting 0 Brilliant 0 Confused

This line is not true

6 + 3 a + 9 b (mod 13) ≡ 2 + a + 3 b (mod 13) 6 + 3a + 9b \text{ (mod 13)} \equiv 2 + a + 3b \text{ (mod 13)}

Mr X - 3 years, 8 months ago

Log in to reply

Thanks. I have changed it.

Chew-Seong Cheong - 3 years, 8 months ago

30 a 0 b 03 ‾ ≡ 3000003 + 10000 a + 100 b (mod 13) ≡ 6 + 3 a − 4 b ) (mod 13) ⟹ 6 + 3 a − 4 b = 13 n − 6 ∵ 3 a = 27 a n d − 4 a = − 36 m a x i m u m v a l u e s f o r a a n d b . W e m a k e a t a b l e f o r 3 a a n d − 4 b f o r a , b f r o m 0 t o 9 I n s p e c t i n g t h e t a b l e a n d o b s e r v i n g w h e r e w e g e t 3 a − 4 b = 13 n − 6 , w h e r e n i s a n i n t e g e r . F o r e v e r y a , b , b e t w e e n 0 t o 9 3 a a n d − 4 b r a n g e s f o r b = 9 t o a = 9 , t h a t i s f r o m − 32 t o + 27. T h i s l i m i t s n t o b e w i t h i n − 2 t o + 2. A s s h o w n b e l o w i n t h e N o t e f o l l o w i n g s a t i s f i e s o u r c o n d i t i o n , t h a t i s d i v i s i b i l i t y b y 13. ( a , b ) = ( 0 , 8 ) / ( 2 , 3 ) / ( 3 , 7 ) / ( 5 , 2 ) / ( 6 , 6 ) / ( 8 , 1 ) / ( 9 , 5 ) . T h e s e a r e 7 v a l u e s . N o t e : F o r a = 0 t o 9 , 3 a = 3 . . . . . 6 . . . . . 9 . . . . . 12 . . . . . 15 . . . . . 18 . . . . . 21 . . . . . 24 . . . . . 27. F o r b = 0 t o 9 , − 4 b = − 4 . . . . − 8 . . . . − 12 . . . . − 16 . . . . − 20 . . . . − 24 . . . . − 28 . . . . − 32 . . . . − 36 3 a − 4 b = 13 n − 6 , ∴ f o r n = − 2 , 13 n − 6 = − 32........... f r o m v a l u e s o f a , a n d b a b o v e a = 0 a n d b = 8. O n l y p o s s i b l e . ∴ f o r n = − 1 , 13 n − 6 = − 19........... f r o m v a l u e s o f a , a n d b a b o v e a = 3 a n d b = 7. O n l y p o s s i b l e . ∴ f o r n = 0 , 13 n − 6 = − 6........... f r o m v a l u e s o f a , a n d b a b o v e a = 2 a n d b = 3. a n d a = 6 a n d b = 6 O n l y p o s s i b l e . ∴ f o r n = + 1 , 13 n − 6 = + 7........... f r o m v a l u e s o f a , a n d b a b o v e a = 5 a n d b = 2. a n d a = 9 a n d b = 5 O n l y p o s s i b l e . ∴ f o r n = + 2 , 13 n − 6 = 20........... f r o m v a l u e s o f a , a n d b a b o v e a = 8 a n d b = 1. O n l y p o s s i b l e . S o ( a , b ) = ( 0 , 8 ) / ( 2 , 3 ) / ( 3 , 7 ) / ( 5 , 2 ) / ( 6 , 6 ) / ( 8 , 1 ) / ( 9 , 5 ) . I n t e r e s t i n g ! ! ! ( 0 , 8 ) , ( 3 , 7 ) , ( 6 , 6 ) , ( 9 , 5 ) ( 1 , X ) , ( 4 , X ) , ( 7 , X ) , ( 2 , 3 ) , ( 5 , 2 ) , ( 8 , 1 ) \color{#D61F06}{\overline{30a0b03} ~~ \equiv 3000003 + 10000a + 100b \text{ (mod 13)} \\ \equiv 6 +3a - 4b) \text{ (mod 13)} \\ \implies~ 6 + 3a-4b=13n~-6~~~~~~~~~~\because~~ 3a=27~and~-4a=-36 ~maximum~values~for ~a~and~b.\\ We~make~a~table~for~ 3a~and ~-4b~~~~ for~ a,b~~from~0~to~9\\ Inspecting~ the~ table~and~observing~where~we~get~3a-4b~=~~13n-6,~~where~n~is~an~integer. \\ For~every~a,~ b,~~between~~0~to~9~~~3a ~and~~-4b~ranges ~for~~~b=9~~to~~a=9,~~that~is~~from~~-32~~to~~+27.\\ This~limits~n~to~be~within~~-2~~to~~+2.\\ As~shown~below~in~the~Note~following~satisfies~our~condition,~~that~is~divisibility~by ~13.\\ (a,b)~=~(0,8)/(2,3)/(3,7)/(5,2)/(6,6)/(8,1)/(9,5). ~~These~are~\Large {\color{#D61F06}{7}}~values.}\\ ~~~~~~\\ \color{#3D99F6}{Note: \\ For~a~=~0~to~9, ~~~~~~~3a=~~3~.....~~6~.....~~9~.....~~12~.....~~15~.....~~18~.....~~21~.....~~24~.....~~27.\\ For~b~=~0~to~9, ~~-4b=-4~....-8~....-12~....-16~....-20~....~-24~....-28~....-32~....-36\\ 3a~-~4b=13n-6,\\ \therefore~~for~n=~-2,~~~13n~-6=~-32...........from~values~of~a,~and~b~above~a=0~~and~~b=8. ~Only~possible. \\ \therefore~~for~n=~-1,~~~13n~-6=~-19...........from~values~of~a,~and~b~above~a=3~~and~~b=7. ~Only~possible. \\ \therefore~~for~n~=~~~0,~~~~13n~-6=~-~6...........from~values~of~a,~and~b~above~a=2~~and~~b=3.~~and~a=6~~and~~b=6 ~Only~possible. \\ \therefore~~for~n=~+1,~~13n~-6=~+7...........from~values~of~a,~and~b~above~a=5~~and~~b=2.~~and~a=9~~and~~b=5 ~Only~possible. \\ \therefore~~for~n=~+2,~~~~13n~-6=~20...........from~values~of~a,~and~b~above~a=8~~and~~b=1. ~Only~possible. \\ So~~(a,b)~=~(0,8)/(2,3)/(3,7)/(5,2)/(6,6)/(8,1)/(9,5).\\ ~~~~~\\ Interesting!!! ~~(0,8),(3,7),(6,6),(9,5) ~~~~~(1,X),(4,X),(7,X),~~~~~(2,3),(5,2),(8,1) }

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...