\documentclass[11pt]{article}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}

\usepackage{amsmath,amscd,amsthm,amsfonts}

\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem{exer}{Exercise}
\newtheorem{exam}{Example}
\theoremstyle{plain}
\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}
\newtheorem{cor}{Corollary}
\newtheorem{prop}{Proposition}

\renewcommand{\P}{\texttt{PARI }}
\renewcommand{\k}{\kappa}
\renewcommand{\H}{\mathbb{H}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\A}{\mathbb{A}}
\newcommand{\G}[1]{\Gamma(#1)}
\newcommand{\GO}[1]{\Gamma_0(#1)}
\newcommand{\Gb}[1]{\bar{\Gamma}(#1)}
\newcommand{\SL}[1]{\mathbf{SL}_2(#1)}
\newcommand{\PSL}[1]{\mathbf{PSL}_2(#1)}
\newcommand{\GL}[1]{\mathbf{GL}_2(#1)}
\newcommand{\V}[2]{\bigl[\begin{smallmatrix}#1 \\#2\end{smallmatrix}\bigr]}
\newcommand{\z}{\zeta}
\renewcommand{\b}{\backslash}
\renewcommand{\hom}[2]{\mathrm{Hom}_k\left(#1,#2\right)}
\DeclareMathOperator{\deck}{Deck}
\DeclareMathOperator{\aut}{Aut}
\DeclareMathOperator{\id}{id}
\DeclareMathOperator{\gal}{Gal}
\DeclareMathOperator{\ord}{ord}
\DeclareMathOperator{\sol}{Sol}
\DeclareMathOperator{\rad}{rad}
\title{An Introduction to \texttt{GP/PARI}}
\author{Bryden Cais}
\begin{document}
\maketitle

\section{What is \P?}

In brief, \P is a sophisticated calculator.  What makes it different from other computation packages (like \texttt{MAPLE, MATHEMATICA, MATLAB} etc.
is that \P was designed by Number Theorists and professional mathematicians, not by entrepreneurs and engineers.  Why should this matter?
For starters, \P has a lot of built in functions that are really useful to number theorists that some of the other programs either don't have
at all or have implemented in a cumbersome manner (I am thinking, for example, of \texttt{PARI}'s ability to work with $p$-adic numbers).  More importantly,though,
is that one gets the impression that \P ``thinks'' like a mathematician.  For example, when you work with fractions, \P keeps them as
quotients of integers, rather than expanding in decimal notation (unless you tell it to).  But rather than give you more examples, let's
dive right in and see \P at work.

\section{Starting, Stopping and Entering Input}

How you start \P depends, of course, on what machine you are running it on.  For a \texttt{UNIX} box, like we are using,
the command (at the usual command prompt) is \texttt{gp} or \texttt{gp-stat}.  Once \P has started up, it will give you its own prompt,
something like \texttt{gp>} or \texttt{?}.  To quit \P type \verb$\q$.  All the usual arithmetic operations work just fine: for example,
try
\begin{verbatim}
    567+129
\end{verbatim}
and
\begin{verbatim}
    121*1729
\end{verbatim}
Remenber to hit the enter key after you have finished typing your input and want \P to start processing.  Let's try division.  Input
\begin{verbatim}
    1728/156
\end{verbatim}
Cool, \P automatically reduces fractions to lowest common terms.  You might try adding two fractions, like
\begin{verbatim}
    567/129+144/13
\end{verbatim}
Again, we get the fraction in reduced form.  What if you wanted it as a decimal expansion?  The way to tell \P that you are thinking
in decimals is to put a decimal point after the numbers you enter.  For example,
\begin{verbatim}
    567./129
\end{verbatim}
or
\begin{verbatim}
    567/129.
\end{verbatim}
both produce
\begin{verbatim}
    4.395348837209302325581395348
\end{verbatim}
If you want more precision, thats easy; just input \verb$\p 50$ for 50 places of accuracy, or \verb$\p 100$ for 100 and so on.
Try
\begin{verbatim}
    exp(Pi*sqrt(163))
\end{verbatim}
Notice that since \P is case sensitive, this is not the same thing as \verb$Exp(Pi*sqrt(163))$ or \verb$exp(pi*sqrt(163))$ etc., so be careful
to get the cases right.  What is going on?  It looks like $e^{\pi\sqrt{163}}$ is nearly an integer.  This surely cannot be.
To get more accuracy, type \verb$\p 100$ and try again.  Sure enough, its clear that $e^{\pi\sqrt{163}}$ is not an integer.  But why so close?
Stick with number theory long enough and you'll find out; the connections are deep and startling.
OK, enough with the basics, lets move on.

\section{Number Theory}

Although \P has a lot of mathematical functionality, we will be primarily interested in its number theory functions.
Input \verb$?$ and observe that \P gives you a list of help topics.  Now input \verb$?4$.  \P now lists all of the number theory
related functions; to find out about a specific one, input a \verb$?$ followed by the name.  Try it.
Let's take a closer look at some of the most useful functions for our purposes.

\subsection{factor}

    Clearly a useful command.  Try
    \begin{verbatim}
        factor(144169225289)
    \end{verbatim}
    \P gives the output
    \begin{verbatim}
        [40163 1]
        [3589603 1].
    \end{verbatim}
    This is a two by two matrix.  In general, the output of \verb$factor(n)$ will be a $r\times 2$ matrix, with
    the $r$ factors of $n$ being listed in the first column, and their corresponding multiplicities in the
    second column.  The above matrix tells us that
    $$144169225289=40163\cdot 3589603$$ and that both factors are prime.  Try some more examples to get a feel for factoring integes.
    Just so you know, factor can factor other things, like polynomials over $\Q$.  Try it.

\subsection{factormod, Mod, lift}

    This little function will factor a polynomial $f(x)$ modulo a prime $p$.  For example, if we want to
    factor $x^3+3x+7$ modulo $11$, we input
    \begin{verbatim}
        factormod(x^3+3*x+7,11)
    \end{verbatim}
    and \P returns
    \begin{verbatim}
        [Mod(1, 11)*x + Mod(10, 11) 1]
        [Mod(1, 11)*x^2 + Mod(1, 11)*x + Mod(4, 11) 1].
    \end{verbatim}
    Yikes!  What does this mean?  Those \verb$Mod$'s are just saying that the first component is being considered
    modulo the second.  For example, \verb$x=Mod(7,23)$ considers $x$ as an integer modulo $23$.  Observe that
    \verb$Mod(7,23)=\Mod(30,23)=Mod(37,23)$ etc.
    To get rid of those annoying \verb$Mod$'s, input \verb$lift(%)$
    (here, the \% symbol refers to the last output. Similarly, $\%k$ refers to $k$ outputs ago).
    Then \P returns the more sensible result
    \begin{verbatim}
        [x + 10 1]
        [x^2 + x + 4 1],
    \end{verbatim}
    telling us that
    $$x^3+3x+7\equiv(x+10)(x^2+x+4)\mod 11.$$
    \verb$Mod$'s aren't all bad, though, as they can be very useful for doing arithmetic
    mod $n$.  For example, if you want to determine the inverse of $23$ modulu 58, just
    input \verb$Mod(1/23,58)$ to find that the inverse is $53$.  \verb$Mod$ also works with polynomials.
    We'll explore this later.

\subsection{chinese}

        This is an implementation of the chinese remainder theorem.  Let \verb$x=Mod(a,m)$ and \verb$y=Mod(b,n)$
        be integers mod $m,n$ respectively.  Then \verb$chinese(x,y)$ gives an integer modulo $mn$ whose reduction
        mod $m$ is $a$ and mod $n$ is $b$ (if the system can be solved).  Let's try an example.  Input
        \begin{verbatim}
            x=Mod(7,23)
            y=Mod(9,54)
            chinese(x,y).
        \end{verbatim}
        \P gives \verb$Mod(927,1242)$.  We can check ourselves.  Observe that
        \verb$fcator(1242)$ gives
        \begin{verbatim}
        [23 1]
        [54 1],
        \end{verbatim} as expected, and
        \verb$Mod(927,23)$ and \verb$Mod(927,54)$ give $7$ and $9$ respectively.  What happens if the moduli are not relatively
        prime?

\subsection{gcd}

        A simple function that gives the greatest common divisor of two integers.  For example, input
        \begin{verbatim}
            gcd(123456789,987654321)
        \end{verbatim}
        to find that these two integers have GCD $9$ (of course, you knew a priori that the two were divisible by $9$, right?)

\subsection{bezout}

        This function is an extension of \verb$gcd$ in that given integers $m,n$ it solves the linear diophantine
        equation
        $$mx+ny=\gcd(m,n)$$
        for integers $x,y$.  Moreover, it gives the ``smallest'' (in an appropriate sense) solution.  For example,
        input
        \begin{verbatim}
            bezout(25678,166784)
        \end{verbatim}
        \P gives us
        \begin{verbatim}
            [-37289, 5741, 2].
        \end{verbatim}
        The first number is the coefficient of $25678$, the second is the coefficient of $166784$ and the last is $\gcd(25678,166784)$.
        \P is telling us that
        $$25678(-37289)+166784(5741)=2.$$  Can you find all solutions to this linear diophantine equation?
        The function \verb$bezout$ also works with polynomials.  Play with this if you like, and make sure you think about
        why the $\gcd$ of two polynomials is a well defined object.

\subsection{lcm}

        I'll bet you can guess what this does.  Try it.

\subsection{isprime}

        This function takes an integer input and returns $0$ if the input is composite and $1$ if it is prime.
        For example,
        \begin{verbatim}
            isprime(257)
            isprime(256)
        \end{verbatim}
        return $1,0$ respectively.

\subsection{nextprime,prime}

        The command \verb$nextprime(x)$ gives the smallest prime bigger than or equal to $x$.  For example,
        \begin{verbatim}
            nextprime(Pi)
            nextprime(2346)
        \end{verbatim}
        give $5,2347$ respectively.
        In a similar manner, \verb$prime(n)$ gives the $n^{\text{th}}$ prime number.

\subsection{eulerphi}

        This is just Euler's ``totient'' function.  Incidentially, one reference \cite{web} explains
        \begin{quote}
        Euler's generalization of the Fermat's Little Theorem depends on a function which indeed was invented by Euler (1707-1783)
        but named by J.J.Sylvester (1814-1897) in 1883. I never saw an authoritative explanation for the name totient he has given
        the function. In Sylvestor's opinion mathematics is essentially about seeing ``differences in similarity, similarity in difference.''
         The word totient rhymes with quotient and the function has to do with division but in an unusual way.
         (Scott Brodie brougt to my attention that the Oxford English Dictionary brings up the latin root tot for adding up, total.
         Tot has also the meaning (of unkown origin) of a small child or a small drink. It would be very much in the spirit of the above
         maxim to use the word with two so different meanings. You could expect this from Sylvester whom E.T. Bell has christened hothead.)
        \end{quote}
        Hm, OK.  At any rate, we input
        \begin{verbatim}
            eulerphi(345)
        \end{verbatim}
        to find that there are 176 units modulo 345.

\subsection{znprimroot}

        It is an important theorem that the group of units modulo $n$ is cyclic if and only if $n=p,p^n$ or $2p^n$
        where $p$ is prime.  This means that there is one unit $g$ called a \textit{primitive root} whose
        successive powers give all the units modulo $n$.  Let's try it for $n=13$.
        We input
        \begin{verbatim}
            znprimroot(13)
        \end{verbatim}
        and get
        \begin{verbatim}
            Mod(2,13)
        \end{verbatim}
        Now lets make a little table.  Type \verb$?vector$ to fin out how the \verb$vector$ command works and what it does.
        Once you understand this, input
        \begin{verbatim}
            vector(12,n,Mod(2^n,13)).
        \end{verbatim}
        \P gives some expression with lots of \verb$Mod$'s in it, so lift the result (using \verb$lift$) to obtain the vector
        \begin{verbatim}
            [2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, 1],
        \end{verbatim}
        which clearly contains all the units modulo $13$.

\subsection{znlog}

        Continuing with our example above, suppose that you know that $g$ is a primitive root modulo $n$ and you
        have some unit $u$ modulo $n$ and you want to know what power of $g$ gives you $u$.  This is the purpose
        of the function \verb$znlog$.  For example, input
        \begin{verbatim}
            g=znprimroot(13)
            znlog(5,g)
        \end{verbatim}
        to find that
        $$2^9\equiv 5\mod 13$$ as you might as well check using \verb$Mod(2^9,5)$.

\subsection{znorder}

        Still working in the unit group modulo $n$, this function gives you the \textit{order} of $u$ modulo $n$
        for any unit $u$.  This is the smallest integer $k$ such that
        $$u^k\equiv 1\mod n.$$  (Why should such an integer always exist?)  Be sure to input $u$ in the form
        \verb$Mod(u,n)$ to tell \P that we are working modulo $n$.
        For example,
        \begin{verbatim}
            znorder(Mod(2,29))
        \end{verbatim}
        returns $28$, which incidentally tells us that $2$ is a primitive root modulo $29$.

\section{Obtaining \P}

        You can get \P as an executable to install on your MAC or PC.  The website is:
        \begin{quote}
        http://www.parigp-home.de/
        \end{quote}
        Make sure to obtain the manuals, tutorial, and user's guide as well as these are invaluable references.

\section{Exercises}

\begin{enumerate}
    \item Factor $50260389661$.

    \item Factor $x^p-x$ modulo $p$.  Is this surprising?

    \item Find all solutions to the linear diophantine equation
    $$56752875 x+91796391 y=\gcd(56752875,91796391).$$

    \item Solve the system of equations
    $$x\equiv i^2\mod p_i$$ where $p_i$ is the $i^{\text{th}}$ prime and
    $1\leq i\leq 20$.
    \textbf{Hint:} Lookup the function \verb$if$ and write a recursive function.  If you write any
    more than one line of code for this, you're thinking along the wrong lines.

    \item Make a table of values of $\varphi(n)$, Euler's function, for $n<50$.
    \textbf{Hint:} use the \verb$vector$ function.  Do you notice any patterns?
    If not, make a list of the factorization of $n$ and of $\varphi(n)$
    for $n<50$.  Now do you notice anything?

    \item Can you figure out what
    \begin{verbatim}
        vector(20,n,sum(j=1,n,if(lift(Mod(n,j))==0,eulerphi(j),0)))
    \end{verbatim}
    does?  It might help to look up the syntax of \verb$if$ and \verb$sum$.  Any conjectures?  Proofs?

    \item What is the sum of the reciprocals of the first $40000$ primes?  Do you think this sum will converge or diverge?
    \textbf{Hint:} it might help to look at the syntax for the sum above, and to use the \verb$isprime$ function.  If
    you want to be really slick and efficient, you shouldn't do this, of course, and there is a better way using \verb$prime$.
    Can you figure out how?

    \item What proportion of the first $100$ primes have $2$ as a primitive root?  How about the first $1000,10000,40000$
    primes?  Can you make a bold conjecture?

\end{enumerate}

\begin{thebibliography}{3}
    \bibitem{web} http://www.cut-the-knot.com/blue/Euler.shtml
\end{thebibliography}

\end{document}