Consider an algorithm for positive integers and -
Take any multiple of . Multiply the last digit by and then, add the resulting number to the remaining number to get a number .
For Example - For , and multiple of , the algorithm would give you .
How many values of are there such that there exists at least one for which is always a multiple of ?
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.
The problem is inspired by a comment of Ashwin Padaki in the discussion Divisble by 7? .
Let c = a p a p − 1 . . . . . . . . . . a 0 be any multiple of n . As the algorithm involves only the last digit and the remaining number, let's reduce this whole number to x y where y = a 0 and x = a p a p − 1 . . . . . . . . . a 1 ( m o d n ) .
The algorithm is multipying y by k and adding it to x .
So, we will be left with the number
a = x + k ⋅ y and we are required to find the number of n 's for which a = 0 ( m o d n ) .
Now note that
1 0 ⋅ a ( m o d n ) = 1 0 ⋅ x + 1 0 k ⋅ y ( m o d n )
Now, a = 0 ( m o d n )
⇒ 1 0 a = 0 ( m o d n )
⇒ 1 0 x + 1 0 k y = 0 ( m o d n )
⇒ 1 0 x + y − y + 1 0 k y = 0 ( m o d n )
⇒ y ( 1 0 k − 1 ) = 0 ( m o d n ) {because its given that- 1 0 x + y = 0 ( m o d n )
⇒ 1 0 k = 1 ( m o d n )
Note that a k satisfying the above derived condition exists for all those n and only for all those n having there last digit as any of 1 , 3 , 7 and 9 .
There are 400 such numbers less than 1 0 0 0 .
Thus the answer is 4 0 0 .