Math 240 Discrete Mathematics - Primality Testing

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

  1. $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)$

  1. $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