0
$\begingroup$

I was trying to solve a problem which states:

How many two-digit numbers have remainder 1 when divided by 3 and remainder 2 when divided by 4?

and solved it by writing down individual numbers...

Looking at the solution, I was baffled by the explanation :

The lowest common multiple of 3 and 4 is 12. Hence both of the required conditions are satisfied only by numbers that are 2 less than multiples of 12 and also less than 100, ie: 10, 22, 34, 46, 58, 70, 82 and 94.

Why on earth does the number have to be 2 less than multiples of 12? Could someone offer a better explanation please?

$\endgroup$
1
$\begingroup$

remainder 1 when divided by 3
$x \equiv 1 \pmod 3$
$x \equiv -2 \pmod 3$

remainder 2 when divided by 4
$x \equiv 2 \pmod 4$
$x \equiv -2 \pmod 4$

And so $x \equiv -2 \pmod 3$ $x \equiv -2 \pmod 4$

Since 3 and 4 are relatively prime, this implies that we can combine the two equations to
$x \equiv -2 \pmod {12}$

Another way of looking at this is

$x \equiv -2 \pmod 3$ means that $x = 3n - 2$ for some $n$, or $x + 2 = 3n$ for some n.

Similarly, $x + 2 = 4m$ for some m.

Hence $3n = x + 2 = 4m$. Since $\gcd(3,4) = 1, $ then m must be a multiple of 3.

It follow that $x + 2 = 4m = 12r$ for some $ m = 3r.$

finally, $ x = 12r - 2$.

$\endgroup$
1
$\begingroup$

In base-twelve, with digits 0123456789AB,

  • Multiples of 3 end in the digit 0, 3, 6, or 9. Numbers that are 1 more than a multiple of 3 thus end in 1, 4, 7, or A (ten).
  • Multiples of 4 end in the digit 0, 4, or 8. Numbers that are 2 more than a multiple of 4 thus end in 2, 6, or A.

So in order for a number to meet both criteria, its dozenal representation must end in the digit A. This means it's 2 less than a multiple of twelve.

$\endgroup$
-1
$\begingroup$

This is a consequence of the Chinese Remainder Theorem: https://en.wikipedia.org/wiki/Chinese_remainder_theorem

$\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.