Finding remainders of large number

This question was asked in a competitive exam.

Find the remainder of dividing $6^{83}+ 8^{83}$ by $49$

Are there any theorems/rules to compute the answer ?

-
Maybe these examples can help you... –  draks ... Jul 20 '12 at 8:21
Did you mean the remainder of (6^83+8^83)/49? Also, what exam was this taken from and is it still ongoing? –  Mike Jul 20 '12 at 8:25
@Mike : Yes.edited the question. –  user2434 Jul 20 '12 at 8:30

Since $6$ and $8$ are both coprime to $49$, we can apply Euler's theorem. We have $\varphi(49)=7^2-7=42$, so we have $$(6\times 8)(6^{83}+8^{83}) \equiv 6+8\equiv 14\mod 49$$ and observing that $6\times 8\equiv -1\bmod 49$ we get that $$6^{83}+8^{83} \equiv (-1)^{-1}(6\times 8)(6^{83}+8^{83})\equiv -14\equiv 35\mod 49$$ thus the remainder is $35$.

-

Use the formula for $(a+b)^n$ for $(7-1)^{83}+(7+1)^{83}$

-

Using Euler's Totient theorem,

As $(6,49)=1$ and $\phi(49)=42$

$6^{42}\equiv 1\pmod {49}\implies 6^{42.k}\equiv1\pmod {49}$ where is any integer. $\implies 6^{84}\equiv 1\pmod{49}\implies 6^{83}\equiv 6^{-1}\pmod{49}$

By observation, $6\times 8=48\equiv -1\pmod{49}\implies 6\times (49-8)\equiv 1\pmod{49}\implies 41\equiv 6^{-1}\pmod{49}$

Similarly, $8^{84}\equiv 1\pmod{49}\implies 8^{83}\equiv 8^{-1}\pmod{49}$ as $(8,49)=1$

As, $6\times 8=48\equiv -1\pmod{49}$, so $(49-6)\times 8\equiv 1\pmod {49}\implies 43\equiv 8^{-1}\pmod{49}$

So, the remainder be $43+41=84\equiv 35\pmod{49}$.

-
How does $48\equiv -1\pmod{49}\implies 6\times (49-8)\equiv 1\pmod{49}$? –  Quixotic Jul 20 '12 at 16:56
If ab≡-1(mod m), then a(m-b)=am-ab≡-ab(mod m)≡-(-1)=1 –  lab bhattacharjee Jul 21 '12 at 4:31

$\begin{eqnarray}\rm{\bf Hint}\ \ \ mod\ \phi(49)\!\!&:&\rm\,\ \color{#C00}{83}\equiv -1\ \ \ by\ \ \ \phi(49) = \phi(7^2) = 7\cdot 6 = 42_{\phantom{\frac{c}{c}}}\\ \Rightarrow\ \rm mod\ 49\!\!&:&\,\ 6^{\color{#C00}{83}}\!+\,8^{\color{#C00}{83}}\equiv\, \dfrac{1}6+\dfrac{1}8\,\equiv\,\dfrac{8+6}{8\cdot 6}\,\equiv\, \dfrac{14}{-1\ }\,\equiv\, 35\end{eqnarray}$

$\begin{eqnarray}\rm and\ \ \ \ mod\ \phi(p^2)\!\!&:&\rm\,\ \color{#C00}{\bf K}\equiv -1\\ \Rightarrow\ \rm mod\ p^2\!\!&:&\rm\,\ (p\!-\!1)^{\color{#C00}{\bf K}}\!+\!\,(p\!+\!1)^{\color{#C00}{\bf K}}\!\equiv \dfrac{1}{p\!-\!1}\!+\!\dfrac{1}{p\!+\!1}\equiv\dfrac{2p}{p^2\!-\!1}\equiv \dfrac{2p}{-1\ }\equiv p(p\!-\!2)\equiv \phi(p)\!-\!p\end{eqnarray}$

-