Science:Math Exam Resources/Courses/MATH312/December 2012/Question 02 (c)/Solution 1

The answer is true.

Recall that 7 passes Miller's test if

$\displaystyle 7^{d}\equiv 1\mod {25}$

or the following holds for some r

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

where $\displaystyle 25-1=24=2^{s}d=2^{3}\cdot 3$ and $\displaystyle 0\leq r\leq 3-1$.

If 7 passes the test, then 25 is a probable prime. If it fails the test, then the number is not prime.

So we check manually:

$\displaystyle {\begin{aligned}7^{3}&\equiv 49\cdot 7\equiv -1\cdot 7\not \equiv 1\mod {25}\\7^{2^{1}\cdot 3}&\equiv 49^{3}\equiv (-1)^{3}\equiv -1\mod {25}\end{aligned}}$

Thus, 7 passes Miller's test. (Note that 25 is not prime but still 7 passes Miller's test).