Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 ?

share|cite|improve this question
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$.

share|cite|improve this answer

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

share|cite|improve this answer

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

share|cite|improve this answer
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}$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.