- Thread starter
- #1

- Thread starter suvadip
- Start date

- Thread starter
- #1

- Jan 30, 2012

- 2,572

Another way is to use Euler's theorem: $19^{\varphi(92)}\equiv1\pmod{92}$. Here $\varphi(92)=92\left(1-\frac{1}{2}\right)\left(1-\frac{1}{23}\right)=44$. So, $19^{88}\equiv1\pmod{92}$ and you only need to compute $19^4\pmod{92}$.

- Feb 15, 2012

- 1,967

\(\displaystyle 19^2 \equiv 361 \equiv 85 \equiv -7\ (\text{mod }92)\)

(I have a profound dislike of "big numbers").

It follows that:

\(\displaystyle 19^{92} \equiv 19^4 \equiv (19^2)^2 \equiv 49\ (\text{mod }92)\).

EDIT: I must learn to read someday, this was implicit in the first post. I'll go crawl under a rock now....

- Admin
- #4

- Mar 5, 2012

- 9,773

If you're not learning about the CRT you might as well stop reading now, since my explanation is rather concise. Sorry.

Since I rather like CRT, I'll continue.

More specifically, CRT says that $19^{92} \pmod{92}$ can be (isomorphically) mapped to:

$$(19^{92} \text{ mod }4,\ 19^{92} \text{ mod } 23) \equiv ((-1)^{92} \text{ mod } 4,\ (-4)^{92 \text{ mod } 22} \text{ mod } 23) \equiv (1 \text{ mod } 4, 3 \text{ mod } 23)$$

The solutions from the 2nd argument are one of $3, 26, 49, 72$.

Only $49$ fits the first argument.

Therefore $19^{92} \equiv 49 \pmod{92}$.