Primality Testing - The Idea
To decide if a number $m$ is prime, check if $m \mid 2^{m-1}-1$
- if yes, answer “$m$ is prime”
- if no, answer “$m$ is not prime”
This test doesn’t always work
Example: $m=341=31\cdot11$ The test gets this wrong
Claim: $341\mid(2^{340} -1)$
Show that
- $31\mid (2^{240}-1)$
let $x=2^5$ then $31=x-1$ and $2^{340} - 1 = x^{68} -1 = (x-1)(1+x+x^2+\dots+x^{67}) = 31 \cdot (something)$
- $11\mid (2^{340}-1)$
By Fermat’s Little theorem: $ 11 \mid (2^{10}-1)$
and write $2^{340} - 1$ as a multiple of $2^{10}-1$ $2^{340} - 1 = (2^{10} -1 ) (1+2^{10} \cdot (2^{10})^2 + \dots +(2^{10})^{34})$ So $11 \mid (2^{340} -1 ) $
$\therefore 341 \mid (2^{340} -1 )$
If I had choosen $a=3$ instead, the test may work for 341 but would fail for some other number. We can’t just use 2 to test the number and we can’t always use 3. We have to test all possible number of $a$ to know whether number $m$ is prime.
Fact: A interger m is prime if and only if for any $1<a\leq m-1$ \[ m \mid (a^{m-1} -1) \]
Fermat Test
Refer to wikipedia for the concept and application of Fermat's primality test_
_Fermat's primality test:https://en.wikipedia.org/wiki/Fermat\_primality\_test