Number theory exercises using GAP

The GAP command to compute all the divisors of an integer $ n$ is DivisorsInt(n); For example, DivisorsInt(15); returns [1,3,5,15].

Exercise 1.11.1   Find all the positive divisors of $ 1234567$.

The remainder and quotient of $ n$ divided by $ m$ are the commands RemInt( n, m ); QuoInt( n, m );, respectively. For example, RemInt(155, 15 ); returns 5.

Exercise 1.11.2   Compute the remainder and quotient of dividing $ m=789$ into $ n=123456$.

GAP does not have a base $ m$ conversion directly. One must use it's p-adic numbers package to convert from decimal to base $ m$ and this only works when $ m=p$ is a prime. The command fam:=PurePadicNumberFamily(p,k); creates the data needed to work with base $ m$ notation, when $ m=p$ is a prime. The integer $ k$ indicates the number of $ m$-ary digits which will be used. The command PadicNumber(fam,a); returns the expansion of $ a$ in base $ m=p$ out to $ k$ places. For example, fam2:=PurePadicNumberFamily(2,6); and PadicNumber(fam2,14); returns 0.111(2) This is read least significant to most significant digits, left to right: the 0 is the $ 1$'s place, those to the right of the decimal point are the $ 2$'s place, $ 4$'s places, and so on. The $ 2$ in the parentheses is the base $ m=2$, so the output tells us $ 14=0\cdot 1 +1\cdot 2 +1\cdot 4 +1\cdot 8$.

Exercise 1.11.3   Convert (the decimal) $ 123456789$ to binary. Also, convert $ 10001001011$ from binary to decimal.

The greatest common divisor of $ m$ and $ n$ is given by GcdInt( m, n); . For example, GcdInt( 108,801); returns 9.

Exercise 1.11.4   Compute the gcd of $ 123456789$ and $ 987654321$.

To find $ x,y$ such that $ mx+ny=gcd(m,n)$, use the GAP command Gcdex( m,n);. For example, Gcdex( 108,801); returns
rec( gcd := 9, coeff1 := -37, coeff2 := 5, coeff3 := 89, coeff4 := -12 ), where $ x=$coeff1, $ y=$coeff2 .

Exercise 1.11.5   Compute the gcd $ d$ of $ 123456789$ and $ 987654321$ and find $ x,y$ such that $ 123456789x+ 987654321y=d$.

To find the least common divisor of $ m$ and $ n$, use the GAP command LcmInt( m, n); . For example, LcmInt( 155,15); returns 255 .

Exercise 1.11.6   Compute the gcd and lcm of $ 12345$ and $ 6789$.

The Euler totient function $ \phi(n)$ is given by the command Phi(n);. For example, Phi(2^{13}-1); returns 8190.

Exercise 1.11.7   Compute $ \phi(2^{15}-1 )$ and $ \phi(2^{17}-1 )$, then deduce whether or not $ 2^{15}-1$ and $ 2^{17}-1$ are prime.

The next prime after $ n$ is given by the command NextPrimeInt(n);. The $ n^{th}$ prime is given by the command Primes(n);. For example, NextPrimeInt(100); Primes(100); returns 101 and 541, respectively.

The prime factorization of $ n$ is given by the command FactorsInt(n); . For example, FactorsInt( 2^63 - 1 ); returns
[ 7, 7, 73, 127, 337, 92737, 649657 ] .

Exercise 1.11.8   Find the $ 150^{th}$ prime and test if $ 1234567$ is prime by finding its factorization.

Program the Lucas-Lehmer sequence $ v_1=4$, $ v_2=14$, .... $ v_n=v_{n-1}^2-2$, by typing 

lucaslehmer :=function(n)                          
 if n = 1 then return 4; fi;
 if 1 < n then  return lucaslehmer(n - 1)^2 - 2; fi;
 return 0;
end;

Exercise 1.11.9 (a)   Compute $ v_{22}\ {\rm mod}\, (2^{23}-1)$, $ v_{30}\ {\rm mod}\, (2^{31}-1)$, and $ v_{46}\ {\rm mod}\, (2^{47}-1)$. Determine if $ 2^{23}-1$, $ 2^{31}-1$, and $ 2^{47}-1$ are prime (using the test in Lemma 1.12.10).

(b) What is the largest prime you can find on your computer using this test?

(c) Rewrite the code so that the procedure computes $ v_1=4\ ({\rm mod}\ q)$ and $ v_n=v_{n-1}^2-2\ ({\rm mod}\ q)$.

(d) Find the smallest $ n$ for which your computer takes more than 1 minute (by your watch) to compute $ v_n$.

The Lucas-Perrin sequence

$\displaystyle 3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39, 51, 68, 90, 119, 158, 209, 277,..., $

is defined by the recurrence $ a_{n+3}=a_{n+1}+a_n$, $ a_0=3$, $ a_1=0$, $ a_2=2$. This is also called the Perrin sequence, named after R. Perrin who mentioned this sequence in a paper in 1899, though it was found earlier by Edouard Lucas in 1878, who gave the following result.

Lemma 1.11.10 (Lucas-Perrin)   If $ p$ is a prime then $ p\vert a_p$.

Program this sequence into GAP by typing 

lucasperrin:=function(n)     
 if n = 1 then return 0; fi;
 if n = 2 then return 2; fi;
 if n = 3 then return 3; fi;
 if n > 3 then return lucasperrin(n-2)+lucasperrin(n-3); fi;
 return -1;
end;

Exercise 1.11.11   Compute $ a_i$, for $ 1\leq i \leq 11$. Verify the Lucas-Perrin lemma for $ p=2,3,5,7,11$.

Exercise 1.11.12  

(a) Compute $ a_{47}$.

(b) What is the largest ``prime candidate'' you can find on your computer 1.10?

Question: Is $ a_n$ divisible by $ n$ if and only if $ n$ is prime?

If the answer was yes, this would be a very fast primality test. On the other hand, it is ``yes'' for all $ n$ up to 15000, as can be checked using GAP. (Exercise: Do this!) However, the answer is ``no''. Indeed, the smallest counterexample (discovered by D. Shanks and W. Adams [AS]) seems to be $ 271441=521^2$.

The Chinese remainder theorem commands give us the minimal solution $ x\geq 0$ of $ x\equiv a_1\ ({\rm mod}\ n_1)$, $ x\equiv a_2\ ({\rm mod}\ n_2)$, ..., $ x\equiv a_k\ ({\rm mod}\ n_k)$.

The command for the Chinese remainder theorem is
ChineseRem([n1,n2,...,nk],[a1,a2,...,ak]); . For example,
ChineseRem([5,7],[1,2]); returns 16.

Exercise 1.11.13   Solve $ x\equiv 2\ ({\rm mod}\ 3),\ x\equiv 1\ ({\rm mod}\ 4),\ x\equiv 3\ ({\rm mod}\ 5)$.

The multiplicative order of $ a$ mod $ m$ in GAP is given by OrderMod( a, m ); . For example, OrderMod(2,7); returns 3.

Exercise 1.11.14   Find

(a) the order of $ 10$ mod $ 17$,

(b) the order of $ 10$ mod $ 101$.

PowerMod( r, e, m ); returns the $ e^{th}$ power of $ r$ modulo $ m$.

Exercise 1.11.15   Verify the example: Let $ p=17$, $ q=19$, so $ \phi(n)=\phi(323)=288$. Let $ e=97$ (the public exponent), so $ d=193$ (the private exponent). Let $ m=100$ be the message. The ``cipher text'' is $ c=168$ since $ m^e=100^{97} \equiv 168 \ ({\rm mod}\ 323)$.

The primitive root mod $ m$ is given by PrimitiveRootMod(m); . The discrete log is given by LogMod( a, b,m); . For example, PrimitiveRootMod(7); and LogMod( 64, 5,97); returns 3 and 12, respectively.

Exercise 1.11.16  

(a) Find the discrete log of $ 11$ to base $ 5$ mod $ 97$, if it exists.

(b) Is $ 197$ a prime? Is $ 2$ a primitive root mod $ 197$? Find the discrete log of $ 91$ to base $ 2$ mod $ 197$, if it exists (ans: $ 44$),


David Joyner 2007-09-03