A Story of an Algorithm

Consider an algorithm for positive integers n n and k k -

Take any multiple of n n . Multiply the last digit by k k and then, add the resulting number to the remaining number to get a number a a .

For Example - For n = 7 n=7 , k = 3 k=3 and multiple of 7 = 105 7=105 , the algorithm would give you a = 10 + 5 × 3 a=10+5×3 .

How many values of n < 1000 n <1000 are there such that there exists at least one k k for which a a is always a multiple of n n ?

Like this one? This is also nice.


The answer is 400.

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

Dhruv Bhasin
Jun 4, 2015

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 c=\overline {a_p a_{p-1} ..........a_0} be any multiple of n n . As the algorithm involves only the last digit and the remaining number, let's reduce this whole number to x y \overline{xy} where y = a 0 y=a_0 and x = a p a p 1 . . . . . . . . . a 1 ( m o d n ) x= \overline{a_p a_{p-1}.........a_1} (mod n) .

The algorithm is multipying y y by k k and adding it to x x .

So, we will be left with the number

a = x + k y a=x+k\cdot y and we are required to find the number of n n 's for which a = 0 ( m o d n ) a=0 (mod n) .

Now note that

10 a ( m o d n ) = 10 x + 10 k y ( m o d n ) 10\cdot a (mod n) = 10\cdot x+ 10k\cdot y (mod n)

Now, a = 0 ( m o d n ) a=0 (mod n)

10 a = 0 ( m o d n ) \Rightarrow 10a=0 (mod n)

10 x + 10 k y = 0 ( m o d n ) \Rightarrow 10x+10ky=0 (mod n)

10 x + y y + 10 k y = 0 ( m o d n ) \Rightarrow 10x+ y- y+ 10ky=0 (mod n)

y ( 10 k 1 ) = 0 ( m o d n ) \Rightarrow y(10k-1)=0 (mod n) {because its given that- 10 x + y = 0 ( m o d n ) 10x+y=0 (mod n)

10 k = 1 ( m o d n ) \Rightarrow 10k=1 (mod n)

Note that a k k satisfying the above derived condition exists for all those n n and only for all those n n having there last digit as any of 1 , 3 , 7 1, 3, 7 and 9 9 .

There are 400 such numbers less than 1000 1000 .

Thus the answer is 400 \boxed {400} .

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...