Dfyjkt

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.

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^nequiv pm 1 pmod k $. Regarding your first question, we know $3equiv 3pmod 7 $ so $3^2equiv 2pmod 7$ since $9pmod 7=2$. So $3^3=3^2times 3equiv 2times 3=6equiv -1 pmod 7$. So $3^3equiv -1 pmod 7$. Hence $(3^3)^2=3^6equiv (-1)^2=1pmod 7$. We know $3^100=3^6cdot 16+4=3^96cdot 3^3cdot 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 $$beginalign*5&equiv 5pmod 17 \ implies 5^2&equiv 8 pmod 17 \ implies 5^3&equiv 6pmod 17 qquad textsince $40pmod 17=6$ \ implies 5^4&equiv 13pmod 17qquad textsince $30pmod17=13$ \ &vdots \ implies 5^8&equiv -1pmod17endalign*$$Note that we could have directly obtained the final result by squaring both sides of the fourth line. So now $5^243=(5^8)^30cdot 5^3=dots$

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

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

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

Let $ainBbb 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 $1leq 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$. $$colorgreen1,2,colorgreen3,4,5,6,colorgreen7,8,colorgreen9$$ This means that $$a^4equiv_101$$ if $gcd(a,10)=1$. So $$1^4equiv_101\3^4equiv_101\7^4equiv_101\9^4equiv_101$$
When $n=p$ is prime $phi(p)=p-1$. With $p=5$ we have $$1^4equiv_51\2^4equiv_51\3^4equiv_51\4^4equiv_51$$ This special case, with $p$ prime, is known as Fermat's little theorem.