Division Algorithm

**nacknack** · April 28th 2010, 03:21 AM

Let a = 43^8765 - 34^5678,
and let c = 43^8765 + 34^5678.

Without evaluating:

1. Show that a is divisible by 3
2.Find the remainder when c is divided by 7
3. Hence find the remainder when c^a is divided by 7.

**Black** · April 28th 2010, 04:29 AM

1) $43 \equiv 1(\text{mod}\, 3)$ and $34 \equiv 1(\text{mod}\, 3)$ , so

$43^{8765}-34^{5678} \equiv 1-1=0(\text{mod}\, 3)$ .

2) $43 \equiv 1(\text{mod}\, 7)$ and $34 \equiv -1(\text{mod}\, 7)$ , so

$43^{8765}+34^{5678} \equiv 1+(-1)^{5678}=2(\text{mod}\, 7)$ .

3)

$c \equiv 2(\text{mod}\, 7)$
$c^2 \equiv 4(\text{mod}\, 7)$
$c^3 \equiv 1(\text{mod}\, 7)$
$c^4 \equiv 2(\text{mod}\, 7)$

$\vdots$

, so the sequence is 2,4,1,2,4,1,2,4,1,... . Since a is divisible by 3, the remainder must be 1.

**Soroban** · April 28th 2010, 07:02 AM

Hello, nacknack!

Are you allowed Modulo Arithmetic?

Let $\begin{array}{ccc}a &=& 43^{8765} - 34^{5678} \\c &=& 43^{8765} + 34^{5678} \end{array}$

Without evaluating:

1. Show that $a$ is divisible by 3.

We have: . $\begin{Bmatrix}43 & \equiv & 1 & \text{(mod 3)} \\ 34 &\equiv & 1 & \text{(mod 3)} \end{Bmatrix}$

Hence: . $a \;=\;43^{8765} - 34^{5678}$

. - . . . . . $\equiv\;\;1^{8765} - 1^{5678}\text{ (mod 3)} \;\;\equiv\;\; 1-1\text{ (mod 3)} \;\;\equiv\;\; 0 \text{ (mod 3)}$

Therefore: . $a \;\equiv\;0\text{ (mod 3)}$ . . . . $a$ is divisible by 3.

2. Find the remainder when $c$ is divided by 7.

We have: . $\begin{Bmatrix}43 &\equiv & 1 & \text{mod 7)} \\ 34 &\equiv & \text{-}1 & \text{(mod 7)} \end{Bmatrix}$

Hence: . $c \;=\;43^{8765} + 34^{5678}$

. . . . . . . $\equiv\;\;1^{8765} + (\text{-}1)^{5678} \text{ (mod 7)} \;\;\equiv\;\;1 + 1 \text{ (mod 7)} \;\;\equiv\;\;2 \text{ (mod 7)}$

When $c$ is divided by 7, the remainder is 2.

3. Hence find the remainder when $c^a$ is divided by 7.

We already have: . $\begin{Bmatrix}43 & \equiv & 1 & \text{(mod 7)} \\ 34 &\equiv & \text{-}1& \text{(mod 7)} \end{Bmatrix}$

Hence: . $a \;=\;43^{8765} - 34^{5678}$

. . . . . . . . $\equiv\;\;(1)^{8765} - (\text{-}1)^{5678} \text{ (mod 7)} \;\;\equiv\;\;1 - 1\text{ (mod 7)} \;\;\equiv\;\; 0\text{ (mod 7)}$

We have: . $c^a \;=\;\left(43^{8765} + 34^{5678}\right)^{43^{8765} - 34^{5678}}$

. . . . . . . . . . $\equiv\;\;2^0\text{ (mod 7)} \;\;\equiv\;\;1\text{ (mod 7)}$

When $c^a$ is divided by 7, the remainder is 1.

But check my work . . . please!

edit: Black was too fast for me (and briefer, too!) . . . *sigh*
.

Thread: Division Algorithm

LinkBack

Thread Tools

Display

Division Algorithm

Similar Math Help Forum Discussions

Division Algorithm.....

Division algorithm/mod

Division Algorithm

Division Algorithm...

division algorithm

Search Tags