2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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$$

$\endgroup$
1
$\begingroup$

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$

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

$[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]$

$\endgroup$
1
$\begingroup$

$\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$.

$\endgroup$
  • $\begingroup$ Why the downvote? $\endgroup$ – copper.hat Jul 26 '15 at 6:46
1
$\begingroup$

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.

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

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.