- Check out the commands
`gcd`and`factor`, and test them on different numbers, small and large. - Axiom provides a few useful commands for taking apart the factors of an
object:
- n:=5040
- f:=factor(n)
- numf:=numberOfFactors(f)
- fs:=[nthFactor(f,i) for i in 1..numf]
- es:=[nthExponent(f,i) for i in 1..numf]
- reduce(*,[fs.i^es.i for i in 1..numf])

- The last command simply multiplies all the factors to their powers.
- Check out the commands
`prime?`,`nextPrime`and`prevPrime`. - To compute the
`i`-th prime, we can construct a*stream*(an infinite list) in Axiom:- primes:Stream Integer:=[i for i in 2.. | prime? i]

- Now we can find, for example, the 100-th prime, and the 2500-th prime:
- primes.100
- primes.2500

- Create random 10 digit primes:
- p := nextPrime(random(10^10))
- q := nextPrime(random(10^10))

- Now multiply them and factor the product. How long did it take?
- Try the same thing with 12 digit primes and 15 digit primes.
- The extended Euclidean algorithm is implemented by the command
`extendedEuclidean`. Here's how to use it:- a:=1149
- b:=3137
- g:=extendedEuclidean(a,b)
- s:=g.coef1
- t:=g.coef2

- and now test them:
- s*a+t*b

- Try this on a few other numbers.
- Axiom uses the command
`positiveRemainder`instead of`mod`command, so let's define`mod`to be a renaming of the`positiveRemainder`function:- mod ==> positiveRemainder

- Now the commands
`addmod`,`submod`,`mulmod`, and`invmod`can be used to perform modular arithmetic. Here's a few examples; first a simple modulus calculation:- -10 mod 3

- Addition, subtraction and multiplication mod 14:
- addmod(10,13,14)
- submod(17,23,14)
- mulmod(13,27,14)

- Powers and inverses:
- powmod(19,237,14)
- invmod(11,14)

- Find out what happens if you try to take an inverse of a number not
relatively prime to the modulus:
- invmod(12,14)

- Try these command with a few other numbers, and test out the examples in the notes.
- The second method, which can be more powerful, is to treat all numbers
as elements of the residue values 0 to
`n-1`. This can be done with the`IntegerMod`construction, or its abbreviation`ZMOD`. Here's a few examples:- a:=11::ZMOD 14

- This declares the variable
`a`to be a member of the residue class modulo 14. Now all arithmetic including`a`will be reduced to this same class of values:- a+25
- a*39
- a^537

- Inversion can be done with the
`recip`command:- recip(a)

- We don't have to define a variable first. All the above commands could
be equivalently written as:
- (11::ZMOD 14)+25
- 11::ZMOD 14*39
- 11::ZMOD 14^537
- recip(11::ZMOD 14)

- If the modulus is a prime, then division (by non-zero values) is also
possible. Axiom provides the alternative construction
`PrimeField`or more simply`PF`. For example:- a:=7::PF 11

- All the above arithmetic operations of addition, subtraction,
multiplication and powers work, but now we also have inversion:
- 1/a

- Using any of the methods you like, test out Fermat's theorem for a large
prime
`p`and an integer`a`. - Euler's totient function is implemented with
`eulerPhi`. Choose a large integer`n`, a random`a`with`gcd(a,n)=1`, and test Euler's theorem