0

What is the remainder when 6^17 + 117^6 is divided by 7?

How to approach these type of questions?

Prakash Wadhwani
  • 161
  • We have $6=7-1$ and $117=7\cdot 17-2$. Expanding, we find that the remainder is the same as the remainder of $(-1)^{17}+(-2)^{6}$, easy to compute. And small! – André Nicolas Mar 07 '14 at 17:28
  • How did you reach (−1)^17+(−2)^6? – Prakash Wadhwani Mar 07 '14 at 17:30
  • Well, when I did it I actually used congruences, but tried to phrase things without using the term, because it may not be familiar to you. Imagine for example using the Binomial Theorem to expand $(7-1)^{17}$. There will be a bunch of terms divisible by $7$ and higher powers of $7$, with a $(-1)^{17}$ at the end. – André Nicolas Mar 07 '14 at 17:45

3 Answers3

0

$6^{17} = (7-1)^{17} = (-1)^{17} + \text{multiples of }7$ $117^6 = (7\times 17 - 2)^6 = (-2)^6 + \text{multiples of }7 $ sum up the two quantities, you get$$ 6^{17}+ 117^6 = 63 + \text{a multiple of }7 = \text{a multiple of }7 $$ so the reminder is 0.

mookid
  • 28,236
0

Use arithmetic $\pmod 7$. Specifically we'll use these facts:

$x^n \pmod y \equiv (x \pmod y)^n \pmod y$

and

$(y - 1) \pmod y \equiv (-1) \pmod y$

Using those facts...

$6^{17} + 117^6 \pmod 7 \equiv$

$(-1)^{17} + (5)^6 \pmod 7$

$5^2 \equiv 4 \pmod 7$ and $5^4 \equiv 4^2 \equiv 2 \pmod 7$, so

$-1 + (4 \times 2) \equiv 0 \pmod 7$

rgettman
  • 764
0

It helps a lot to know about modular arithmetic. Then you see that

$$6\equiv-1\mod 7\qquad\text{and}\qquad117\equiv-2\mod7$$

and thus

$$6^{17}+117^6\equiv(-1)^{17}+(-2)^6=-1+64=63\equiv0\mod7$$

It helps even more to know about Fermat's little theorem, because then you would know that $117^6\equiv1\mod7$ directly (as soon as you check that $7$ doesn't divide $117$).

Barry Cipra
  • 79,832