# What is the remainder when $6\times7^{32} + 7\times9^{45}$ is divided by $4$?

What is the remainder when $6\times7^{32} + 7\times9^{45}$ is divided by $4$ ?

$7 \equiv 3 \pmod 4$

$7^2 \equiv 9 \pmod 4\equiv 1 \pmod 4$

$(7^2)^{16} \equiv 1^{16} \pmod 4$

i.e $7^{32} \equiv 1 \pmod 4$

Similarly $9 \equiv 1 \pmod 4$ implies $9^{45} \equiv 1 \pmod 4$. But the problem arise with the coefficients and addition sign. what to do?

$$6 \cdot 7^{32} + 7 \cdot 9^{45} \equiv 6 \cdot 1 + 7 \cdot 1 \equiv 6+7 \equiv 13 \equiv 1 \mod 4$$

The relation "go modulo 4" is very nice. It respects addition and multiplication.

So $$6 \cdot 7^{32} + 7 \cdot 9^{45}$$ is the same as $$6 \cdot 1 + 7 \cdot 1$$ by what you have already computed!

Reduction modulo an integer is a homomorphism of rings ie $$a+b \pmod n=a \pmod n+b\pmod n$$ and $$a\times b\pmod n=a\pmod n\times b \pmod n$$

These facts are easy to check directly e.g. $(a+pn)(b+qn)=ab+(aq+bp+pqn)n$ and $(a+pn)+(b+qn)=a+b+(p+q)n$.

This means that it doesn't matter whether you do your reductions first and the arithmetic after, or do the arithmetic first and then the reduction, or a combination of the two.

Note also that the reduction $7\equiv -1$ is allowed. So I would be doing this as $$6\times 7^{32}+7\times 9^{45}$$ and do all the reductions you can to get something like $$2 \times (-1)^{32}+(-1)\times 1^{45}=2-1$$

You're on the right track. Note that $9 = 1 \mod 4$, so $9^{45} = 1 \mod 4$. Then just apply normal rules. You have $6\times 1+7\times 1=13=1$

• usually, it's $9\equiv1\pmod{4}$ – robjohn Jun 28 '15 at 7:06
• @robjohn Thanks. I just did a quick edit of the OP, mainly to fix the exponents. – user223391 Jun 28 '15 at 7:07
• I meant rather than 9 = 1 \mod 4 it is more customary to say 9\equiv1\pmod{4} – robjohn Jun 28 '15 at 13:55

$[6\equiv\color\red2\pmod4]\wedge[7^{32}\equiv\color\green1\pmod4]\implies[6\cdot7^{32}\equiv\color\red2\cdot\color\green1\equiv\color\purple2\pmod4]$

$[7\equiv\color\red3\pmod4]\wedge[9^{45}\equiv\color\green1\pmod4]\implies[7\cdot9^{45}\equiv\color\red3\cdot\color\green1\equiv\color\orange3\pmod4]$

$[6\cdot7^{32}\equiv\color\purple2\pmod4]\wedge[7\cdot9^{45}\equiv\color\orange3\pmod4]\implies[6\cdot7^{32}+7\cdot9^{45}\equiv\color\purple2+\color\orange3\equiv1\pmod4]$

$\phi(4) = 2$ and since $(4,7), (4,9)$ are relatively prime we have $[7^2]_4 = [1]_4$, $[9^2]_4 = [1]_4$ and so $[6 \cdot 7^{32}+7 \cdot 9^{45}]_4 = [6]_4+[7 \cdot 9]_4=[69]_4 = [1]_4$.

• Why the downvote? – copper.hat Jul 26 '15 at 6:46

A different approach: One could rewrite the problem as:

$6*7^{32} + 7*9^{45} = 6* (8-1)^{32} + 7* (8+1)^{45}$ and then apply the binomial theorem.

$(8-1)^{32} = \binom{32}{0}*8^{32} *(-1)^0 + \binom{32}{0}*8^{31} *(-1)^1 ... + \binom{32}{0}*8^0 *(-1)^{32}$

$(8+1)^{45} = \binom{45}{0}*8^{45} *(+1)^0 + \binom{45}{0}*8^{44} *(+1)^1 ... + \binom{45}{0}*8^0 *(+1)^{45}$

It is easy to see that all terms apart from the last one are divisible by 4. Therefore one has just to compute the terms: $6* \binom{32}{0} *(-1)^{32} + 7 * \binom{45}{0} *(+1)^{45}$, however: $\binom{n}{0} = 1 \ \forall n$ thus one just gets: $6*1 +7*(+1)$ = 13 that is equal to a remainder of +1 mod(4)

Which gives the desired result.

• You forgot to use curly braces around the exponents in your first line. – N. F. Taussig Jun 28 '15 at 10:16
• thx, it's fixed now. – Imago Jun 28 '15 at 10:25