Number Theory

with MAPLE at UMBC

Contents

1. Integer Operations
2. Polynomial Operations
3. Gaussian Integer Operations
4. Finite Field Operations

The MAPLE programming language has basic commands and subroutines which implement all basic number theory (and many other things). A general introduction to MAPLE use and how MAPLE can be accessed at UMBC can be found in a separate document.

MAPLE supports the use of integers of arbitrary length and a number of other basic data types such as polynomials.

Integer Operations

The basic arithmetic operations, +, -, *, /, are available from the keyboard. Note that the division operator returns a quotient (eg 7/2 returns 7/2) so the answer should be truncated with the floor function (eg floor(7/2) returns 3). The modular reduction operator is represented by the mod command (eg 7 mod 2 returns 1). Exponentiation is represented with the ^ symbol.

Examples:

• (8 + 7) mod 13;
  (returns an answer of 2)
• (5 * 4) mod 13;
  (returns an answer of 7)
• floor(7 / 2);
  (returns an answer of 3)
• 3^2;
  (returns an answer of 9)

In addition to the basic arithmetic operations for integers MAPLE implements gcd and the extended gcd operations as basic functions:

Examples:
• gcd(15,6);
  (returns an answer of 3)
• igcdex(23,7,'s','t');
  (returns an answer of 1 and gives s and t values of -3 and 10 respectively, as 23*(-3)+7*10=1)
• floor(7 / 2);
  (returns an answer of 3)

Efficient modular exponentiation (the Russian Peasant algorithm) is implemented with the Power command, so
Power(2,1236) mod 1237;
returns the value 1.

Factoring and primality testing are implemented with the ifactor and isprime commands. Examples of their use are
ifactor(123456);
which returns the product 2^6*3*643 and the command
isprime(643);
which returns the value true.

More information on manipulating integers in MAPLE can be gotten with the help command:
?integer

Polynomial Operations

Polynomials are represented using the usual arithmetic operations. Thus, the polynomial 2x³+5x²-x+2 is typed in as 2*x^3+5*x^2-x+2.

Polynomials are manipulated and combined with the same basic operations as are used on integers, +, -, *, ^. Division is done with the quo() and rem() commands. Multiplication and exponentiation operations are left unevaluated unless the expand() command is used to force expansion and evaluation.

Examples:

• (x^2+2*x+1)+(x+5);
  (returns an answer of x²+3x+6)
• (x^2+2*x+1)*(x+5);
  (returns an unevaluated answer of (x²+2x+1)*(x+5))
• expand((x^2+2*x+1)*(x+5));
  (returns an answer of x³+7x²+11x+5
• expand((x+1)^2);
  (returns an answer of x²+2x+1)
• quo(x^2+3,x+1,x);
  (returns the quotient of the two polynomials w/ variable "x", x-1)
• rem(x^2+3,x+1,x);
  (returns the remainder of the polynomial division, 4)

The Euclidean and extended Euclidean algorithms for polynomials are implemented with the gcd() and gcdex() commands. Polynomials are factored with the factor() command and irreducibility (ie primality) is checked with the irreduc() command.

Examples:
• gcd(x^3+2*x^2+x+2,x^2+5*x+6);
  (returns an answer of x+2)
• factor(x^3+2*x^2+x+2);
  (returns an answer of (x+2)(x²+1))
• irreduc(x^3+2*x^2+x+2);
  (returns an answer of false)

When working with polynomials over a ground field other than the integers or rationals you use similar operations whose names start with a capital letter. If the coefficients are the integers mod some integer use the mod operator:

• Factor(x^2+3*x+3) mod 7; # Factor with coefficients mod 7
• Irreduc(x^8+x^5+1) mod 2;
• Powmod(x,12,x^8+x^5+1,x) mod 2; # Compute x¹² (mod x⁸+x⁵+1) w/ coeffs mod 2

More information on manipulating polynomials in MAPLE can be gotten with the help command:
?polynomial

Gaussian Integer Operations

Computation in the ring of Gaussian Integers (ie the set of complex numbers of the form (m+ni), where m and n are integers and i is the square root of negative one) is done with the commands in the standard MAPLE package GaussInt. In order to use the commands in this package you must first load it with the command:
with(GaussInt);
This command will print out a list of the commands available in the package.

The square root of negative one is represented in MAPLE with a capital letter "I", so the Gaussian Integer 2+3i is is typed into MAPLE as 2+3*I.

Gaussian Integers are manipulated and combined with the same basic operations as are used on integers, +, -, *, ^. Division is done with the GIquo() and GIrem() commands.

Examples:

• (2+3*I)*(1-I);
  (returns an answer of 5+I)
• (2+3*I)^2;
  (returns an answer of -5+12I)
• GIquo(5+2*I,1+I);
  (returns the quotient 3-I)
• GIrem(5+2*I,1+I);
  (returns the remainder 1)

The Euclidean and extended Euclidean algorithms for Gaussian Integers are implemented with the GIgcd() and GIgcdex() commands. They are factored with the GIfactor() command and primality is checked with the GIprime() command.

Examples:
• GIfactor(7+5*I);
  (returns an answer of (I)(1+I)(-1-6I))
• GIprime(7+5*I);
  (returns an answer of false)
• GIgcd(7+5*I,8-2*I);
  (returns an answer of 1+I)

More information on using the GaussInt package to manipulate Gaussian Integers in MAPLE can be gotten with the help command:
?GaussInt

Finite Field Operations

Finite fields (or Galois Fields) are represented by polynomials with operations performed modulo some fixed irreducible polynomial and coefficients reduced modulo some prime. Operations in a finite field may be represented with the use of the usual operators along with the Rem operator, as well as the Powmod operator.

As an example, consider the field GF(2⁵), as represented by the polynomials with coefficients mod 2, reduced modulo the fixed irreducible fifth-degree polynomial x⁵+x³+1:
> Irreduc(x^5+x^3+1) mod 2; # Confirm irreducibility
> Rem((x^3)*(x^2+x),x^5+x^3+1,x) mod 2; # Multiply two elements
> Powmod(x+1,31,x^5+x^3+1,x) mod 2; # Compute (x+1)^31

There is also a package which is distributed with MAPLE which implements Galois Fields in a more consistent (but more clumsy and verbose) manner. Documentation for the GF package can be found with the help command:
?GF

A. Other Resources

• Jim Gallentine's Notes at Colorado State Univ