Remainder of a product of numbers

Question

When the positive integer N is divided by 6, the remainder is 3. When the positive integer M is divided by 4, the remainder is 1. Which of the following integers could be the remainder when the product of the two numbers, NM, is divided by 12? Indicate all such integers. 1 3 5 7 9 My approach is N is an odd multiple of 3 -> I represent it as 3n M can be represented as 4m + 1 NM=3n(4m +1) now NM / 12 = 3n(4m +1) /12 n*(4m +1) /4 -> 4nm +n /4 -> n/4 -> n is an odd number so n%4 will be 1 or 3 where did I go wrong?

Answer 1

The problem is that $3n$ does not necessarily represent an odd multiple of $3$; this is ensured only when $n$ itself is odd. To represent it unambiguously as an odd multiple of $3$, write N as $3(2n+1)$ instead. Now multiply this with $4m+1$ and you get $MN = (4m+1)(6n+3) = 24mn+12m+6n+3$. Obviously, $24mn \equiv 12n \equiv 0 \mod(12)$, so the whole expression is congruent to $6n+3$ mod($12$) which itself is equal to $3(2n+1)$. In other words, which congruence classes mod(12) are the product of $3$ and an odd number? There are just two: $3$ and $9$.