2

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?

Dimitri
  • 1,287

3 Answers3

5

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

Obinna Okechukwu
  • 1,869
  • Why is it that we only need to find values for k = 0,1,2,3 ? – Dimitri Nov 06 '13 at 15:13
  • 1
    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. – Casteels Nov 08 '13 at 10:18
2

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.

Zach L.
  • 6,633
0

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?

ssharma
  • 61