Number Theory Class and Methods

0.0 Background and Overview

Number theory is a branch of mathematics dealing with the behaviour of integers, and the various relations which exist between them. It is a very rich and diverse field, and covers topics from the mundane, such as divisibility, to the esoteric, such as Fermats last theorem. It also includes topics such as Diophantine equations, prime numbers, Wilson and Catallan numbers and so forth.

Congruences are a particularly interesting area of Number Theory. Two numbers a and b, are said to be congruent if, when a and b are divided by a third number n, they have the same remainder. Consider the example of a = 24, and b = 18. a and b are said to be congruent modulo 6. Additionally, they would be congruent for n = 1, 2, and 3. They would not be congruent modulo 9 however. To see why, consider the case of n = 6. For a, 24 / 6 = 4, with remainder 0. For b, 18 / 6 = 3, again with remainder 0. Since the remainders are the same in each case, these numbers are said to be congruent modulo n.

Just as in algebra, it is natural to extend the concept of an equation to that of systems of equations, in Number theory, congruences can be extended in a similar way. The result is a problem called the Chinese remainder theorem. This theorem says, let m1, m2, …, mr be pairwise relatively prime integers. Then the system of congruences,

has a unique solution modulo M = m1m2…mr.

As a historical aside, this problem is called the Chinese Remainder Theorem after Chinese mathematician Sun-Tsu, who, around 100A.D., presented a rule which would determine a number x, having remainders 2, 3, and 2 when divided by 3, 5, and 7 respectively. What Sun-Tsu was proposing was a rule which would solve the following system of congruences

It is because of Sun-Tsu’s proposal, that this problem is called the Chinese Remainder Theorem.

Solution of the Chinese remainder theorem requires knowing whether two numbers are relatively prime or not, which in turn requires determining the factorization of the numbers in question. So, this small set of topics, leads to a set of interesting problems to solve.

Most areas in number theory use at least one of the above concepts. For example, the greatest common divisor (GCD), and the least common multiple (LCM), both use factorization in their solution; the GCD in that it effectively factors both numbers and finds the largest common value, while the LCM can be found by forming the product of the two numbers, then dividing by the GCD.

In addition, various relations exist among prime numbers. These include the most basic, which is testing whether a number is prime, as well as more advanced, including relative and twin primality, and how many primes exist which are less than a given number. Twin primes are primes separated by 2. Three and five, and five and seven are two examples. Relative primality investigates whether a set of numbers have any common factors. If no common factors exist, than the numbers are said to be relatively prime. Note, that two numbers do not have to be prime to be relatively prime; 4 and 9 are an example of two relatively prime numbers, which themselves are not prime. The number of primes less than a given number is exactly that. In the case of 10, the result would be 4; the primes 2, 3, 5, 7.

The totient functions is another function from number theory which is intimately connected to prime and relatively prime numbers. Specifically, the totient function for n, returns the number of integers not exceeding, and relatively prime to n. For example, if we were to take the totient of 6, there exist five positive integers (not including zero) less than 6, of which two of them (1, 5) are relatively prime. So, the totient of 6 is 2. Other functions related to the totient include the sum of the divisors of n, where integers which wholly divide n are summed, and the number of divisors of n. Finally, there is the concept of perfect numbers. A perfect number n, is one where the sum of the divisors equals 2n.

1. Proposal

 

The proposed project will implement classes and methods to determine, solve, or assist in the solution of the following:

* Prime Number Relations

If a number is prime

If n numbers are relatively prime

If a pair of numbers are twin primes

The number of primes less than a given number

* Modulus Related Operations

Congruences

Chinese Remainder Theorem (Systems of Congruences)

* Prime Factorization

Case for n numbers

* Greatest Common Divisor

Case for n numbers

* Least Common Multiple

* Totient and Related Functions

Totient Function

Sum of Divisors of n

Number of Divisors of n

Perfect Numbers

 

2. Implementation Plan

 

Each of the topics proposed will be implemented using an individual class. A main() program will be written which asks the user which area they are interested in, and then proceeds to ask the relevant questions, finally outputting the result.

2.1 Requirements for Each Class

Each of the above techniques has commonalties with each of the others. For example, prime factorization requires a knowledge of whether a number is prime. Similarly, the Chinese remainder theorem uses the concept of relative primality, which itself uses prime factorization.

Including the many instances of the various subfunctions required for the above collection, using simple inheritance would be inefficient on a space basis, as many functions would need to be duplicated in each class. It therefore makes more sense to allow the classes to access eachother. This approach has advantages and disadvantages. On the plus side, the overall program would be physically smaller. This is not as much an issue today with the large amounts of memory found on most computers. It also offers the advantage of limiting the duplication process by the programmer, in that duplicate functions would not need to be generated.

On the down side, by keeping the subfunctions separate, the classes must be used together; e.g. I could not take the factorization class and use it by itself, as it is dependant upon the results from the prime class. Because of this, each class will include the functions needed for it to fully operate. This will allow the classes to be self-contained, this increasing their portability.

3. Class Requirements

* Modulus Related Operations

* Prime Factorization

* Greatest Common Divisor

* Least Common Multiple

* Totient and Related Functions