Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

As a follow-up question, what can be said about multiples of $5$ in base 2?

I think I must look at the last two digits, but I am not sure what the whole idea might be.

share|improve this question

1 Answer 1

A starting point for a divisibility test (by 5) in binary would be the observation that $2^4\equiv1\pmod5$. Therefore also $2^{4n}\equiv1\pmod5$ for all natural numbers $n$. From that point on it is quite similar to the familiar "casting nines" method of testing divisibility by nine in base 10.

For example: $$ 110101001000_2=1101_2\cdot(16)^2+0100_2\cdot16^1+1000\equiv 1101_2+0100_2+1000_2=13+4+8=25\equiv0\pmod5. $$

In other words, you study groups of four bits at a time (starting from the least significant), and add the hexadecimal digits formed by these groups together. The result is divisible by five if and only if the original number is.

share|improve this answer
1  
we can further utilize $2^2=4\equiv-1\pmod 5,$ right? –  lab bhattacharjee Feb 24 '13 at 11:50
    
@lab: Correct, then the algorithm will look like the usual test for divisibility by eleven, IOW we look at an alternating sum. –  Jyrki Lahtonen Feb 24 '13 at 11:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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