find the smallest natural number $r$ that $6^{83}+8^{83}=49q+r$? find the smallest natural number $r$ that $6^{83}+8^{83}=49q+r$?
I tried to find a pattern but I was not successful because it takes a lot of calculation to find out how long is the cycle.It is clear that it is multiply of $7$,The book wrote the answer $35$ but how?
 A: We can use Euler's Totient Theorem. The totient of $49$ is $\phi(49)=49\times(1-\frac{1}{7})=42$. 
Now, one can write $6^{83}+8^{83}$ as $6^{83}+8^{83}\equiv 6^{-1}+8^{-1}\pmod{49}$. 
Then replace the ones with $246$ and $344$ (which are $1 \mod 49$ and are clearly divisible by $6$ and $8$ respectively). Then clearly $41+43\equiv35\pmod{49}$. The answer is therefore $35$.
A: Since $6 = 7-1$ and $8 = 7 + 1$ then:
$$\begin{align*}6^{83} &= (7-1)^{83} \\ &= \sum_{k=0}^{83}{83\choose k}(-1)^{83-k}7^k \\ &= 49q_1 + {83\choose 1}(-1)^{82}7 + {83\choose 0}(-1)^{83}7^0 \\ &= 49q_1 + 580 \\ &= 49q_1' + 41.\\ \\ \\
8^{83} &= (7+1)^{83} \\ &= \sum_{k=0}^{83}{83\choose k}1^{83-k}7^k \\ &= 49q_2 + {83\choose 1}1^{82}7 + {83\choose 0}1^{83}7^0 \\ &= 49q_2 + 582 \\ &= 49q_2' + 43.\end{align*}$$
So
$$6^{83} + 8^{83} = 49(q_1' + q_2') + 84 = 49q + 35.$$

Generally one would use Euler's totient function and similar techniques, but sometimes a more elementary solution can be found.
A: I would be a little shorter, and wouldn't denote the inverse of $6$ and of $8$ modulo $49$ as $\frac18$ and $\frac18$, as fractions of congruence classes have no natural meaning.
Euler's theorem tells us that
$$6^{83}\equiv6^{83\bmod\varphi(49)}=6^{83\bmod42}=6^{-1}\enspace\text{and similarly}\enspace8^{83}\equiv8^{-1}\pmod{49}.$$
Now  $6\cdot8\equiv -1\mod49$, so
$$6^{83}+8^{83}\equiv6^{-1}+ 8^{-1}\equiv -8-6=-14\equiv 35\pmod{49}.$$
