(Modular Arithmetic) Congruences With Exponents

Question

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 1

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.

Answer 2

Hint:

For the first two questions, Fermat's little theorem works because $7$ and $17$ are both prime. Now you can use the second form: $a^{p-1} \equiv 1 \pmod p$ (if $a \nmid p$ ).

For the last question, $2^4 \pmod {18} \equiv -2$. Then $(2^4)^4 = 2^{16} \equiv -2$, and $2^{256} \equiv -2$, so you can break up $300$ into powers of $4$.

Answer 3

Usually the standard routine is to use Euler's theorem which states that:

Let $a\in\Bbb Z_n$, if $\gcd(a,n)=1$ then $$a^{\phi(n)}\equiv_n 1$$ $\phi(n)$ is called the Euler totient function, and it is the number of integers $k$ such that $1\leq k<n$ and $\gcd(k,n)=1$.

For instance $\phi(10)=4$ because there are only four integers less than $10$, that are relatively prime (no common factor) to $10$. $$\{\color{green}{1},2,\color{green}{3},4,5,6,\color{green}{7},8,\color{green}{9}\}$$ This means that $$a^4\equiv_{10}1$$ if $\gcd(a,10)=1$. So $$1^4\equiv_{10}1\\3^4\equiv_{10}1\\7^4\equiv_{10}1\\9^4\equiv_{10}1$$ When $n=p$ is prime $\phi(p)=p-1$. With $p=5$ we have $$1^4\equiv_{5}1\\2^4\equiv_{5}1\\3^4\equiv_{5}1\\4^4\equiv_{5}1$$ This special case, with $p$ prime, is known as Fermat's little theorem.