How to solve a congruence with Euclidean algorithm with exponents

Question

I need help solving this particular congruence with Euclidean algorithm. I, in general, don't know how to solve congruences with exponents so I don't even know how to start.

\begin{align*} x \equiv 6^{29} \;(\bmod\; 7) \end{align*}

I know how to solve the ones without exponents, so it would be great if someone could do a step by step solution for this example and explain it to me a little bit better. I want to use Euclidean algorithm because that's how I learnt to do all other congruences and Chinese remainder theorem. (This is how i do them: https://www.youtube.com/watch?v=4-HSjLXrfPs)

Any help is much appreciated.

Answer 1

Irrespective of $6\equiv -1\bmod 7$; Euler's theorem helps:

For any $a$ not divisible by $7$, on has $$a^n\equiv a^{n\bmod\varphi(7)}=a^{n\bmod 6}\bmod n.$$ Actually $6$ has order $2$ modulo $7$, so one even has $\;a^n\equiv a^{n\bmod 2}\bmod 7$.

Answer 2

$6x\equiv 6^{30}\pmod 7$ evaluate the unmodded value of $6^{30}$ and do as you did before.

Answer 3

Since $6^{29} = (6^2)^{14}\cdot6=(\mathring{7}+1)^{14}\cdot6$ and from $(\mathring{7}+1)^{14}=\mathring{7}+1^{14}$ we have:

\begin{align*} x \equiv 6^{29} \equiv 6(\mathring{7}+1^{14}) \equiv 6 \;(\bmod\; 7) \end{align*}

So you have to look for numbers of the form $7k+6$ with $k\in\mathbb{Z}$.