2

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.

Community
  • 1
The Pointer
  • 4,182

3 Answers3

3

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.

The Pointer
  • 4,182
  • I just edited the missing $-1$ in for you. – The Pointer Aug 25 '18 at 11:08
  • 1
    @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$. –  Aug 25 '18 at 11:12
  • So for the second one, we have $5^{243}=(5^8)^{30}\cdot 5^4= 5^4 \equiv 13$ (mod $17$)? – The Pointer Aug 25 '18 at 11:27
  • 1
    @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}$. –  Aug 25 '18 at 11:29
  • 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! – The Pointer Aug 25 '18 at 11:31
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$.

Toby Mak
  • 16,827
  • But this isn't a general way to solve these problems? – The Pointer Aug 25 '18 at 10:19
  • @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. – Toby Mak Aug 25 '18 at 10:22
  • 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? – The Pointer Aug 25 '18 at 10:31
  • @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. – Toby Mak Aug 25 '18 at 10:34
  • 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? – The Pointer Aug 25 '18 at 10:36
  • @ThePointer $\phi(n)$ is Euler's totient function for any positive integer $n$. This is a generalisation of Fermat's little theorem, so that the exponent doesn't only have to be prime. – Toby Mak Aug 25 '18 at 10:39
  • Let us continue this discussion in chat. – Toby Mak Aug 25 '18 at 10:40
0

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.

cansomeonehelpmeout
  • 12,782
  • 3
  • 22
  • 49