1

I used Fermat's Little Theorem to find:

$$9^{45} \mod 23$$ What I have done so far: $$9^{45} = (9^2)^{22}9$$

$$9^{22} \equiv 1 \pmod{23}$$ According to Fermat's Little Theorem.

So, now I have: $$9^{45} \equiv (9^2)^{22}9 \equiv 1^2 9 \pmod{23}$$

So: $$9^{45} \mod 23 = 9$$

I am a bit uncertain about my notation etc. For example, in the last line, should it be a $\equiv$ or a $=$? Can someone please verify my method?

Julia
  • 496
  • 2
    Why not simply write $9^{45} \equiv 9 \pmod{23}$? The notation you've used (where mod is used as a sort of "operator") is not generally the convention in this context. – Ben Grossmann Jul 20 '15 at 19:05
  • @Omnomnomnom ~ Yes, that is basically what I wrote in my second to last step, but is the last step correct? – Julia Jul 20 '15 at 19:07
  • @Omnomnomnom ~ Ok, so the convention is to leave it as you wrote it and then just say that 9 is an answer for example (I want to find a specific answer) – Julia Jul 20 '15 at 19:09
  • 2
    To expand on the top comment, we write $9^{45}\equiv 9$, which is read "$9^{45}$ is congruent to $9$". Then, to specify what "congruent" means in this specific case, we put $\pmod{23}$ at the end. – Arthur Jul 20 '15 at 19:10
  • @Arthur That makes it clearer, thanks – Julia Jul 20 '15 at 19:11
  • 1
    @Julia in the context of computer science, something like what you've written is more common. For example, in Python, you can input 9 ** 45 % 23 and the computer would spit out 9. – Ben Grossmann Jul 20 '15 at 19:13
  • @Omnomnomnom ~ Ok, the material that I am revising forms part of a CS course and the examples in class has specific answers (like 9). – Julia Jul 20 '15 at 19:15
  • 1
    All right. It would seem then that whichever way you write the answer is correct; I wouldn't fuss over the notation here. The mathematical way to ask the question might something like "find a representative of $9^{45}$ modulo $23$ from the set ${0,\dots,22}$". – Ben Grossmann Jul 20 '15 at 19:18
  • 1
    A minor quibble: After you showed that $9^{22} \equiv 1 \pmod{23}$ using Fermat's Little Theorem, you obtained $9^{45} \equiv (9^2)^{22} \cdot 9 \equiv 1^2 \cdot 9 \pmod{23}$. It would be more illuminating to write $9^{45} \equiv (9^{22})^2 \cdot 9 \equiv 1^2 \cdot 9 \pmod{23}$. – N. F. Taussig Jul 20 '15 at 19:25
  • @N.F.Taussig ~ I get what you are saying. How about writing: $9^{45} \equiv (9^2)^{22} \equiv 1^{22} \cdot 9 \pmod{23}$? – Julia Jul 20 '15 at 19:28
  • 1
    @Julia Note that $9^2 \equiv 81 \equiv 12 \pmod{23}$. Thus, $9^{45} \equiv (9^2)^{22} \cdot 9 \equiv 12^{22} \cdot 9 \equiv 1 \cdot 9 \pmod{23}$, where the last equivalence follows from Fermat's Little Theorem. What you originally wrote is correct since $9^{45} \equiv (9^2)^{22} \equiv (9^{22})^2 \cdot 9 \equiv 1^2 \cdot 9 \equiv 9 \pmod{23}$. To me, it makes more sense to write $9^{45} \equiv (9^{22})^2 \cdot 9 \equiv 1^2 \cdot 9 \equiv 9 \pmod{23}$ since you have already established that $9^{22} \equiv 1 \pmod{23}$. – N. F. Taussig Jul 20 '15 at 20:00

1 Answers1

1

Your solution is correct, but in the last line one should have a $\equiv$, because the numbers are not equal. Furthermore the equivalence sign should be before the mod 23, i.e. $9^{45} \equiv 9 \mod 23$.

In general:

  • If the numbers are really equal, both $=$ and $\equiv$ are correct.
  • If the numbers are not equal, you should use $\equiv$.
wythagoras
  • 25,026