Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
2  
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
add comment

4 Answers

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|improve this answer
add comment

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

share|improve this answer
add comment

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|improve this answer
1  
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
add comment

$\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|improve this answer
add comment

Your Answer

 
discard

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.