A positive integer $p$ is prime if the only positive integers dividing $p$ are $1$ and itself. Prime numbers play a crucial role in number theory, and as such have long been the subject of much interest. It was proved by Euclid more than 2000 years ago that there are infinitely many primes. In the 1600s, the French mathematician Pierre de Fermat discovered the following fact about prime numbers, which later became known as known as Fermat's little thoerem:
Fermat's little theorem: If $p$ is a prime number, then
$$a^p \equiv a \quad(\text{mod }p)$$for all $0 \leq a < p$
Here, the statement $a \equiv b \,(\text{mod }p)$ means that $a$ and $b$ have the same remainder after dividing by $p$, where $\text{mod}$ is short for "modulo". In view of Fermat's little theorem, we say that a number $n$ is prime-like if it satisfies the conclusion of the theorem, that is, if $a^n \equiv a \,(\text{mod }n)$ for all $0 \leq a < n$. Fermat's little theorem can then be simply stated as "every prime number is prime-like."
A natural question then arises: is the converse true? That is, is every prime-like number prime? It turns out that this is false! There exist numbers which are prime-like but not prime. We call such numbers false primes.
In this report we will explore the properties of these false primes.
A first step toward studying false primes is being able to identify them. Toward that end, we begin with identifying prime numbers. Recall that a positive integer $p$ is prime if its only positive integer divisors are $1$ and $p$. On the other hand, if a number $n$ is not prime, then it must be divisible by at least one factor $2,3,...,$ or $n-1$. We can then test a given number $n$ for primeness by checking whether it is divisible by any of these possible factors.
Note that $a$ divides $n$ exactly when the remainder of $n$ divided by $a$ is zero.
In Python, this check for divisibility can be performed with the Boolean expression n % a == 0, where the % symbol is the modulo operation.
If this check fails for any $a$, then the number $n$ is not prime.
If however the check succeeds for every $2 \leq a \leq n-1$, then the number $n$ is prime.
While it is sufficient to check each of the possible factors $2, 3,...,$ and $n-1$ when testing for primality, we can greatly speed up our algorithm with a simple observation. Namely, if a number $n$ is not prime, then it must have at least one factor $q \leq \sqrt{n}$. Otherwise, $n$ would necessarily have at least two factors $q$ and $r$ with $q,r > \sqrt{n}$, so that $n \geq q\cdot r > n$, which is a contradiction. Incorporating this observation into our algorithm means that we need only check the possible factors which are no larger than $\sqrt{n}$.
The function is_prime(n), defined below, returns the True if n is prime and False if n is not prime, using the ideas discussed above.
from math import sqrt # import the square root function from the math module
def is_prime(n):
if n < 2:
return False # There are no prime numbers less than 2
for a in range(2,int(sqrt(n) + 1)): # Iterate over possible factors no greater than sqrt(p)
if n % a == 0: return False # If 'a' divides 'p', 'p' is not prime
return True # If no factor was found, 'p' is prime
It will be useful to generate lists of prime numbers. The function get_primes(N) generates the list of all primes which are no greater than $N$ by checking whether each number $2,3,...,N$ is prime.
def get_primes(N):
primes = [] # Initialize an empty list of primes
for n in range(2,N+1): # Iterate over the integers from 2 to N
if is_prime(n): primes.append(n) # Add n to the list if n is prime
return primes
We can test the functions is_prime and get_primes by comparing the output of get_primes to a known list of primes (see Sequence A000040 from The On-line Encyclopedia of Integer Sequences):
print(get_primes(50))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
In order to identify false primes, we first need to be able to identify prime-like numbers.
To test whether a number $n$ is prime-like, we must check whether $a^n \equiv a \,(\text{mod }n)$ for every $0 \leq a < n$.
In Python, this check can be performed with the Boolean expression a**n % n == a % n, where ** denotes exponentiation.
Note that, in computing this check as written above, Python will need to compute a**n before evaluating the remainder modulo n. As a or n become large, a**n will become orders of magnitude larger. On the other hand, the final result a**n % n will remain on the order of n. A useful optimization is to use the builtin pow() function to evaluate this remainder. The calling sequence pow(a,n,k) is equivalent to a**n % k in result, but makes use of modular arithmetic to optimize the calculation.
The function is_primelike(n), defined below, returns True if n is prime-like and returns False if n is not prime-like, using the ideas discussed above.
def is_primelike(n):
for a in range(n): # Iterate over all 'a's to be checked.
if not pow(a,n,n) == a % n: # If any 'a' fails to satisfy the conclusion of Fermat's little theorem,
return False # then 'n' is not prime-like
return True # If all checks passed, then 'n' is prime-like
Together the functions is_prime and is_primelike allow us to define a function is_false_prime(n) which returns True if n is a false prime and False if n is not a false prime. That is, the function is_false_prime(n) returns True if is_prime(n) is False and is_primelike(n) is True, and returns False otherwise.
def is_false_prime(n):
if not is_prime(n) and is_primelike(n): # 'n' is a false prime if it is not prime
return True # and is prime-like
return False # otherwise, 'n' is not a false prime
It should be noted that the order that these checks are carried out in the is_false_prime function is not inconsequential.
Although the following Boolean expressions
not is_prime(n) and is_primelike(n)
is_primelike(n) and not is_prime(n)
are logically equivalent, their evaluation in Python has a crucial difference.
Namely, if the first part of an and conjunction is False, then Python will not bother to evaluate the second part, since the conjunction will be False regardless.
With this in mind, we define the is_false_prime function to test n for primality before testing for prime-likeness.
The reasoning for this is two-fold:
is_prime function was greatly improved in efficiency by checking only those possible factors $a$ which are no greater than $\sqrt{n}$. We were not able to make the same optimization for the is_primelike function.is_primelike function will not find any $a$ for which the check $a^p \equiv a\,(\text{mod }p)$ fails, meaning that it will check all $n$ possibilities before returning True. We can test the is_false_prime function with some simple examples:
for n in [1,3,4]: # test 1,3, and 4 for false primeness
if is_false_prime(n):
print('{:} is a false prime.'.format(n)) # print whether 'n' is a false prime
else: print('{:} is not a false prime.'.format(n)) # or not
1 is a false prime. 3 is not a false prime. 4 is not a false prime.
It is clear that $3$ is not a false prime, since it is itself prime. To verify the remaining cases, we look at the following table of calculations:
For $n=1$:
| $$\quad a\quad$$ | $$\quad a^1\quad$$ | $$\quad a^1 \,\,(\text{mod }1)\quad$$ |
|---|---|---|
| 0 | 0 | 0 |
For $n=4$:
| $$\quad a\quad$$ | $$\quad a^4\quad$$ | $$\quad a^4 \,\,(\text{mod }4)\quad$$ |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 1 | 1 |
| 2 | 16 | 0 |
| 3 | 81 | 1 |
From the tables, we see that
which is supported by the output from the is_false_prime function.
We next define a function get_false_primes(N) which will generate a list of the first N false primes, using the is_false_prime function.
Note that, unlike in the get_primes function above, we do not know a priori how many numbers we will need to test for false primeness in order to generate the first N false primes.
With this in mind, we make use of a while loop that will continue testing numbers until we have found the desired number of false primes.
def get_false_primes(N=20):
false_primes = [] # Initialize an empty list of false primes
n = 1 # Start the search at 'n' = 1
while len(false_primes) < N: # Continue searching for false primes until we've found 'N'
if is_false_prime(n):
false_primes.append(n) # Add 'n' if it is a false prime
n += 1 # Increment 'n' to check the next number
return false_primes
With the get_false_primes function defined above, we can now easily find false primes. We find the first 20 false primes below:
false_primes = get_false_primes(20)
print('Count | False prime')
print('-------------------')
for i,false_prime in enumerate(false_primes):
print('{:>4} | {:}'.format(i+1,false_prime))
Count | False prime ------------------- 1 | 1 2 | 561 3 | 1105 4 | 1729 5 | 2465 6 | 2821 7 | 6601 8 | 8911 9 | 10585 10 | 15841 11 | 29341 12 | 41041 13 | 46657 14 | 52633 15 | 62745 16 | 63973 17 | 75361 18 | 101101 19 | 115921 20 | 126217
One immediate observation is that each of these false primes are odd. This might suggest that this is true for all false primes, though these 20 cases are not enough to confirm this conjecture. However, a simple argument shows that this is indeed the case:
Suppose that $n$ is an even false prime. Since $n$ is prime-like, we have
$$n-1 \equiv (n-1)^n \,\, (\text{mod } n).$$On the other hand, the properties of modular arithmetic tell us that
$$(n-1)^n \equiv (-1)^n \,\,(\text{mod }n).$$Since $n$ is even, we know that $(-1)^n = 1$. Connecting these statements, we have
$$n-1 \equiv 1\,\,(\text{mod } n),$$which can be equivalently stated as $0 \equiv 2 \,\,(\text{mod }n)$. This cannot happen unless $n = 1$ or $n=2$. But $n$ cannot be $1$ since $n$ was assumed to be even, and $n$ cannot be $2$ since $n$ was assumed to be a false prime (and so, not a prime number).
We have reached a contradiction, which means that $n$ can not be a even false prime. Thus every false prime must be odd.
The fundamental theorem of arithmetic states that every integer greater than $1$ can be represented uniquely as a product of prime numbers (up to the order of the factors). This representation is called the prime decomposition of $n$. As an example, the prime decomposition of $60$ can be written as
$$60 = 2\cdot 2\cdot 3 \cdot 5$$To continue our exploration of false primes, we next define a function get_prime_decomp(n) which finds the prime decomposition of a number n.
In order to find the prime decomposition of n, we make use of the get_primes function to first generate a list of possible prime factors.
We then iterate through the list of possible prime factors, and count how many times each factor p divides n.
To perform this count, we introduce a temporary variable m initialized to be equal to n.
If p divides m, we add it our prime decomposition and redefine m to remove the factor p that was just discovered.
We then check if p divides the new m.
This continues in like fashion until p no longer divides m, at which point we proceed to the next prime number.
def get_prime_decomp(n):
prime_decomp = [] # Initialize an empty list for the prime decomposition
primes = get_primes(n) # Generate the list of possible prime factors
for p in primes:
m = n # Initialize the temporary variable 'm' equal to 'n'
while (m % p) == 0: # If 'p' divides 'm'...
prime_decomp.append(p) # add 'p' to the prime decomposition...
m = m//p # and factor 'p' out of 'm'
return prime_decomp
We test the function get_prime_decomp with n=60 and compare to the prime decomposition given above:
print(get_prime_decomp(60))
[2, 2, 3, 5]
This gives the expected prime decomposition for $n=60$, including the repeated prime factor $p=2$.
We next find the prime decompositions for each of the false primes we've found, and print these decompositions for study.
prime_decompositions = [ get_prime_decomp(n) for n in false_primes ]
print('Count | False prime | Decomposition')
print('-----------------------------------------')
for i,(false_prime, prime_decomposition) in enumerate(zip(false_primes, prime_decompositions)):
print('{:>4} | {:>8} | {:}'.format(i+1,false_prime,
' *'.join([str(p).rjust(3) for p in prime_decomposition])))
Count | False prime | Decomposition ----------------------------------------- 1 | 1 | 2 | 561 | 3 * 11 * 17 3 | 1105 | 5 * 13 * 17 4 | 1729 | 7 * 13 * 19 5 | 2465 | 5 * 17 * 29 6 | 2821 | 7 * 13 * 31 7 | 6601 | 7 * 23 * 41 8 | 8911 | 7 * 19 * 67 9 | 10585 | 5 * 29 * 73 10 | 15841 | 7 * 31 * 73 11 | 29341 | 13 * 37 * 61 12 | 41041 | 7 * 11 * 13 * 41 13 | 46657 | 13 * 37 * 97 14 | 52633 | 7 * 73 *103 15 | 62745 | 3 * 5 * 47 * 89 16 | 63973 | 7 * 13 * 19 * 37 17 | 75361 | 11 * 13 * 17 * 31 18 | 101101 | 7 * 11 * 13 *101 19 | 115921 | 13 * 37 *241 20 | 126217 | 7 * 13 * 19 * 73
The prime factorization for each of the false primes listed above (aside from 1) includes at least 3 primes. Moreover, there are no repeated prime factors in any of these prime decompositions. These observations suggest that all false primes may share these properties.
In summary, we have introduced and explored the properties of false primes, that is, numbers which are prime-like but not prime. We were able to prove the following fact about false primes:
Although we are not able to prove them, we make the following conjectures about false primes:
With the Python tools developed above, we can only ever generate a finite number of false primes to test these conjectures. Instead, one could employ tools from Number Theory to try and prove these conjectures.
Other potential avenues for exploration include studying the distribution of the false primes:
These questions are difficult to study, as the computation costs of identifying false primes grows as the numbers increase in size, which may become prohibitive. Nonetheless, they raise interesting opportunities for further exploration.