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

Recall that 2 passes Miller's test if

$2^d\equiv 1mod209$

or for some value r

$2^{2^{r}d}\equiv -1mod209$

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

$2^{13}\equiv 2^8\cdot 2^5\equiv (256)(32)\equiv (47)(32)\equiv 1504\equiv 41\equiv ̸\pm 1mod209$

and for the powers of 2,

$2^{2\cdot 13}\equiv 41^2\equiv 1681\equiv 9\equiv ̸\pm 1mod209$

$2^{4\cdot 13}\equiv 9^2\equiv 81\equiv ̸\pm 1mod209$

$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\equiv ̸\pm 1mod209$

$2^{16\cdot 13}\equiv 82^2\equiv (81+1{)}^2\equiv 81^2+162+1\equiv 82+162+1\equiv 36\equiv ̸\pm 1mod209$

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