4

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!

Edward
  • 41

3 Answers3

3

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.

lhf
  • 216,483
0

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

DonAntonio
  • 211,718
  • 17
  • 136
  • 287
  • The OP needs to use base $2$, not $3$. – lhf Mar 28 '16 at 12:27
  • @lhf Thank you. I didn't even notice that condition. IT seems rather weird since as in this case it works but it could fail in others. Not only that, the used exponent for two is rather pretty high... – DonAntonio Mar 28 '16 at 12:38
0

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.

Piquito
  • 29,594