Das Paket numtheory

Die einzelnen Befehle

Faktoren einer natürlichen Zahl, insbesondere Primfaktoren

• ifactor(n) returns the complete integer factorization of n
• factorset(n) omputes the set of prime factors of its integer argument n.
• bigomega(n) computes the number of prime divisors of the integer n counted with multiplicity.
• divisors(n) computes the set of positive divisors of its integer argument n.
• tau(n) computes the number of positive divisors of n.
• sigma(n) compute the sum of the positive divisors of n.
  sigma[k](n) compute the sum of the kth power of positive divisors of n.
• mobius(n)
  The function mobius(n) gives the Möbius function of n. It returns 1, -1, or 0 depending on the factorization of n. Note that it returns 0 if and only if n has a square factor > 1
• isprime(n)
  liefert true falls n eine Primzahl ist, sonst false.
• issqrfree(n)
  liefert true falls n quadratfrei ist, sonst false.
• nthpow(m,n)
  The function nthpow will return (b)^n where b is the greatest natural number such that b^n divides m.

• nextprime(n)
  liefert die nächste Primzahl nach n.
• prevprime(n)
  liefert die nächst-kleinere Primzahl zu n.
• ithprime(n);
  liefert die n-te Primzahl.

• pi(n)
  liefert die Anzahl der Primzahlen kleiner oder gleich n

Spezielle Zahlen

• factorial(n)   oder auch     n!
  liefert n Fakultät.
• binomial(n,r) computes binomial coefficients.
  If the arguments are both non-negative integers with 0 ≤ r ≤ n, then binomial(n, r) = n!/r!/(n-r)!,
• fermat(n)
  returns the nth Fermat number 2^(2^n)+1, for n < 22.
• mersenne(n) computes the nth Mersenne prime. If the argument n is an integer then mersenne(n) will return 2^n-1 if 2^n-1 is known to be prime. Otherwise, if n is prime, but 2^n-1 is not determinably prime, then mersenne(n) will return FAIL. Finally, if n is composite it will return false
• safeprime(n)
  The function safeprime will compute the smallest safe prime that is greater than n. A safe prime is a number p such that p is prime and (p-1)/2 is prime.
• bernoulli(n)
  computes the nth Bernoulli number.
  Bernoulli numbers come from the coefficients in the Taylor expansion of x/(e^x - 1).
• euler(n)
  computes the nth Euler number.
  The nth Euler number E(n) is defined by the exponential generating function: 2/(exp(t)+exp(-t)) = sum(E(n)/n!*t^n, n = 0..infinity)
• fibonacci(n)
  computes the nth Fibonacci number F(n).

Kettenbrüche

• cfrac computes a regular or simple continued fraction expansion
• cfracpol computes simple continued fraction expansions for all real roots of a rational polynomial
• invcfrac
  convert a simple periodical continued fraction expansion to a quadratic surd
• nthconver
  the nth convergent of simple or regular continued fraction
• nthdenom
  the nth denominator of simple or regular continued fraction
• nthnumer
  the nth numerator of simple or regular continued fraction

Restklassenringe

• chrem(u, m) gives the Chinese Remainder Algorithm:
  If u is a list of integers, chrem(u, m) computes the unique positive integer a such that a mod m0 = u0, a mod m1 = u1, ..., a mod mn = un, and a < m0 m1 ... mn. The moduli m0, m1, ..., mn must be pairwise relatively prime.
  Beispiel: chrem([1,2,3],[3,10,7]) liefert die Zahl 52 (es ist 52 ≡ 1 (mod 3);   52 ≡ 2 (mod 10); und 52 ≡ 3 (mod 7).)
• mcombine
  Also a Chinese remainder calculation
• migcdex
  computes solutions to the modulo N extended GCD problem

• phi(n)
  The function phi will compute the totient function of n, which is the number of positive integers not exceeding n and relatively prime to n.
• invphi
  The function invphi(n) will return a increasing list of integers [m1, m2, ..., mk] such that phi(mi) = n for i from 1 to k

• order(n,m)
  The smallest integer i such that n^i = 1 (mod m) is returned.
  Dies ist also die Ordnung der Restklasse von n in der Einheitengruppe von Z/Zm.
• primroot(n)
  return the smallest primitive root of the number n, if possible, otherwise it returns FAIL.
  The integers that are relatively prime to n form a group of order phi(n) under multiplication (mod n). If this group is cyclic then a generator of the group is called a primitive root of n. (i.e. the order of primroot (n) is phi(n)).
  primroot(g,n)
  computes the first primitive root of n greater than g (if possible).
• pprimroot
  pseudo-primitve root: The function pprimroot(g, n) computes the next primitive root larger than g or, if n does not have primitive roots, computes a number which is not a root of order of any of the factors of phi(n).
• lambda
  Carmichael's lambda function. The size of the largest cyclic group generated by g^i (mod n) is given by lambda(n).

• imagunit will find a square root of -1 (mod n), if possible, otherwise it returns FAIL.
• msqrt The function msqrt will compute the square root of x (mod n). It finds an integer y such that y^2 = x (mod n) if possible, otherwise it returns FAIL
• mroot
  The function mroot computes the rth root of x (mod p). It finds an integer y such that y^r = x (mod p) if possible. Otherwise, it returns FAIL.
• rootsunity
  This function will calculate all the pth roots of unity mod r and return the result as an expression sequence
• mlog   or index
  The function mlog will compute the discrete logarithm (is also called the index) of x to the base a (mod n). It finds an integer y such that a^y = x (mod n) if possible, otherwise it returns FAIL.

• quadres
  checks if a number is a quadratic residue mod another
• legendre
  The legendre(a, p) function computes the Legendre symbol L(a/p) of a and p,
• jacobi
  The function jacobi will compute the Jacobi symbol J(a/b) of a and b

• mipolys
  The mipolys function computes the number of monic irreducible univariate polynomials of degree n over the finite field Z mod p, if the parameter m is not specified

Ringe algebraischer Zahlen

• sq2factor
  integer factorization in Z(sqrt(2))
• GIgcd = gcd of Gaussian integers
• factorEQ = integer factorization in Z(sqrt(d)) where Z(sqrt(d)) is a Euclidean ring
• cyclotomic
  cyclotomic(n, t) will return the nth cyclotomic polynomial in t
• integral_basis
  integral bases of algebraic number fields

Weiteres

• isolve
  For solving equations for integer solutions
• thue
  solve a Thue equation or inequality
• minkowski
  solve Minkowski's linear forms (homogeneous diophantine approximation)
• kronecker
  Inhomogeneous Diophantine approximation
• nearestp
  the nearby lattice point problem
• pdexpand
  compute the periodic expansion of a rational number
• sum2sqr
  returns the solutions of the sum of two squares problem.

Funktionen

• Zeta(z)
  Riemansche Zeta-Funktion
  The Zeta function is defined for Re(z)>1 by Zeta(z) = sum(1/i^z, i=1..infinity) and is extended to the rest of the complex plane (except for the point z=1) by analytic continuation. The point z=1 is a simple pole.
• GAMMA(z)
  The Gamma function is defined for Re(z)>0 by GAMMA(z) = int( exp(-t)*t^(z-1), t=0..infinity ) and is extended to the rest of the complex plane, less the non-positive integers, by analytic continuation. GAMMA has a simple pole at each of the points z=0,-1,-2,....

Links

• Einführung in Maple (Dietmar Henke)