# Thread: Prime testing with base 2 test.

1. ## Prime testing with base 2 test.

I have a question in my book as follow:

Use the base 2 test on 511 and 509

(base 2 test is n does not satisfy $2^n\equiv2mod(n)$ then it is composite)

For the first part I think I am good:

Noting that $2^9=512\equiv1mod(511)$ so

$2^{511}=({2^{9}})^{56}*2^7\equiv2^7mod(511)$

and $2^7$ is not $\equiv2mod(511)$

However for the second part I get a bit confused:

$2^9=512\equiv3mod(509)$ so

$2^{509}=({2^{9}})^{56}*2^5\equiv(3^{56}*2^5)$ But I am a bot confused as to where to go next.

Thanks for any help

(oh and anybody knows the Latex symbol for not equivalent that would be great)

2. Originally Posted by hmmmm
(oh and anybody knows the Latex symbol for not equivalent that would be great)
$\not \equiv$ = \not \equiv

-Dan