1. ## Division Algorithm

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.

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

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

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

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

3)

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

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

3. Hello, nacknack!

Are you allowed Modulo Arithmetic?

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

Without evaluating:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

When $\displaystyle 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*
.