Here is a question: What is the remainder when 123456789 × 987654321 is divided by 6 ?
This is the given answer: The sum of the digits of both numbers is 45, so both are multiples of 3. Also, both numbers are odd so their product is an odd multiple of 3. Hence there is a remainder of 3 when the product is divided by 6.
This is how I did it: Both numbers are divisible by 3. When you divide both numbers by 3, you still have to divide by 2 (to get the 6). Both numbers (when they have been divided by 3) are odd numbers. The remainders of both of these, when they are divided by 2, is 1. So the overall remainder is 1*1 = 1. (This is because, when you divide by 3, you are left with an odd number and an odd number divided by 2 gives you one)
Could someone please clarify what is wrong in my thinking and my approach? Many thanks.
Best Answer
We seek $\,ab\bmod 6\,$ where both $a,b$ are odd and multiples of $\,3$.
You correctly infer $\,a = 3(1\!+\!2j),\ b = 3(1\!+\!2k),\,$ then incorrectly infer $\, ab \equiv 1\pmod{\!6}$
But $\bmod 6\!:\ ab = (3\!+\!6j)(3\!+\!6k)\equiv (3)(3)\equiv 3,\,$ not $\,1.\,$
It seems you believe $\ 3n\bmod 6 \ =\ n\,\bmod\, 2\,\ $ [$=1\,$ for odd $\,n\,$]
However, correct is: $\, 3n\bmod 6 = 3(n\bmod 2)\ $ [$=3\,$ for odd $\,n\,$] $ $ by $ $ $\!\!\bmod\!$ Distributive Law
Generally: $\ 3\mid b\Rightarrow 3ab\bmod 6 = 3(ab/3 \bmod 2) = 3(ab\bmod 2)\ $ [$= 3\,$ if $a,b$ both odd, else $0$]