Number theory exercises using MAGMA

This section is very similar to §1.11 but applied to MAGMA as opposed to GAP.

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

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

The remainder and quotient of $n$ divided by $m$ is the MAGMA command Quotrem(n,m);. For example, Quotrem( 11, 2); returns 5 1.

Exercise 1.12.2   compute the remainder and quotient of dividing $m=789$ into $n=123456$.

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

MAGMA 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 Zp<p> := pAdicRing(m); creates the data needed to work with base $m$ notation, when $m=p$ is a prime. The integer $n$ indicates the number of $m$-ary digits which will be used. The commands r := Zp!a; Coefficients(r); returns the expansion of $a$ in base $m=p$ out to $k$ places. For example,
Zp<p> := pAdicRing(5);r := Zp!127;, Coefficients(r); returns
[ 2, 0, 0, 1 ] This is read least significant to most significant digits, left to right: the $2$ is the $1$'s place, those to the right of the decimal point are the $5$'s place, $25$'s places, and so on. The output tells us $127=2\cdot 1 +0\cdot 5 +0\cdot 25 +1\cdot 125$.

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

The greatest common divisor of $m$ and $n$ is given by
GreatestCommonDivisor(m, n); . For example, GreatestCommonDivisor(10005,50001); returns 3.

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

To find $x,y$ such that $mx+ny=gcd(m,n)$, use the GAP command XGCD([ m,n]);. For example, XGCD([108,801]); returns

Exercise 1.12.6   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 LCM([ m, n]); . For example, LCM([ 155,15]); returns 255 .

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

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

Exercise 1.12.8   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 NextPrime(n);. For example, NextPrimeInt(100); returns 101.

The prime factorization of $n$ is given by the command Factorization(n); . For example, Factorization(100); returns [ <2, 2>, <5, 2> ].

Exercise 1.12.9   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

function lucaslehmer(n)                                 
 if n eq 1 then return 4; end if;
 if 1 lt n then  return lucaslehmer(n - 1)^2 - 2; end if;
 return 0;
end function;

We turn to a method to test the primality of special numbers of the form $2^p-1$, where $p$ is a prime. The next result is included to illustrate the type of special methods known to test the primality of integers of special forms.

Lemma 1.12.10 (Lucas-D.H. Lehmer)   For $p>2$, $q=2^p-1$ is prime if $q\vert v_{p-1}$, where $v_1=4$ and $v_n=v_{n-1}^2-2$.

The proof is omitted. See [Br].

Note that we need not and should not compute $v_n$ directly, which grows very fast (in fact, it grows faster than $2^{1.9^n}$). For example, when testing for the primality of $q=2^{31}-1$, we do not compute $v_{30}$ and see if $q\vert v_{30}$; rather we compute $v_{30}\ ({\rm mod}\, q)$ and see if it is zero. The point is that the new sequence

$$\overline{v}_1=4\ ({\rm mod}\ q), \ \ \ \ \overline{v}_n=\overline{v}_{n-1}^2-2\ ({\rm mod}\ q),$$

can be computed rather quickly on a computer, since the terms are always less than or equal to $q$. On the other hand, the sequence $v_n$ is rather slow to compute (due to their size), when $n$ is large.

Lucas-Lehmer test: Let $q=2^p-1$, where $p$ is a prime. For $p>2$, if $\overline{v}_{p-1}=0 \ ({\rm mod}\ q)$, then $q$ is a prime.

Exercise 1.12.11 (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

$$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.12.12 (Lucas-Perrin)   If $p$ is a prime then $p\vert a_p$.

Program this sequence into MAGMA by typing

function lucasperrin(n)                                 
 if n eq 1 then return 0; end if;
 if n eq 2 then return 2; end if;
 if n eq 3 then return 3; end if;
 if 1 lt n then  return lucasperrin(n - 2) + lucasperrin(n - 3); end if;
 return -1;
end function;

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

Exercise 1.12.14  

(a) Compute $a_{47}$.

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

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 MAGMA. (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
CRT([a1,a2,...,ak],[n1,n2,...,nk]);. For example, CRT([1,2],[5,7]); returns 16 .

Exercise 1.12.15   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 MAGMA is given by the commands R := ResidueClassRing(m); Order(R!a); . For example,
R := ResidueClassRing(17); Order(R!11); returns 16.

Exercise 1.12.16   Find

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

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

R := ResidueClassRing(m); r:=R!a; r^e; returns the $e^{th}$ power of $r$ modulo $m$.

Exercise 1.12.17   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 PrimitiveRoot(m);. The discrete log is given by Log(GF(m)!a,GF(m)!b); ($m$ prime). For example, PrimitiveRootMod(7); and LogMod( 64, 5,97); returns 3 and 12, respectively.

Exercise 1.12.18  

(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$),

In MAGMA, type ContinuedFraction(r);, where $r$ is real, to get the continued fraction of $r$. For example, ContinuedFraction(Sqrt(2)); returns [ 1, 2, 2, ...].

Exercise 1.12.19   Find the continued fraction expansions of the golden ratio $(1+\sqrt{5})/2$, and make a conjecture as to what the nth convergents are.