Question

If P_n=6^n+8^n,
(P_83÷49) what is the remainder?

Answer 1

Answer on Question #81522 – Math – Combinatorics | Number Theory

Question

If $P_n = 6^n + 8^n$,

$(P_83 \div 49)$ what is the remainder?

Solution

First use Euler theorem (6 and 8 are both mutually prime with 49):

$$6^{\phi(49)} \equiv 1 \pmod{49},$$ $$8^{\phi(49)} \equiv 1 \pmod{49}.$$

Find

$$\phi(49) = \phi(7^2) = 7^2 - 7 = 42.$$

Then

$$6^{42} \equiv 1 \pmod{49}, \quad 8^{42} \equiv 1 \pmod{49}$$

from which

$$6^{84} = (6^{42})^2 \equiv 1 \pmod{49}, \quad 8^{84} = (8^{42})^2 \equiv 1 \pmod{49}.$$

Then $6^{83} \equiv 6^{-1} \pmod{49}, \quad 8^{83} \equiv 8^{-1} \pmod{49}$

Next, from an equality

$$49 = 6 \cdot 8 + 1$$

we have

$$6^{-1} \equiv -8 \pmod{49}, \quad 8^{-1} \equiv -6 \pmod{49},$$

and then

$$6^{83} + 8^{83} \equiv -14 \pmod{49} \equiv 35 \pmod{49}.$$

Answer: 35.

Answer provided by https://www.AssignmentExpert.com