Divisibility problem with modular arithmatic

Here's the question:

"When an integer $n$ is divided by 6, the remainder is 5. What are the possible values of the remainder when $9n$ is divided by 8?"

I'm not entirely sure how to decipher this questions because I'm having a hard time understanding it. Does the first part mean: $n = 6k + 5$ where $5$ being the remainder?

Answer

You're correct that $n = 6k + 5$ for some $k$. When we multiply this equation by 9, we get $9n = 54k + 45$. The goal is to understand what happens when we divide by 8, so we want to divide 54 and 45 by 8 and see what we get. Well, 54 = 6*8 + 6 and 45 = 8*5 + 5, so we can shuffle some things around and see that $9n = 8(6k + 5) + 6k + 5$. So to understand what happens to $9n$ when we divide by $8$, we just need to understand what happens to $6k + 5$ when we divide by 8.

Now, remember that we don't know anything about the $k$. It can be anything. So let's try and spot a pattern. If $k = 0$, then we just have $5$, and so the remainder is $5$. Here are a few other values of $k$:

• $k=1$ gives 11, which when divided by 8 leaves 3 left over.


• $k=2$ gives 17, which when divided by 8 leaves 1 left over.


• $k=3$ gives 23, which when divided by 8 leaves 7 left over



• $k=4$ gives 29, which when divided by 8 leaves 5 left over.

Note we saw the pattern 5,3,1,7, and then went back to 5. If you keep going with more $k$, and try things like negative $k$, you'll notice this pattern seems to repeat over and over again. So you might guess the possible values are 5,3,1,7. We definitely have the values of $k$ that give these, but how do we know that $k=-18952898529$ won't give us something different?

It looks like our list repeats over and over again with period 4, so lets divide $k$ by 4 and take the remainder. So we write $k = 4a + b$, where $b$ is either $0,1,2,3$, and $a$ is just some number. We're interested in what happens when you divide $6k + 5$ by $8$, so substituting leaves us with understanding what happens to $6(4a + b) + 5 = 24a + 6b + 5$ divided by $8$. But we can rewrite this as $8(3a) + 6b + 5$, so now we just need to see what happens when we divide $6b + 5$ by $8$. But we know that $b$ can only be the numbers $0,1,2,3$! The resulting numbers are then $5,11,17,23$, and the remainders of these after dividing by $8$ are just $5,3,1,7$, which is exactly what we want.