Number Theory Class and Methods Shean T. McMahon Readme.txt P231, Final Project File List: Readme.txt This file. Breif Overview of Class and Methods with examples Main.cpp Control program. Contains menus, I/O, calling routines, ... Numbers.h Header file. Contains number theory class and methods. Number theory is an area of mathematics concerned with the study of integers. The number theory class is a class and collection of methods which solve certain problems in this area of mathematics. The class addresses: Finding the Greatest Common Divisor of n numbers. Finding the Least Common Multiple of n numbers. Determining if a given number is prime. Determining if a pair of numbers are relatively prime. Determining of any twin primes exist for a given number. Determining the number of primes less than a given number. Determining the prime factorization of a given number. Solving congruences. Solving systems of congruences using the Chinese Remainder Theorem. Solving the totient function. Determining the sum of the divisors of a given number. Determining the number of divisors of a given number. Determining if a given number is a perfect number. A main function (main.cpp), which is essentially a system of menu's, prompts for information, and output strings is included to demonstrate operation of the class and associated methods. A bit of background information on each of the techniques is included for those unfamiliar with number theory. Greatest Common Divisor (GCD) The GCD of two numbers is the largest value, which divides both numbers an integer number of times. Example: The divisors of 20 are: 1, 2, 4, 5, 10, 20 The divisors of 15 are: 1, 3, 5, and 15 The GCD of 15 and 20 is 5. QED Methods which calculate the GCD for two numbers and n numbers are included. Least Common Multiple (LCM) The LCM of two numbers is the smallest number which both numbers divide an integer number of times. Example: The LCM of 22 and 16 is 176. Why? Looking at the multiples of 16 yields: 0, 16, 32, 48, ..., 144, 160, 176, 192, ... While the multiples of 22 are: 0, 22, 44, 66, ..., 132, 154, 176, 198, ... The least common multiple for numbers can be seen to be 176. QED Methods to calculate the LCM for two numbers and n numbers are included. Prime This method determines if a number is prime. The method returns a status code, which tells the calling function whether the given number is prime, composite, or not defined/out of bounds ( 0 or 1). Relatively Prime This method determines if two given numbers are relatively prime. Two numbers are relatively prime if they have no common factors other than 1. Note that the numbers do not have to be prime to be relatively prime. Example: 5 and 9 are relatively prime. Why? 5 is prime, so it has factors 1 and 5. 9 is composite, and has factors 1, 3, and 9. There are no common factors other than 1 here, so 5 and 9 are relatively prime. Example: 4 and 21 are relatively prime. 4 is composite, and has factors 1, 2, and 4 21 is composite, and has factors 1, 3, 7, and 21. There are no common factors other than 1 here, so 4 and 21 are relatively prime. Example: 18 and 78 are not relatively prime 18 has factors 1, 2, 3, 6, 9, and 18. 78 has factors 1, 2, 3, 6, 13, 26, 39, and 78. There are three common factors here other than 1, 2, 3, and 6. Therefore, 18 and 78 are not relatively prime. Twin Primes A twin prime is a prime number which differs from a given prime number by two. Example: 5 and 7 are twin primes Why? 5 and 7 are both prime, and they differ by 2. Therefore, they are twin primes. The twin prime method returns the number of twin primes which exist for a given number, as well as any the twin primes, should they exist. Number of Primes A method which finds the quantity of primes less than a given number is provided. Example: There are 7 primes less than 18. Why? The primes less than 18 are 2, 3, 5, 7, 11, 13, 17. Therefore, 7 primes less than 18 exist Prime Factorization This method determines the prime factorization of a given number. Congruences A congruence is written: a congruent b (mod m) In number theory literature, the term congruent is symbolized by the 3 bar equals sign, also known as the "defined" symbol. mod is just the modulus operation. The congruence, a congruent b ( mod m), just asks the question: "Is there some integer n, such that n * m = a - b. For example, 20 is congruent to 10 mod 5, as 2 * 5 = 20 - 10. Here, n is 2. Alternatively, 20 is not congruent to 10 mod 3, as no n exists, which will solve the relation. Chinese Remainder Theorem (CRT) The CRT states: For the system of congruences X congruent b1 ( mod m1) X congruent b2 ( mod m2) ... X congruent bi ( mod mi), Where the mi are pairwise relatively prime, there exists a unique solution modulo M = m1 * m2 * ... * mi. For example, given the system of three congruences X congruent 2 ( mod 3 ) X congruent 4 ( mod 5 ) X congruent 6 ( mod 7), A unique solution modulo M = 3 * 5 * 7 = 105 exists. In this case, the solution is 104. To solve this, we first generate a subsolution for the first two, and then find the solution to the pair consisting of the subsolution and the third congruence. For the first two, the CRT says a unique solution modulo M = 3 * 5 = 15 exists. We first generate all allowed values for one of the congruences which are less than M, and find which one solves the other in the pair. If we work on the second, we get X = 4 + 5 * 0 = 4 = 4 + 5 * 1 = 9 = 4 + 5 * 2 = 14. 14 will also solve the first congruence, so we now generate a new congruence using 14 and M. So, X congruent 14 ( mod 15) Now we solve the next pair, X congruent 14 ( mod 15) X congruent 6 ( mod 7) We solve this pair the same way we solved the first pair. It turns out, that X = 104 solves the original three congruences. Totient The totient function determines the number of integers not exceeding, and relatively prime to a given number. Example: The totient of 10 is 4. Why? The numbers which are less than 10, and relatively prime to 10 are 1, 3, 7, 9. There are four numbers here, so the totient of 10 is 4. QED Sum of Divisors The sum of the divisors of a given number is exactly that. The divisors are found, and then summed. Example: The sum of the divisors of 12 is 28. Why? The divisors of 12 are: 1, 2, 3, 4, 6, and 12. The sum of these numbers is: 1 + 2 + 3 + 4 + 6 + 12 = 28. QED Number of Divisors This method determines how many divisors, not prime factors of a given number exist. Example: There are 4 divisors of 22. Why? The four divisors of 22 are 1, 2, 11, and 22. QED Perfect Numbers A number n, is said to be a perfect number if the sum of its divisors equals 2 * n. Example: 6 is a perfect number. Why? The divisors of 6 are 1, 2, 3, and 6 The sum of these divisors is 1 + 2 + 3 + 6 = 12 2 * n = 2 * 6 = 12 12 = 12, therefore, n is a prefect number. QED