Elementare ZahlentheorieL

Software: MAPLE

Aufruf von MAPLE

Auf den Unix-Rechnern der Fakultät gibt man ein xmaple.
Bei den Windows-Rechnern im Rechenzentrum verwendet man entweder das enstsprechende Icon (ein Ahornblatt mit der Versionsnummer - jetzt die Nummer 10), oder Start - Programme.

Allgemeine Befehle

Funktionsgraphen

Primzahlen, Primfaktorzerlegung

Man gibt ein:
> ifactor(24);
dies liefert die Primfaktorzerlegung einer Zahl, hier der Zahl 24,
Antwort in diesem Fall: (2)³(3)

Wie üblich sagt das Semikolon ; hinter dem Befehl ifactor(m) dem Rechner, dass dieser Befehl nun ausgef
Schreibt man statt des Semikolons einen Doppelpunkt : , so wird das Ergebnis berechnet, aber nicht ausgedruckt.

Für die meisten zahlentheoretischen Funktionen und Algorithmen muss man zuerst das Zahlentheorie-Paket numtheory aufrufen, dies erfolgt durch den Befehl:

with(numtheory): oder auch durch
with(numtheory);

Danach stehen viele Befehle zur Verfügung! Zum Beispiel:

The function pi(n) computes the number of prime numbers less than or equal to the given integer n
ithprime(n)
Dies liefert die n-te Primzahl.
The function phi(n) will compute the totient function of n, which is the number of positive integers not exceeding n and relatively prime to n.

Rechnen mit ganzen Zahlen

Größter gemeinsamer Teiler (ggT)
igcd (24, 36);
Antwort: 12
Kleinstes gemeinsames Vielfaches (kgV)
ilcm (24, 36);
Antwort: 72
Ganzzahliger Quotient zweier ganzer Zahlen
iquo (25, 7);
Antwort: 3
Rest der Division zweier ganzer Zahlen
irem (17, 5);
Antwort: 2
floor(n) - greatest integer less than or equal to a number
ceil(n) - smallest integer greater than or equal to a number
igcdex(a,b,'s','t')
liefert den ggT g der Zahlen a,b und speichert zusätzlich als s und t Zahlen mit g = sa + tb (Bezout'sche Gleichung).

For-To-Do-Schleife

For-To-Do-Schleife:

> s:=5; for i to 4 do s:=s+i od;

s:=5 s:=6 s:=8 s:=11 s:=15

In Maple 10 funktioniert die mehrzeilige Ausgabe nur, wenn man im Worksheet-Modus ist.
Gegebenenfalls muss man unter File New ein neues Arbeitsblatt aufrufen, und dabei Worksheet Modus anklicken.

Noch ein Beispiel:
> s:= 5: for i from 3 to 4 do s:= s + i od: s;

12 Hier wird zu s = 5 zuerst 3, dann 4 addiert; die Zwischenergebnisse werden nicht ausgedruckt
(wegen der Verwendung des Doppelpunkts : nach od ). Ausgedruckt wird nur das Endergebnis s = 12.

Weitere Schleifen

While-Schleife
> k:= 7: i:= 0; while (i < 3) do i:= i + 1; od; i:=0
i:=1
i:=2
i:=3
If-Then-Else
> k:= 7: if k = 3 then text:= "k gleich 3" else text:= "k ungleich 3" fi: text; "k ungleich 3"

Das Paket `numtheory`

`bigomega`	`cfrac`	`cfracpol`	`cyclotomic`	`divisors`
`factorEQ`	`factorset`	`fermat`	`GIgcd`	`imagunit`
`index`	`integral_basis`	`invcfrac`	`invphi`	`issqrfree`
`jacobi`	`kronecker`	`lambda`	`legendre`	`mcombine`
`mersenne`	`migcdex`	`minkowski`	`mipolys`	`mlog`
`mobius`	`mroot`	`msqrt`	`nearestp`	`nthconver`
`nthdenom`	`nthnumer`	`nthpow`	`order`	`pdexpand`
`phi`	`pi`	`pprimroot`	`primroot`	`quadres`
`rootsunity`	`safeprime`	`sigma`	`sq2factor`	`sum2sqr`
`tau`	`thue`

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.
issqfree(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,....