5
$\begingroup$

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 ?

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

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

$\endgroup$
6
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

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

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

$\endgroup$

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.