(Modular Arithmetic) Congruences With Exponents

I am trying to find the following:

The least positive integer $n$ for which

$3^n \equiv 1$ (mod $7$)

And hence $3^{100}$ (mod $7$).

The least positive integer $n$ for which

$5^n \equiv 1$ (mod $17$) or $5^n \equiv -1$ (mod $17$)

And hence evaluate $5^{243}$ (mod $17$).

Evaluate $2^4$ (mod $18$) and hence evaluate $2^{300}$ (mod $18$).

I've learned how to use the Euclidean algorithm, but I have no idea how to compute congruence when they have exponents, as above. These seem very daunting to me. I would greatly appreciate it if people could please take the time to explain how this is done.

I will then post my work for each of these for, if possible, feedback on the solutions, since I do not have any solutions for these.

Thank you.

Answer

Regarding congruences with exponents - the cool thing about them is you can raise 'each side' to some power, or multiply them by a common factor and it remains true. It's often useful to show that $x^n\equiv \pm 1 \pmod k$. Regarding your first question, we know $3\equiv 3\pmod 7$ so $3^2\equiv 2\pmod 7$ since $9\pmod 7=2$. So $3^3=3^2\times 3\equiv 2\times 3=6\equiv -1 \pmod 7$. So $3^3\equiv -1 \pmod 7$. Hence $(3^3)^2=3^6\equiv (-1)^2=1\pmod 7$. We know $3^{100}=3^{6\cdot 16+4}=3^{96}\cdot 3^3\cdot 3$, and since we know the value of all these modulo $7$, $3^{100}$ is congruent mod $7$ to the product of them.

For your 2nd question, we can apply these same principles - it just takes a bit longer $$\begin{align*}5&\equiv 5\pmod {17} \\ \implies 5^2&\equiv 8 \pmod {17} \\ \implies 5^3&\equiv 6\pmod {17} \qquad \text{since $40\pmod {17}=6$} \\ \implies 5^{4}&\equiv 13\pmod {17}\qquad \text{since $30\pmod{17}=13$} \\ &\vdots \\ \implies 5^8&\equiv -1\pmod{17}\end{align*}$$ Note that we could have directly obtained the final result by squaring both sides of the fourth line. So now $5^{243}=(5^8)^{30}\cdot 5^3=\dots$

However, using Euler's theorem is usually faster - there's examples of solutions to similar problems within that link.