0
$\begingroup$

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.

$\endgroup$
6
  • 2
    $\begingroup$ Which remainder when divided by 6, also yields a remainder of 0 when divided by 3 and a remainder of 1 when divided by 2? $\endgroup$
    – Calvin Lin
    Oct 16, 2020 at 16:50
  • $\begingroup$ Borrowing notation from computer science... a%(pq) is not necessarily the same as (a%p)%q. $\endgroup$
    – JMoravitz
    Oct 16, 2020 at 17:14
  • $\begingroup$ Thanks @CalvinLin - I'm not quite sure what it is that you are asking. Would you mind rephrasing. Terribly sorry for not understanding . $\endgroup$
    – vgupt
    Oct 16, 2020 at 17:18
  • 1
    $\begingroup$ Calvin is trying to get you to recognize what is more generally known as the Chinese Remainder Theorem... in this specific case that knowing that if $x$ leaves remainder $1$ when divided by two and leaves remainder $0$ when divided by three that this is enough information to know that $x$ leaves remainder three when divided by six, not $1$. $\endgroup$
    – JMoravitz
    Oct 16, 2020 at 17:24
  • $\begingroup$ You wound up for some reason chaining these divisions and remainders together in a nonsensical way which yielded an incorrect result. You wound up "dividing by three and then dividing by two" to get a remainder of $1$ and thinking that this final remainder was what would have been the remainder if you had divided by six. That is simply wrong. $\endgroup$
    – JMoravitz
    Oct 16, 2020 at 17:26

1 Answer 1

1
$\begingroup$

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$]

$\endgroup$
1
  • $\begingroup$ Thanks @Bill Dubuque $\endgroup$
    – vgupt
    Oct 17, 2020 at 6:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .