1

Find the sum of all four digit natural numbers of the form $4AB8$ which are divisible by $2,3,4,6,8$ and $9$

I know that I can ignore the conditions of 2,3,4 and 6 because checking for divisibility by 8 and 9 would be sufficient to satisfy all conditions.

To check for divisibility by 9, I need to make sure that all the digits summed up would be divisible by 9. So $$4+A+B+8\equiv 0 (\textrm{mod} 9)$$ Since $$0\leq A+B\leq 18$$, $$A+B=6$$ or $$A+B=15$$

Now checking for divisibility by 8, I need to make sure that the last 3 digits are divisible by 8. I.e. $$100A+10B+8\equiv 0 (\textrm{mod} 8)$$ This simplifies to $$10A+B\equiv 0 (\textrm{mod}8)$$ Applying the previous equations from the divisibility by 9, I can get that: $$9A\equiv -6 (\textrm{mod} 8)$$ and $$9A\equiv -15 (\textrm{mod}8)$$

This would further simplify to: $$9A\equiv 18 (\textrm{mod} 8)$$ and $$9A\equiv 9 (\textrm{mod}8)$$ which would give me $$A=1,2,9$$ and $$B=5,4,6$$ respectively.

The pairs $(2,4)$ and $(9,6)$ work but $4158$ is not divisible by $8$. I'm not too sure where I went wrong but I'm new to modular arithmetic and any help is appreciated. Thank you!

ItsImpulse
  • 417
  • @user49640 Thanks for correcting my mistake - I thought the OP was checking the cases divisible by 8 or by 9, instead of 8 and 9. – Toby Mak Jun 15 '17 at 06:29
  • 2
    I see a mistake where you wrote $10A + B \equiv 0$ modulo 8. Here you are dividing by 10, but 10 is not invertible modulo 8. What you can do instead is divide by 5 (which is equivalent to multiplying by 5, since 5 is its own inverse mod 8). Then you get $20A + 2B \equiv 0$ modulo 8. Now, because 2 divides 8, what you get at the next stage is slightly different. The condition is equivalent to $10A + B \equiv 0$ mod 4, or $2A + B \equiv 0$ modulo 4. – user49640 Jun 15 '17 at 06:31
  • @user49640 ah I see, I didnt realise that division isn't the same under modular arithmetic. Thank you! – ItsImpulse Jun 15 '17 at 06:41
  • 1
    @ItsImpulse Division works roughly the same way if the number you're dividing by is invertible with respect to the modulus. For example, 5 is invertible modulo 14, because 5 times 3 is 1 modulo 14. Another way you can recognize this is to see whether 5 is relatively prime to 14. (It is.) – user49640 Jun 15 '17 at 06:48
  • @user49640 however, using the fact that $2A+B\equiv 0 \mod 4$ and $A+B=6$ or $A+B=15$, I will get that $A=1,2,5,6,9$ which doesn't solve the problem either. Sorry if this is an inconvenience. – ItsImpulse Jun 15 '17 at 07:18
  • $A$ can't be 1 or 5. Remember that $0 \leq B \leq 9$. – user49640 Jun 15 '17 at 19:08

0 Answers0