Least positive integer $\equiv 3^{18} \pmod{37}?$

Question

To determine this for $13^{33} \pmod{64}$ is easy since $\phi(64)=32$ and $\gcd(64,33)=1$, we have $13^{\phi(64)}=13^{32}\equiv1 \pmod{64}$. This means that

$$13^{33}=13^{31}\cdot13\equiv 13 \equiv1 \pmod{64}$$

But this method don't apply to $3^{18} \pmod{37}$ since $\phi(37)=36>18.$ How can I do this?

Answer 1

Hint. From Fermat's little theorem, given $37$ is prime and $\gcd(3,37)=1$ $$3^{36} \equiv 1 \pmod{37}$$ or $$37 \mid \left(3^{18}+1\right)\cdot \left(3^{18}-1\right)$$ According to Euclid's lemma one of these should happen $37 \mid \left(3^{18}+1\right)$ or $37 \mid \left(3^{18}-1\right)$

---

But, there is an "easier" way $$27\equiv 3^3 \equiv -10 \pmod{37} \Rightarrow \\ 3^{18} \equiv 10^6 \equiv 100^3 \pmod{37} \Rightarrow \\ 3^{18} \equiv {-11}^3 \equiv 121\cdot(-11)\pmod{37} \Rightarrow \\ 3^{18} \equiv 10\cdot(-11) \equiv - 110\pmod{37} \Rightarrow \\ 3^{18} \equiv 1\pmod{37}$$ because $37 \mid 111$ or $100 \equiv -11 \pmod{37}$.

Answer 2

$\bmod 37\!:\,\ 1\equiv 5(15)\,\overset{\large \times 3}\Longrightarrow\, 3\equiv 15^{\large 2}\,\overset{(\ \ )^{\Large 18}}\Longrightarrow\, 3^{\large 18}\!\equiv 15^{\large 36}\!\equiv 1\ $ by little Fermat

Answer 3

mod $37,$ $ \color{blue}{3^4=81\equiv 7},$ so $ 3^8\equiv (\color {blue }{3^4})^2 \equiv \color{blue}7^2=49 \equiv 12, $ so $\color{red}{3^9\equiv 3\times}$$\color{black}{3^8}\color{red}{\equiv 3 \times} \color{black}{12} \color{red}{\equiv 36 \equiv -1},$

so $ \color{green}{3^{18}\equiv (3^9)^2\equiv 1 }$

Answer 4

Applying the quadratic reciprocity theorem, there is no need to calculate much:

$3$ is a square $\mod 37$, iff $37$ is a square $\mod 3$. (Note: $37 = 4n+1$).

Since $37 \equiv 1 \mod 3$, is a square, then: $3$ is a square $\mod 37$.

All squares power to $18$ are $1 \mod 37$. (Note: $18 = (37-1) / 2$).

And all not squares power to $18$ are $-1\equiv36 \mod 37$

Because $3$ is a square, then $3^{18} \equiv 1 \mod 37$

With this same argument it is proved that: $5 ^ {18} \equiv -1 \mod 37$. Since $5$ is not a square $\mod 37$. Since $37 \equiv 2 \mod 5$ is not a square $\mod 5$.