A prime or not a prime¶
due: Thursday, September 14, 8:00 AM
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:
Prime numbers are the building blocks of integers: any integer \(n>1\) can be written in a unique way as a product of primes
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
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
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
for any integer \(p > a \geq 0\).
For example, for \(p=3\) we have
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