A prime or not a prime

Prime numbers

A prime number is an integer greater than 1 which is divisible only by 1 and by itself. For example, 5 is a prime but 6 is not since 6 is divisible by 1, 2, 3, and 6. There are infinitely many prime numbers. Here is the list of all primes smaller than 50:

\[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47\]

Prime numbers are the building blocks of integers: any integer \(n>1\) can be written in a unique way as a product of primes

\[n = p_{1}\cdot p_{2} \cdot {\dots} \cdot p_{m}\]

such that \(p_{1} \leq p_{2} \leq {\dots} \leq p_{m}\). This product called the primary decomposition of \(n\). For example: \(12 = 2\cdot 2\cdot 3\), \(25 = 5\cdot 5\), \(90 = 2\cdot 3\cdot 3\cdot 5\).

Exercise 1. Write a Python function myprimes(n) that returns the list of all primes smaller or equal to n, ordered from the smallest to the largest:

myprimes(10)

[2, 3, 5, 7]

myprimes(29)

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Exercise 2. Write a Python function primary(n) that for each integer n greater than 1 returns a list

\[[p_{1}, p_{2}, \dots, p_{m}]\]

where \(p_{1}, \dots, p_{m}\) are primes such that \(p_{1} \leq p_{2} \leq {\dots} \leq p_{m}\) and \(n = p_{1}\cdot p_{2} \cdot {\dots} \cdot p_{m}\):

primary(10)

[2, 5]

primary(90)

[2, 3, 3, 5]

Primes and false primes

Prime numbers are important in mathematics as well as in some practical applications. For example, they are used to encrypts data (credit card numbers etc.) so that it can be transmitted securely. For this reason it is interesting to look for new methods that can help us recognize which numbers are prime and which are not. Here we will explore one such possible method.

Congruences

Given integers \(m, n\) and \(k\) we say that \(m\) and \(n\) are congruent modulo \(k\) if the reminder from dividing \(m\) by \(k\) is the same as the reminder from dividing \(n\) by \(k\). In such situation we write \(m \equiv n \ (\text{mod } 7)\). For example \(19 \equiv 47 \ (\text{mod } 7)\) since

\[19 = 2\cdot 7 + 5 \ \ \ \ \ \ \ 47 = 6\cdot 7 + 5\]

so the reminder from division of both 19 and 47 by 7 is 5.

Note. The congruence relation is preserved by the arithmetic operations: if \(m_{1} \equiv n_{1} \ (\text{mod } k)\) and \(m_{2} \equiv n_{2} \ (\text{mod } k)\) then \(m_{1}+ m_{2} \equiv n_{1}+n_{2} \ (\text{mod } k)\) and \(m_{1}m_{2} \equiv n_{1}n_{2} \ (\text{mod } k)\).

Congruences and prime numbers

Here is a basic fact in number theory that relates prime numbers and congruences:

Theorem. If \(p\) is a prime number then

\[a^{p} \equiv a \ (\text{mod } p)\]

for any integer \(p > a \geq 0\).

For example, for \(p=3\) we have

\[1^{3} = \phantom{2}1 \equiv 1 \ (\text{mod } 3)\]
\[2^{3} = \phantom{2}8 \equiv 2 \ (\text{mod } 3)\]
\[3^{3} = 27 \equiv 3 \ (\text{mod } 3)\]
\[4^{3} = 64 \equiv 4 \ (\text{mod } 3)\]

which shows that the formula \(a^{3} \equiv a \ (\text{mod } 3)\) holds for \(a= 1, 2, 3, 4\).

The formula from the above theorem does not hold in general if \(p\) is not a prime number. For example for \(p = 4\) and \(a = 2\) we have \(2^{4}= 16\) which is not congruent to 2 modulo 4.

If it would turn out that the only numbers \(p\) that satisfy the formula \(a^{p} \equiv a \ (\text{mod } p)\) for all \(0 \leq a < p\) are prime numbers we would get a new way of recognizing which numbers are prime. It turns out, however, that there are numbers \(p\geq 2\) such that:

  • \(p\) is not a prime

  • the formula \(a^{p} \equiv a \ (\text{mod } p)\) holds for all \(0 \leq a < p\)

We will call such numbers false primes. The smallest number which is a false prime is 561.

Project

Part 1. Write a Python script to find the first 20 false primes.

Hint. Call a number \(p\) prime-like if \(p\geq 2\) and the formula \(a^{p} \equiv a \ (\text{mod } p)\) holds for all \(0 \leq a < p\). You can start your work on part 1 by writing a function isprimelike(n) that returns True if n is prime-like and returns False otherwise. Once you know that an integer is prime-like you just need to check that it is not a prime number.

Part 2. Compute the primary decomposition of each false prime you found.

Part 3. What can you say or conjecture about properties of false primes?

Note. In order to compute with Python the reminder from division of the number \(a^{n}\) by \(k\) we can use the command (a**n)%k. For example:

print(7**2 % 5)

4

This method is however inefficient, since Python computes first \(a^{n}\), which can be a very large number, and only then calculates the reminder from division by \(k\). A much faster way of performing the same computation is by using the function pow() which uses modular arithmetic to compute the power and the reminder at the same time. The result of the command pow(a,n,k) is exactly the same as that of (a**n)%k:

print(pow(7, 2, 5))

4

The function pow() can be also used with two arguments. The command pow(a,n) returns simply the power \(a^{n}\).

print(pow(7, 2))

49