1    Introduction

1.1    What is a prime?

A prime  number, is an integer greater than 1 which is divisible by only 1 and itself.   For  example,  5  is  a  prime  number since  its ony factors are  1  and  5, however 6 is not a prime number since aside from 1 and 6 it also has factors 2

and 3. Here are all the primes less than 50

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

Prime numbers are the fundamental building blocks of all the integers.  Every

n = p1 · p2   pm                                                                  (1)

such that p1  ≤ p2  ≤ p3  ≤ ... ≤ pm .This is called the primary  decomposition  or prime factorization of n. Here are some examples of primary decomposition.

12 = 2 · 2 · 3

25 = 5 · 5

90 = 2 · 3 · 3 · 5.           (2)

1.2    Primes and false primes

Aside from being important in mathematics, prime numbers also have various practical applications such as data encryption.  Thus it is of interest to recognize if a number is prime or not and come up with methods to do so.  One such possible method is described here.

1.2.1    Congruence

Two numbers m and n are said to be congruent modulo k , m 三 n(  mod k) if m  mod k = n  mod k, that is if both m and n are divided by k they will have the same remainder. For example 19 三 47(  mod 7) since

19 = 2 · 7 +  5

47 = 6 · 7 +  5  .

Theorem 1  Congruence   is  perserved   by  arithmetic   operations.     That  is,   if m1  三 n1 (  mod k)  and m2  三 n2 (   mod k),  then m1  + m2  三 n1  + n2 (  mod k) and m1 m2  三 n1 n2 (  mod k) .

Aa important fact in number theory that deals with congruence is Fermat’s little theorem.

Theorem 2 (Fermat’s little theorem)  If p is a prime number, then for any integer a such that p > a ≥ 0

ap  三 a(    mod p).                                              (3)

For example, for p = 3

13  = 1 三 1(    mod 3)

23  = 8 三 2(    mod 3)

33  = 27 三 3(    mod 3)

43  = 64 三 4(    mod 3).

1.2.2    False primes

The formula in the above theorem does not generally hold if p is not prime, for example 24  = 162(  mod 4).  If it were true that only prime ps satisfied ap  三 a(  mod p) for all 0 ≤ a < p then we would have a new way of recognizing which numbers are primes which would be cool and important.  Unfortunately there are non-prime values of p for which the formula in equation (3) holds.  We Call such numbers “false primes” .

A number p is a false prime if

. p is not prime

. the formula ap  三 a(  mod p) holds for all integer values of a such that 0 ≤ a < p.

The smallest flase prime is 561.  In this project we will explore the properties of false primes.

2    Project Components

1. Write a function myprimes(n) that returns a list of all prime numbers less than or equal to n.

.  Ex: myprimes(10) returns [2, 3, 5, 7].

.  Ex: myprimes(11) returns [2, 3, 5, 7, 11].

.  For an efficient way of doing this see “sieve of Eratosthenes.”

2. Write a function primary(n)  that for each integer n returns its primary decomposition.  That is, it returns a list [p1 , p2 ,..., pn] where p1 , p2 ,..., pn are prime numbers such that p1  ≤ p2  ≤ p3  ≤ ... ≤ pm and n = p1 ·p2 · ... ·pm .

.  Ex: primary(10) returns [2, 5].

.  Ex: primary(90) returns [2, 3, 3, 5].

3. Write a python script to find the first 20 false primes.

.  Hint:  Call a number p  “prime-like” if it is  ≥ 2 and the formula in equation  (3) holds for it.  You can write 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 if it is prime.

4.  Compute the primary decomposition of each of the first 20 false primes you found.

5. What can you say or conjecture about the properties of false primes.

2.1    Note

In this project you will often have to perform the following operation ab    mod c. While this is doable in python with a**b  % c this is computationally inefficient. Instead this operation can be made more efficient by using the pow(·) function. The result of the command pow(a,b,c)  is equivalent to the result of a**b  %  c but much more computationally efficient.  USE THE POW FUNCTION! The command pow(a,b) just returns ab.

3    Grading

The report grade will have the following distribution:

3.1    Introduction

The introduction is the first section of your report. It describes the project (the underlying math) and the goals of the report. It should be written in away that is engaging and understandable to a student who has some background in math and coding but does not take this course. The introduction SHOULD NOT be in list form.  While some of the concepts in the introduction will be repeated from the project description, you should state the concepts in your own words and not copy from the project description.

3.2    Conclusion

This section should summarize your results and major findings.   It  can also include potential future extensions of the project. This should be the last section of the report.

3.3    Content and presentation

Outside of the two section mentioned your report should be broken up into sections and subsections in such a way as to maximize readability and compre- hensibility. Where appropriate use Latex to format math.

PLEASE INCLUDE YOUR NAME AND UB ID NUMBER INSIDE THE REPORT AS WELL AS INCLUDING YOUR NAME AS PART OF THE SUB- MITTED FILE NAME!

3.4    Code

Your code should be readable and understandable.  Code should be broken up into small snippets each of which gets its own cell.  Words should be used to describe what the code is doing and what the logic of your approach is.  DO NOT put all of your code into a single section with no words or discussion.

Code should be readable with understandable variable names and comments included to explain what is not clear.

All python code included in the report should be written in such a way that it can be executed sequentially.  For example, a function should never be used prior to its definition.

All code included must work. Do not submit code with errors.

Code output must serve the narrative of your report and should be formatted for easy reading and understanding.

3.5    Use of external resources

You are allowed but not at all required to consult resources outside of what is presented in the course.  If you use an external resource in a significant way (not just googling an error message or a command that you forgot) please include a citation in your report.  You are welcome to use features of python that were not shown in this class but you must understand fully what the feature does.