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?

  • 1
    $\begingroup$ Yes, that's what it means. $\endgroup$ Nov 2 '13 at 3:27

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.


The possible answers are 1,3,5 and 7. Here's how to solve it.
First, note that since the remainder when divided by 6 is 5, we know that $n = 6k + 5$
So, $9n = 9(6k+5) \equiv (48k + 40) + (6k + 5) \equiv (6k + 5)\mod{8}$.
So, $9n \equiv (6k + 5)\mod{8}$.
Also note that 6m + 5 = 6(m+4) + 5 (mod 8), so the remainders repeat with a period of 4.
So we only need to find the values for k = 0,1,2 and 3 (or any other four consecutive integers) to obtain all possible remainders. Which gives 1,3,5 and 7

  • $\begingroup$ Why is it that we only need to find values for k = 0,1,2,3 ? $\endgroup$
    – Dimitri
    Nov 6 '13 at 15:13
  • 1
    $\begingroup$ To rephrase what obinna said in that sentence: As you run through all $k\in\mathbb{Z}$, the remainders form a periodic sequence with period 4. So you only have to consider four consecutive $k$'s to determine all possible remainders. $\endgroup$
    – Casteels
    Nov 8 '13 at 10:18

Here 9n divided by 8 will give the same reminder as n divided by 8, as 9 will give a reminder of 1 by 8. Now the number is of the form 6k + 5 where k is a whole no. Since 6k+5 is an odd no., reminders when divided by 8 will be odd as well. Hence reminders possible are 1,3,5,7.

Does this approach work for you?


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.