% Copyright The Numerical Algorithms Group Limited 1992-94. All rights reserved.
% !! DO NOT MODIFY THIS FILE BY HAND !! Created by ht.awk.
\newcommand{\IntegerNumberTheoryFunctionsXmpTitle}{IntegerNumberTheoryFunctions}
\newcommand{\IntegerNumberTheoryFunctionsXmpNumber}{9.36}
%
% =====================================================================
\begin{page}{IntegerNumberTheoryFunctionsXmpPage}{9.36 IntegerNumberTheoryFunctions}
% =====================================================================
\beginscroll


The \spadtype{IntegerNumberTheoryFunctions} package contains a variety of
operations of interest to number theorists.
%-% \HDindex{number theory}{IntegerNumberTheoryFunctionsXmpPage}{9.36}{IntegerNumberTheoryFunctions}
Many of these operations deal with divisibility properties of integers.
(Recall that an integer \spad{a} divides an integer \spad{b} if there is
an integer \spad{c} such that \spad{b = a * c}.)

\xtc{
The operation \spadfunFrom{divisors}{IntegerNumberTheoryFunctions}
returns a list of the divisors of an integer.
}{
\spadpaste{div144 := divisors(144) \bound{div144}}
}
\xtc{
You can now compute the number of divisors of \spad{144} and the sum of
the divisors of \spad{144} by counting and summing the elements of the
list we just created.
}{
\spadpaste{\#(div144) \free{div144}}
}
\xtc{
}{
\spadpaste{reduce(+,div144) \free{div144}}
}

Of course, you can compute the number of divisors of an integer \spad{n},
usually denoted \spad{d(n)}, and the sum of the divisors of an integer
\spad{n}, usually denoted \spad{\texht{$\sigma$}{sigma}(n)},
%-% \HDindex{sigma@{$\sigma$}}{IntegerNumberTheoryFunctionsXmpPage}{9.36}{IntegerNumberTheoryFunctions}
without ever listing the divisors of \spad{n}.

\xtc{
In \Language{}, you can simply call the operations
\spadfunFrom{numberOfDivisors}{IntegerNumberTheoryFunctions} and
\spadfunFrom{sumOfDivisors}{IntegerNumberTheoryFunctions}.
}{
\spadpaste{numberOfDivisors(144)}
}
\xtc{
}{
\spadpaste{sumOfDivisors(144)}
}

The key is that \spad{d(n)} and
\spad{\texht{$\sigma$}{sigma}(n)}
are ``multiplicative functions.''
This means that when \spad{n} and \spad{m} are relatively prime, that is, when
\spad{n} and \spad{m} have no prime factor in common, then
\spad{d(nm) = d(n) d(m)} and
\spad{\texht{$\sigma$}{sigma}(nm) = \texht{$\sigma$}{sigma}(n)
\texht{$\sigma$}{sigma}(m)}.
Note that these functions are trivial to compute when \spad{n} is a prime
power and are computed for general \spad{n} from the prime factorization
of \spad{n}.
Other examples of multiplicative functions are
\spad{\texht{$\sigma_k$}{sigma_k}(n)}, the sum of the \eth{\spad{k}} powers of
the divisors of \spad{n} and \texht{$\varphi(n)$}{\spad{phi(n)}}, the
number of integers between 1 and \spad{n} which are prime to \spad{n}.
The corresponding \Language{} operations are called
\spadfunFrom{sumOfKthPowerDivisors}{IntegerNumberTheoryFunctions} and
\spadfunFrom{eulerPhi}{IntegerNumberTheoryFunctions}.
%-% \HDindex{phi@{$\varphi$}}{IntegerNumberTheoryFunctionsXmpPage}{9.36}{IntegerNumberTheoryFunctions}
%-% \HDindex{Euler!phi function@{$\varphi$ function}}{IntegerNumberTheoryFunctionsXmpPage}{9.36}{IntegerNumberTheoryFunctions}

An interesting function is \spad{\texht{$\mu$}{mu}(n)},
%-% \HDindex{mu@{$\mu$}}{IntegerNumberTheoryFunctionsXmpPage}{9.36}{IntegerNumberTheoryFunctions}
the \texht{M\"{o}bius $\mu$}{Moebius mu} function, defined
%-% \HDindex{Moebius@{M\"{o}bius}!mu function@{$\mu$ function}}{IntegerNumberTheoryFunctionsXmpPage}{9.36}{IntegerNumberTheoryFunctions}
as follows:
\spad{\texht{$\mu$}{mu}(1) = 1}, \spad{\texht{$\mu$}{mu}(n) = 0},
when \spad{n} is divisible by a
square, and
\spad{\texht{$\mu = {(-1)}^k$}{mu(n) = (-1) ** k}}, when \spad{n}
is the product of \spad{k} distinct primes.
The corresponding \Language{} operation is
\spadfunFrom{moebiusMu}{IntegerNumberTheoryFunctions}.
This function occurs in the following theorem:

\noindent
{\bf Theorem} (\texht{M\"{o}bius}{Moebius} Inversion Formula): \newline
%\texht{\begin{quotation}\noindent}{\newline\indent{5}}
Let \spad{f(n)} be a function on the positive integers and let \spad{F(n)}
be defined by
\texht{\narrowDisplay{F(n) = \sum_{d \mid n} f(n)}}{\spad{F(n) =}
sum of \spad{f(n)} over \spad{d | n}}
where the sum is taken over the positive divisors of \spad{n}.
Then the values of \spad{f(n)} can be recovered from the values of
\spad{F(n)}:
\texht{\narrowDisplay{f(n) = \sum_{d \mid n} \mu(n) F({{n}\over {d}})}}{\spad{f(n) =}
sum of \spad{mu(n) F(n/d)} over \spad{d | n},}
where again the sum is taken over the positive divisors of \spad{n}.

\xtc{
When \spad{f(n) = 1}, then \spad{F(n) = d(n)}.
Thus, if you sum \spad{\texht{$\mu$}{mu}(d) \texht{$\cdot$}{*} d(n/d)}
over the positive divisors
\spad{d} of \spad{n}, you should always get \spad{1}.
}{
\spadpaste{f1(n) == reduce(+,[moebiusMu(d) * numberOfDivisors(quo(n,d)) for d in divisors(n)]) \bound{f1}}
}
\xtc{
}{
\spadpaste{f1(200) \free{f1}}
}
\xtc{
}{
\spadpaste{f1(846) \free{f1}}
}
\xtc{
Similarly, when \spad{f(n) = n}, then \spad{F(n) = \texht{$\sigma$}{sigma}(n)}.
Thus, if you sum \spad{\texht{$\mu$}{mu}(d) \texht{$\cdot$}{*}
\texht{$\sigma$}{sigma}(n/d)} over the positive divisors
\spad{d} of \spad{n}, you should always get \spad{n}.
}{
\spadpaste{f2(n) == reduce(+,[moebiusMu(d) * sumOfDivisors(quo(n,d)) for d in divisors(n)]) \bound{f2}}
}
\xtc{
}{
\spadpaste{f2(200) \free{f2}}
}
\xtc{
}{
\spadpaste{f2(846) \free{f2}}
}


The Fibonacci numbers are defined by \spad{F(1) = F(2) = 1} and
%-% \HDindex{Fibonacci numbers}{IntegerNumberTheoryFunctionsXmpPage}{9.36}{IntegerNumberTheoryFunctions}
\spad{F(n) = F(n-1) + F(n-2)} for \spad{n = 3,4, ...}.
\xtc{
The operation \spadfunFrom{fibonacci}{IntegerNumberTheoryFunctions}
computes the \eth{\spad{n}} Fibonacci number.
}{
\spadpaste{fibonacci(25)}
}
\xtc{
}{
\spadpaste{[fibonacci(n) for n in 1..15]}
}
\xtc{
Fibonacci numbers can also be expressed as sums of binomial coefficients.
}{
\spadpaste{fib(n) == reduce(+,[binomial(n-1-k,k) for k in 0..quo(n-1,2)]) \bound{fib}}
}
\xtc{
}{
\spadpaste{fib(25) \free{fib}}
}
\xtc{
}{
\spadpaste{[fib(n) for n in 1..15] \free{fib}}
}

Quadratic symbols can be computed with the operations
\spadfunFrom{legendre}{IntegerNumberTheoryFunctions} and
\spadfunFrom{jacobi}{IntegerNumberTheoryFunctions}.
The Legendre symbol
%-% \HDindex{Legendre!symbol}{IntegerNumberTheoryFunctionsXmpPage}{9.36}{IntegerNumberTheoryFunctions}
\texht{$\left({a \over p}\right)$}{\spad{(a/p)}}
is defined for integers \spad{a} and
\spad{p} with \spad{p} an odd prime number.
By definition, \texht{$\left({a \over p}\right)$}{\spad{(a/p) = +1}},
when \spad{a} is a square \spad{(mod p)},
\texht{$\left({a \over p}\right)$}{\spad{(a/p) = -1}},
when \spad{a} is not a square \spad{(mod p)}, and
\texht{$\left({a \over p}\right)$}{\spad{(a/p) = 0}},
when \spad{a} is divisible by \spad{p}.
\xtc{
You compute \texht{$\left({a \over p}\right)$}{\spad{(a/p)}}
via the command \spad{legendre(a,p)}.
}{
\spadpaste{legendre(3,5)}
}
\xtc{
}{
\spadpaste{legendre(23,691)}
}
The Jacobi symbol \texht{$\left({a \over n}\right)$}{\spad{(a/n)}}
is the usual extension of the Legendre
symbol, where \spad{n} is an arbitrary integer.
The most important property of the Jacobi symbol is the following:
if \spad{K} is a quadratic field with discriminant \spad{d} and quadratic
character \texht{$\chi$}{\spad{chi}},
then \texht{$\chi$}{\spad{chi}}\spad{(n) = (d/n)}.
Thus, you can use the Jacobi symbol
%-% \HDindex{Jacobi symbol}{IntegerNumberTheoryFunctionsXmpPage}{9.36}{IntegerNumberTheoryFunctions}
to compute, say, the class numbers of
%-% \HDindex{class number}{IntegerNumberTheoryFunctionsXmpPage}{9.36}{IntegerNumberTheoryFunctions}
imaginary quadratic fields from a standard class number formula.
%-% \HDindex{field!imaginary quadratic}{IntegerNumberTheoryFunctionsXmpPage}{9.36}{IntegerNumberTheoryFunctions}
\xtc{
This function computes the class number of the imaginary
quadratic field with discriminant \spad{d}.
}{
\spadpaste{h(d) == quo(reduce(+, [jacobi(d,k) for k in 1..quo(-d, 2)]), 2 - jacobi(d,2)) \bound{h}}
}
\xtc{
}{
\spadpaste{h(-163) \free{h}}   
}
\xtc{
}{
\spadpaste{h(-499) \free{h}}   
}
\xtc{
}{
\spadpaste{h(-1832) \free{h}}  
}



\endscroll
\autobuttons
\end{page}
%