Science:Math Exam Resources/Courses/MATH312/December 2009/Question 02 (a)/Solution 1

Recall that 2 passes Miller's test if

$\displaystyle 2^{d}\equiv 1\mod {209}$

or for some value r

$\displaystyle 2^{2^{r}d}\equiv -1\mod {209}$

where $\displaystyle 209-1=208=2^{s}d$ and $\displaystyle 0\leq r\leq s-1$. If 2 fails the test, then 209 is not prime. For us, we see that $\displaystyle 208=2^{3}(26)=2^{4}\cdot 13$ and so d is 13 and r is 4. We compute manually.

$\displaystyle 2^{13}\equiv 2^{8}\cdot 2^{5}\equiv (256)(32)\equiv (47)(32)\equiv 1504\equiv 41\not \equiv \pm 1\mod {209}$

and for the powers of 2,

$\displaystyle 2^{2\cdot 13}\equiv 41^{2}\equiv 1681\equiv 9\not \equiv \pm 1\mod {209}$

$\displaystyle 2^{4\cdot 13}\equiv 9^{2}\equiv 81\not \equiv \pm 1\mod {209}$

$\displaystyle 2^{8\cdot 13}\equiv 81^{2}\equiv (2\cdot 41-1)^{2}\equiv 4\cdot 41^{2}-4\cdot 41+1\equiv 4\cdot 9-164+1\equiv 36+45+1\equiv 82\not \equiv \pm 1\mod {209}$

$\displaystyle 2^{16\cdot 13}\equiv 82^{2}\equiv (81+1)^{2}\equiv 81^{2}+162+1\equiv 82+162+1\equiv 36\not \equiv \pm 1\mod {209}$

and so the number 209 is not prime and 2 fails Miller's test. Thus 209 is composite. In fact $\displaystyle 209=11\cdot 19$.