A Journey Through Discovery: Exploring Primality in Modular Arithmetic By: Nick Anderson Megan Funk Robert Messerschmidt Introduction  We began our quest by looking into modular arithmetic.  Then, we explored the idea of generators and what numbers constituted a generator.  But, we did not explore even numbers as generators. Modular Arithmetic  Modular arithmetic, which is also known as clock arithmetic, is a system of arithmetic for integers that begins and ends at the same place.  For example, if you are looking at numbers mod 5, once you go beyond the number 5, the numbers start over again.  So 6 is congruent to 1 mod 5.  This system is the basis of our research. Composite Modulo  We looked at composite modulo and found that no odd composite modulo that is not a prime power would allow a generator.  We focused on the prime modulo and looked at a few composite, but those were not of interest. Generators  We defined a generator through a process.  First, we choose a prime number, p, to investigate.  Then, we looked at each number in the set respectively to find out which numbers produced all numbers in the set mod p. Generators cont…  Then we made sure that the sets produced ended at the number 1.  We said that these sets are generator sets and the first number in the sets are generators.  From here, we looked into grouping these generator sets. Grouping Generators  We found that generators can be grouped based on the number of elements that bring the set back to the starting point.  For example, if we look at the set Z(13), and the number 3 within Z(13), the generator set is 3-9-1, so the order is 3.  Another example in Z(13) is 5, the generator set is 5-12-8-1, so the order is 4.  With this information we were able to group sets based on their order. Information detailing the code used as well as why this was useful to our cohort Primal Data Different Programs  Primes – Sieve of Eratosthenes  Generators – Program which “generated” generators  Different timings for implementations Results  Added computational power lead to big results  This shifted our focus to interpretation  Properties of Generators 8 Smallest Generators for first 100 Primes 7 6 5 4 3 2 1 0 0 10 20 30 40 50 60 70 80 90 100 First 100 Primes Smallest Generator 25 Smallest Generators for first 1000 Primes 20 15 10 5 0 0 100 200 300 400 500 600 700 800 900 1000 First 1000 Primes Smallest Generator 35 Smallest Generators for first 10000 Primes 30 25 20 15 10 5 0 0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 First 10000 Primes Smallest Generator 50 Smallest Generators for first 100000 Primes 45 40 35 30 25 20 15 10 5 0 0 10000 20000 30000 40000 50000 60000 70000 80000 90000 100000 First 100000 Primes Smallest Generator Smallest Generators for first 375,000 - ish primes 80 70 60 50 40 30 20 10 0 0 200000 400000 600000 800000 1000000 1200000 First 375000-ish Primes Smallest Generator R Charts Bound on the smallest generator for the first 1,000,000 primes Or, in general On to Robert!! Now What?  Overall goal? Primality testing  Analyze our data and find patterns.  Least generator ◦ Frequency of different least generators Frequency of Least Generators to 1,000,000( as %) 2 29 40 3 28 35 5 30 26 6 25 20 24 7 15 10 23 5 10 0 22 11 21 12 20 13 19 14 18 15 17  This information may lead us to ◦ Find certain numbers that allow us to find the least generator without random testing. ◦ What numbers, that have least generators that approach the upper bound (Large), may have in common. ◦ How can we exclude larger groups of elements from testing/improve our algorithms? Questions? Comments? Thank you to Siguna Mueller and Mathematics Nick Anderson nanders5@uwyo.edu Megan Funk funk@uwyo.edu Robert Messerschmidt rmessers@uwyo.edu