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.
Best 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.