Using the fermat test to show 513 is not prime

Question

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!

Answer 1

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}$$

Answer 2

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.

Answer 3

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.