2
$\begingroup$

N is a number in base 9.Find N when n is divided by 8(in base 10)? And N can be very large.say N=32323232.....50 digits

This can be done by converting N to base 10.But time consuming.

What will be the fastest approach given that no proof is required.Like in a rapid fire round.Just Answer.

One solution is: In base 9,divisibility check for 8 is sum of the digits(digit sum).Digit sum of N=25(i.e from 25*3+25*2).Converting 25 to base 10 gives 23.Thus the question changes to (23*2+23*2) in base 10 i.e 115 in base 10.COnverting it back to base 9 gives 137.Now sum of digit in base 9 is 1+3+7 i.e 12.So answers is (1+2%8)=3

How to arrive at the rule in bold.Is there a general rule exist for such cases?Please provide the proof for the above?

Is there any faster way to solve this?

$\endgroup$
2
$\begingroup$

In base $b+1$ where integer $b\ge1$

as $b+1\equiv1\pmod b,(b+1)^r\equiv1^r\equiv1$

$$\sum_{r=0}^n(b+1)^ra_r\equiv \sum_{r=0}^na_r\pmod b$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.