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 $\displaystyle 2^n\equiv2mod(n)$ then it is composite)

For the first part I think I am good:

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

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

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

However for the second part I get a bit confused:

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

$\displaystyle 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)