Combination Application

Since we are searching for the remainder upon dividing by 49, we will rewrite our expression as following:

$a_{83} = 6^{83} + 8^{83} = (7-1)^{83} + (7+1)^{83}$

After simplifying most of the terms will be equivalent to 0 by module 49 and we get:

$(7-1)^{83} + (7+1)^{83} \equiv {83 \choose 82}*7 -1 + {83 \choose 82}*7 + 1 \equiv 2*7*83 \equiv 35 \pmod{49}$

Since gcd( $6,49$ ) = gcd( $8,49$ ) = $1$ , Euler's theorem yields

$6^{\phi(49)}\equiv 1$ (mod $49$ ) and $8^{\phi(49)}\equiv 1$ (mod $49$ ),

where $\phi(49) = 49\left(1-\frac{1}{7}\right) = 42$ . Therefore,

$(6^{42})^2 = 6^{84}\equiv 1$ (mod $49$ ) $\Rightarrow 8\cdot 6^{84} = 48\cdot 6^{83} \equiv 8$ (mod $49$ ) $\Rightarrow 6^{83} \equiv -8$ (mod $49$ ),

and

$(8^{42})^2 = 8^{84}\equiv 1$ (mod $49$ ) $\Rightarrow 6\cdot 8^{84} = 48\cdot 8^{83} \equiv 6$ (mod $49$ ) $\Rightarrow 8^{83} \equiv -6$ (mod $49$ ).

Combining the last two results we finally obtain

$a_{83} = 6^{83}+8^{83}\equiv-8-6$ (mod $49$ ) $\,\equiv\boxed{35}$ (mod $49$ ).

$\begin{aligned} a_{83} &= 6^{83} + 8^{83} \\ &= (7-1)^{83} + (7+1)^{83} \end{aligned}$

Can be expanded using binomial theorem

\[ \begin{array}{cccccccr} &&\bigg( \binom{83}{0}7^{83}\cdot(-1)^{0} & + \cancel{ \binom{83}{1}7^{82}\cdot(-1)^{1}} &+ \binom{83}{2}7^{81}\cdot(-1)^{2} &+ \cancel{\binom{83}{3}7^{80}\cdot(-1)^{3}} &+ \ldots &+ \binom{83}{82}7^{1}\cdot(-1)^{82} &+ \cancel{\binom{83}{83}7^{0}\cdot(-1)^{83}} \bigg)

\\ &+&\bigg( \binom{83}{0}7^{83}\cdot(1)^{0} &+ \cancel{\binom{83}{1}7^{82}\cdot(1)^{1}} &+ \binom{83}{2}7^{81}\cdot(1)^{2} & + \cancel{\binom{83}{3}7^{80}\cdot(1)^{3}} &+ \ldots &+ \binom{83}{82}7^{1}\cdot(-1)^{82} &+ \cancel{\binom{83}{83}7^{0}\cdot(1)^{83}} \bigg)
\\ \hline \\ &&\bigg( 2 \cdot \binom{83}{0}7^{83}\cdot(-1)^{0} & &+ 2\cdot \binom{83}{2}7^{81}\cdot(-1)^{2} & &+ \ldots &+ 2 \cdot \binom{83}{82}7^{1}\cdot(-1)^{82} &\bigg) \end{array}\]

All the odd powers cancel and twice of even remain. Form that $\color{#D61F06}{7^2}$ can be factored out with remainder in $\color{#3D99F6}{\text{Blue}}$

$\implies \color{#D61F06}{7^2} \color{#333333}{\cdot\bigg( 2 \cdot \binom{83}{0}7^{83-2}\cdot(-1)^{0} + 2\cdot \binom{83}{2}7^{81-2}\cdot(-1)^{2} + \ldots + 2 \cdot \binom{83}{80}7^{3-2}\cdot(-1)^{82} \bigg) + \color{#3D99F6}{2 \cdot \binom{83}{82}7^{1}\cdot(-1)^{82}}}$

$\color{#3D99F6}{2 \cdot \binom{83}{82}7^{1}\cdot(-1)^{82 }} \color{#333333}{ = 2 \times 83 \times 7 \times 1 = 1162 \equiv \boxed{\color{#D61F06}{35}}\pmod{49}}$

The goal is to compute the residue of:

$6^{83}+8^{83} \pmod{49}.$

First, compute $\phi(49)=7^2-7^1=42.$ Then, apply Euler's Theorem :

$6^{83}+8^{83} \equiv 6^{41}+8^{41} \pmod {49}.$

The residues can be found using the method of repeated squares. Find the binary representation of 41:

$41_{10}=101001_{2}.$

Then compute the residues of the repeated squares:

$\begin{array}{c|c|c} k & 6^{2^k} \pmod{49} & 8^{2^k} \pmod{49} \\ \hline 0 & 6 & 8 \\ 1 & 36 & 15 \\ 2 & 22 & 29 \\ 3 & 43 & 8 \\ 4 & 36 & 15\\ 5 & 22 & 29 \end{array}$

Then, simplify the congruence:

$\begin{aligned} 6^{41}+8^{41} &\equiv \left(6^{2^5}\right)\left(6^{2^3}\right)\left(6^{2^0}\right) + \left(8^{2^5}\right)\left(8^{2^3}\right)\left(8^{2^0}\right) \pmod{49} \\ &\equiv (22)(43)(6)+(29)(8)(8) \pmod{49} \\ &\equiv 41+43 \pmod{49} \\ &\equiv \boxed{35}. \end{aligned}$