Find the remainder when $5^{7121}$ is divided by $7$

Question

Hey I'm stuck on this question, as I've been given two methods of solving questions like it, $gcd(a,b)$ $\rightarrow$ $a=b\times n+r$ then $b=r\times k +z$ if that makes sense, but you keep doing that until you get a remainder of $0$ and the remainder in your previous equation is the remainder of the original statement. The second method is $a=p_{1}^{a_1}p_{2}^{a_2}p_{3}^{a_3}...$, $b=p_{1}^{b_1}p_{2}^{b_2}p_{3}^{b_3}...$ where $p_1, p_2, p_3$ are primes then, $gcd(a,b)=p_{1}^{min(a,b)}\times p_{2}^{min(a,b)}$. I don't know if there's another way to solve it or if you have to use this method but I've tried to use both methods and it doesn't seem right because the number is so big. Any help would GREATLY be appreciated, thanks! :)

Answer 1

Working modulo $7$ we may write,

$$5^{7121} \equiv (-2)^{7121}$$

$$\equiv -(2^3)^{2373} 2^2$$

$$ \equiv -2^2$$

$$\equiv -4$$

$$\equiv 3$$

So the remainder is $3$

Answer 2

Notice that $$5^3=125\equiv-1\;\mod 7$$ Then \begin{align*} 5^{7121}=5^{3\times 2373+2}&\equiv(-1)^{2373}\cdot 5^2\mod 7\\ &\equiv-25\mod 7\\ &\equiv3\mod 7 \end{align*}