Show 1387 is a base 2 pseudoprime and is also composite using Miller's test

Question

My attempt:

1387 is a base 2 pseudoprime if $2^{1386} \equiv 1 \bmod 1387$. We note $1387=19 \cdot 73$ and $1386=18 \cdot 7 \cdot 11$, and by Fermat's Little Theorem(FLT), $2^{18} \equiv 1 \bmod 19$, so $(2^{18})^{77} \equiv 1 \bmod 19$. Applying FLT again, $2^{72} \equiv (2^{18})^4 \equiv 1 \bmod 73$. I would then like to imply $2^{18} \equiv 1 \bmod 73$, is this justified? Then by the Chinese Remainder Theorem, $2^{1386} \equiv 1 \bmod 1387$.

A number is composite if it does not pass Miller's test for some base. Here, we use base 2. $2^{1386/2} = 2^{693} \equiv 512 \bmod 1387$, thus $2^{1386/2}$ is not congruent to $1$ or $-1$ mod 1387, therefore 1387 is composite. Here, I have calculated $2^{693} \equiv 512 \bmod 1387$ using a calculator, as $693 = 3\cdot 3 \cdot 7 \cdot 11$ so I couldn't use the Chinese remainder theorem. Is there a way to calculate it by hand?

Answer 1

You can use $$2^{18}\equiv 1\mod 1387$$

First of all, how to get this result ?

$2^{18}\equiv1\mod 19$ follows from Fermat's little theorem.

Since $73$ divides $2^9-1$ , we also have $2^{18}\equiv 1\mod 73$.

Chinese remainder theorem shows $2^{18}\equiv 1\mod 1387$.

Therefore, you can reduce the exponent $693$ modulo $18$ giving $9$, hence $2^{693}\equiv 2^9=512\mod 1387$

Answer 2

You can render $2^{18}\bmod 73$ efficiently with the repeated squaring method. The exponent $18$ has the binary representation $10010$ so we have:

$2^{18}\equiv ((((2^2)^2)^2×2)^2\bmod 73$

The multiplication by the base $2$ after three squarings corresponds to the second $1$ being three positions after the initial $1$ in $10010_2$. Working from the inner parentheses outward you get $2^{18}\equiv 1$ with little trouble, and you get $2^9\equiv 1$ (before the last squaring) too.