2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Have you heard of Euler's totient function? $\endgroup$ – user472341 Aug 25 '18 at 10:13
  • $\begingroup$ @Jazzachi No, and nor were we taught it. So I think my instructors want us to solve this through other means? $\endgroup$ – The Pointer Aug 25 '18 at 10:14
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I just edited the missing $-1$ in for you. $\endgroup$ – The Pointer Aug 25 '18 at 11:08
  • 1
    $\begingroup$ @ThePointer We know $3^3\equiv -1 \pmod 7$ so $3^6\equiv 1\pmod 7$. So $3^{96}\equiv 1\pmod 7$. We also know $3\equiv 3\pmod 7$. So $3^{100}=3^{96}\times 3^3\times 3\equiv (1)(-1)(3)$, hence $3^{100}\equiv 4\pmod 7$. $\endgroup$ – user472341 Aug 25 '18 at 11:12
  • $\begingroup$ So for the second one, we have $5^{243}=(5^8)^{30}\cdot 5^4= 5^4 \equiv 13$ (mod $17$)? $\endgroup$ – The Pointer Aug 25 '18 at 11:27
  • 1
    $\begingroup$ @ThePointer Minor typo, should be $5^3$ not $5^4$. But your approach is correct, and since $5^3\equiv 6 \pmod {17}$, $5^{243}\equiv 6\pmod {17}$. $\endgroup$ – user472341 Aug 25 '18 at 11:29
  • $\begingroup$ Ok, great, I think I understand it now! Thank you very much for taking the time to explain this to me. I found this very enlightening! $\endgroup$ – The Pointer Aug 25 '18 at 11:31
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ But this isn't a general way to solve these problems? $\endgroup$ – The Pointer Aug 25 '18 at 10:19
  • $\begingroup$ @ThePointer It depends on the question. Luckily, this is an exercise, so they might want you to notice that $7$ and $17$ are both prime. If you have to use Euler's totient function, you might use the identity for $\phi(mn)$ and carry on from there. $\endgroup$ – Toby Mak Aug 25 '18 at 10:22
  • $\begingroup$ I don't understand why we use the second form? We don't even know what $p$ is, so how do we know whether to use the first or second form? $\endgroup$ – The Pointer Aug 25 '18 at 10:31
  • $\begingroup$ @ThePointer We can use the second form because $a$ does not divide $p$ in your questions (if $p = 7$, $a$ is not $14, 21, 28$ etc.). $p$ is prime. $\endgroup$ – Toby Mak Aug 25 '18 at 10:34
  • $\begingroup$ Hmm, I see. But the Wikipedia article also assumes that $n = p$? That doesn't necessarily have to be true for this problem, right? So is it valid for us to use this method? $\endgroup$ – The Pointer Aug 25 '18 at 10:36
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.