Using the fermat test to show 513 is not prime I've been asked to use the fermat test for the base a=2 to show that 513 is not a prime number. 
Could someone please help explain what a base exactly is in this context?
Thanks in advance!
 A: The theory
Fermat's theorem says that if $n$ is prime, then $a^{n-1} \equiv 1\bmod n$ for all $0 < a < n$. Testing whether this is true for a given $n$ is called the Fermat primality test. In this context, $a$ is called a base. The Fermat primality test can prove that $n$ is not a prime if you find a base that fails the Fermat test. Unfortunately, the Fermat test cannot prove that $n$ is a prime because there are numbers that satisfy the Fermat test for all bases but are not prime; they are called pseudoprimes.
The example
As @lab bhattacharjee has noticed, $2^9=512\equiv-1\bmod 513 $ and so $2^{18}\equiv 1 \bmod 513$.
Now, $512 = 28 \cdot 18 + 8$ and so $2^{512} \equiv 2^8 = 256 \not\equiv 1 \bmod 513$.
If $513$ were a prime, we'd have $2^{512} \equiv 1 \bmod 513$, by Fermat's theorem.
A: For example
$$3^3\cdot19=513=0\pmod{513}\implies 3^{512}=(3^3)^{170}\cdot3^2\neq1\pmod{513}$$
since, as shown, $\;3^3\;$ is a zero divisor, and thus Fermat's Test fails here.
Using base $\;a=2\;$ : since
$$2^9=512=-1\pmod{513}\;\;\text{and also}\;\;512=9\cdot56+8\;,\;\;\text{we get}$$
$$2^{512}=(2^9)^{56}\cdot2^8=(-1)^{56}\cdot256=256\neq1\pmod{513}$$
A: We prove that $2^{512}\not\equiv1\pmod {513}$
$$2^{512}=2^{2^9}=\left(2^{2^5}\right)^{2^4}\equiv (481)^{2^4}\pmod{513}\equiv(-32)^{16}\pmod {513}$$
$$(-32)^{16}\equiv256\pmod{513}\ne 1\pmod{513}$$
Thus $513$ is not a prime.
