If you say $$n=161038=2\cdot 73\cdot 1103$$ I know $n$ is a pseudoprime if $$2^n \equiv2 \mod n$$ I don't really know where to go from here. Can someone please help me in the right direction. Thanks.
$\endgroup$2 Answers
$\begingroup$Denote $$n=161038=2\cdot 73\cdot 1103$$
The order of $\ 2\ $ modulo $\ 73\ $ (the smallest positive integer $\ k\ $ with $\ 2^k\equiv 1\mod 73\ $) is $\ 9\ $, modulo $\ 1103\ $ it is $\ 29\ $. In the first case, this can easily be verified by inspection, in the second case note that the orde must divide $\ 1103-1=1102\ $ Once you know $\ 2^{29}\equiv 1\mod 1103\ $ , you know that the order must be either $\ 1\ $ or $\ 29\ $ , where $\ 1\ $ is clearly impossible. Both orders divide $\ n-1\ $, hence we have $$2^{n-1}\equiv 1\mod p$$ for the primes $\ p=73\ $ and $\ p=1103\ $ and therefore $\ 73\ $ and $\ 1103\ $ divide $\ 2^{n-1}-1\ $ (and hence $\ 2^n-2\ $) and therefore their product. $\ 2\ $ obviously divides $\ 2^n-2\ $ finishing the proof.
$\endgroup$ $\begingroup$We will take it for granted that $1103$ is prime. (It's not too hard, with a calculator, to verify that it is.) In order to show that $2^n\equiv2$ mod $n$ with $n=2\cdot73\cdot1103$, it suffices to show
$$\begin{align} 2^n&\equiv2\mod 2\\ 2^n&\equiv2\mod 73\\ 2^n&\equiv2\mod1103 \end{align}$$
The first of these, of course, is obvious (since $n\gt0$). All the work goes into showing the congruences mod $73$ and $1103$.
Note that
$$2\cdot73\cdot1103\equiv2\cdot73\cdot1=146\mod 1102$$
Similarly,
$$2\cdot73\cdot1103\equiv2\cdot1\cdot1103=2206\equiv46\mod 72$$
(the final step requiring some calculation, namely $2206-72\cdot30=2206-2160=46$). By Fermat's little theorem, therefore, it suffices to show that $2^{146}\equiv2$ mod $1103$ and $2^{46}\equiv2$ mod $73$. That is, it suffices to show that $2^{145}\equiv1$ mod $1103$ and $2^{45}\equiv1$ mod $73$.
Let's do $2^{45}\equiv1$ mod $73$ first. Since $45=5\cdot9$ and $72=8\cdot9$, we have $2^{45}\equiv1$ mod $73$ if and only if $2^9\equiv1$ mod $73$. But this is easy to check: $2^9=512=1+7\cdot73\equiv1$ mod $73$. (Alternatively, if you like, we have $2^9=2^6\cdot2^3=64\cdot8\equiv-9\cdot8=-72\equiv1$ mod $73$.)
For $2^{145}=1$ mod $1103$, we first note that $145=5\cdot29$ and $1102=29\cdot38$ (the latter being easy to verify with a calculator). As with $2^{45}$ mod $73$, we have $2^{145}\equiv1$ mod $1103$ if and only if $2^{29}\equiv1$ mod $1103$. This is a little trickier to check, but here's one approach:
$$2^{10}=1024=1103-79\equiv-79\mod 1103$$and thus (given a calculator to check the arithmetic)$$2^{30}\equiv(-79)^3=-493039=2-1103\cdot447\equiv2\mod1103 $$
from which it follows that $2^{29}\equiv1$ mod $1103$, and we're done.
The key thing to note is that Fermat's little theorem ultimately told us what had to be shown, namely $2^9\equiv1$ mod $73$ and $2^{29}\equiv1$ mod $1103$. After that, it's a matter a finding efficient ways to calculate appropriate powers of $2$ mod those two primes.
$\endgroup$
