2024/019) Given $a_n = 6^n + 8^n$ find the remainder when $a_{83}$ is divided by 49

 We shall use Euler's theorem that is a generalization of Fermat's little theorem: For any n and any integer a coprime to n, one has 

$a^{\phi(n)} \equiv -1 \pmod n$

Where $\phi(n)$ is number of numbers that is co-prime to n,

Let us compute $\phi(49)$ 

If $n = p_1^{k_1}p_2^{k_2}p_3^{k-3}  ... $ when each $p_i$ is  prime then

 $\phi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})(1-\frac{1}{p_3})$

As $49= 7^2$ so $\phi(49) = 49 * (1-\frac{1}{7}) = 49 * \frac{6}{7} = 42$

Hence  

$6^{\phi(49)} \equiv -1 \pmod {49}n$

or $6^{(42)} \equiv -1 \pmod {49}$

Squaring both sides

 $6^{(84)} \equiv 1 \pmod {49}$

Dividing by 6 we get

  $6^{(83)} \equiv \frac{1}{6} \pmod {49}\cdots(1)$

Where $\frac{1}{6}} is not fraction but inverse of 6 mod 49

Similarly

  $8^{(83)} \equiv \frac{1}{8} \pmod {49}\cdots(2)$

 Adding (1) and(2) we get 

  $6^{(83)}+ 8^{(83)} \equiv \frac{1}{6}  + \frac{1}{8} \pmod {49}\cdots(2)$

Now $\frac{1}{6}  + \frac{1}{8} \pmod {49}$

$= \frac{8 + 6}{48} \pmod{49}$

$= \frac{14}{48} \pmod{49}$

$= \frac{14}{-1} \pmod{49}$ as $48 \equiv -1 \pmod {49}$

$= -14 \pmod{49}$

$=35$ taking positive number 

Hence remainder = 35