# MTHT 435 Foundations of Number Theory

## Useful MAPLE Commands

Chapter 1: Divisibility
• Division: Suppose b is positive and we want to write a=qb+r. We can calculate q using the command:

floor(a/b);

and we can calculate r using the command
a mod b;

as we will frequently want to calculate both q and r it is useful to define a simple function. Here is a function called idiv for integer division. Add the following definition to your worksheet.
idiv:=(n,m)->[floor(n/m),n mod m];

Once we have defined idiv if we give the command
idiv(a,b);

MAPLE will return the pair
[q,r]

where a=qb+r.

• gcd(a,b) and lcm(a,b) can be computed with the commands
gcd(a,b);
lcm(a,b);
Chapter 3,4 Congruences
• We calculate a (mod n) using the command
a mod n;
For example 4*7 mod 5 will return 3

• If a and n are relatively prime we can solve ax=b mod n by
b/a mod n

• We can define a function modpow such that modpow(a,x,n) returns a^x (mod n)
modpow:=(a,x,n)-> piecewise( x=0, 1, x=1, a mod n, x mod 2=1 , a*modpow(a,x-1,n) mod n, x mod 2=0, modpow(a,x/2,n)^2 mod n);