1

I'm given a number 'C' in a known base, and the first few digits 'D' (rightmost) of the other number, in the same base. I'm also told that a certain number of a digit 'E' can be appended to the end of the number (on the left). Given all this information, is there any way to know how many of the digit needs to be appended in order to get a number that is divisible by 'C' without actually having to append 'E' to 'D' until I arrive at such a value?

For instance, given:

Base = 5 C = 43 (in base 5, 23 in base 10), D = 412 (in base 5, 107 in base 10), E = 4 (in base 5, 4 in base 10 as well)

Instead of repeatedly testing like: 412/43, 4412/43, 44412/43, 444412/43....

Is there any way to instantly know how many 4's I'd need to add?

Himanshu Goel
  • 11
  • Note that $43$ base $5$ is $23$ base $10$, not $25$. Fairly quickly (in this case) one can use the Pigeonhole Principle to get a crude upper bound. I do not see a quick way to find the smallest number of $4$'s (in general) though for $23$, it is not too bad, since $22$ does not have many factors. – André Nicolas Mar 15 '15 at 02:07
  • @AndréNicolas woops, fixed the error, thanks for pointing that out. I see how the pigeonhole principle could be used to get a crude bound, I already have an upper bound but I suppose I can make that tighter using it. Can you explain how you mean to get the smallest number of 4's knowing the factors of 22? – Himanshu Goel Mar 15 '15 at 02:31

0 Answers0