This is documentation for Mathematica 4, which was
based on an earlier version of the Wolfram Language.
View current documentation (Version 11.1)

 Documentation /  Mathematica /  Das Mathematica Buch /  Höhere Mathematik in Mathematica /  Mathematische Funktionen /

PseudozufallszahlenKombinatorische Funktionen

3.2.4 Ganzzahlige und zahlentheoretische Funktionen

Einige ganzzahlige Funktionen

Der Rest bei der Divison von durch .

In[1]:= Mod[17, 3]

Out[1]=

Der ganzzahlige Teil von .

In[2]:= Quotient[17, 3]

Out[2]=

Mod funktioniert auch mit reellen Zahlen.

In[3]:= Mod[5.6, 1.2]

Out[3]=

Das Ergebnis von Mod hat immer dasselbe Vorzeichen wie das zweite Argument.

In[4]:= Mod[-5.6, 1.2]

Out[4]=

Für beliebige ganze Zahlen a und b gilt stets, daß b*Quotient[a, b] + Mod[a, b] gleich a ist.

Ganzzahlige Reste mit Versatz

Insbesondere wenn man mit Mod Indizes für Teile von Objekten erhalten will, ist es häufig angemessen, einen Versatz zu spezifizieren.

So wird im Grunde der 18. Teil der Liste herausgezogen, wobei die Liste als zyklisch behandelt wird.

In[5]:= Part[{a, b, c}, Mod[18, 3, 1]]

Out[5]=

Die Funktion größter gemeinsamer Teiler GCD[, , ... ] liefert die größte ganze Zahl, die alle ohne Rest teilt. Wenn Sie einen Quotienten zweier ganzer Zahlen eingeben, benutzt Mathematica tatsächlich GCD, um gemeinsame Faktoren zu entfernen und eine rationale Zahl in kleinsten Termen anzugeben.

Die Funktion kleinstes gemeinsames Vielfaches LCM[, , ... ] liefert die kleinste ganze Zahl, die alle Faktoren von jedem der enthält.

Die größte ganze Zahl, die sowohl 24 als auch 15 teilt, ist 3.

In[6]:= GCD[24, 15]

Out[6]=

Das Kronecker-Delta oder Kronecker-Symbol KroneckerDelta[, , ... ] ist gleich 1, wenn alle gleich sind, und es ist sonst gleich 0. kann als total symmetrischer Tensor angesehen werden.

Dies liefert einen total symmetrischen Tensor mit Rang 3.

In[7]:= Array[KroneckerDelta, {3, 3, 3}]

Out[7]=

Ganzzahlige Faktorisierung und verwandte Funktionen

Dies liefert die Faktoren von 24 als und . Das erste Element jeder Liste ist der Faktor, das zweite sein Exponent.

In[8]:= FactorInteger[24]

Out[8]=

Hier sind die Faktoren einer größeren ganzen Zahl.

In[9]:= FactorInteger[111111111111111111]

Out[9]=

Sie sollten bedenken, daß die Faktorzerlegung von ganzen Zahlen allgemein als ein fundamental schwieriges mathematisches Berechnungsproblem anerkannt ist. Folglich ist es leicht möglich, eine ganze Zahl einzutippen, die Mathematica erst in einer astronomischen Zeit in Faktoren zerlegen kann. Solange die ganzen Zahlen, die Sie eingeben, weniger als etwa 20 Stellen lang sind, sollte FactorInteger keine Probleme haben. Jedoch nur in speziellen Fällen wird die Funktion mit viel längeren Zahlen umgehen können. (Sie können einige Faktorisierungen beschleunigen, indem Sie die Option FactorComplete->False setzen, so daß FactorInteger[n] versucht, nur einfache Faktoren aus n herauszuziehen.)

Hier ist eine ziemlich lange ganze Zahl.

In[10]:= 30!

Out[10]=

Mathematica kann diese ganze Zahl leicht faktorisieren.

In[11]:= FactorInteger[%]

Out[11]=

Obwohl Mathematica möglicherweise nicht in der Lage ist, eine große ganze Zahl zu faktorisieren, kann es oft noch testen, ob die ganze Zahl eine Primzahl ist oder nicht. Außerdem verfügt Mathematica über eine schnelle Möglichkeit, die k-te Primzahl zu finden.

Es kann oft sehr viel schneller getestet werden, ob eine Zahl eine Primzahl ist, als sie zu faktorisieren.

In[12]:= PrimeQ[234242423]

Out[12]=

Hier ist ein Diagramm der ersten 100 Primzahlen.

In[13]:= ListPlot[ Table[ Prime[n], {n, 100} ] ]

Out[13]=

Dies ist die millionste Primzahl.

In[14]:= Prime[1000000]

Out[14]=

Besonders in der Zahlentheorie ist es oft wichtiger, die Verteilung der Primzahlen zu kennen, als ihre tatsächlichen Werte. Die Funktion PrimePi[x] liefert die Anzahl der Primzahlen , die kleiner oder gleich sind.

Dies liefert die Anzahl der Primzahlen kleiner als eine Milliarde.

In[15]:= PrimePi[10^9]

Out[15]=

In der Voreinstellung erlaubt FactorInteger nur ganze reelle Zahlen. Wenn Sie aber die Option GaussianIntegers -> True setzen, arbeitet die Funktion auch mit ganzen Gaußschen Zahlen. Das sind komplexe Zahlen mit ganzzahligen Real- und Imaginärteilen. Genauso wie die Faktorzerlegung mit reellen Primzahlen eindeutig ausführbar ist, ist sie es mit Gaußschen Primzahlen. Trotzdem gibt es gewisse potentielle Zweideutigkeiten bei der Auswahl der Gaußschen Primzahlen. In Mathematica werden sie stets, bis auf einen möglichen Anfangsfaktor von oder , so gewählt, daß sie positive Realteile und nichtnegative Imaginärteile haben.

Über den ganzen Gaußschen Zahlen kann 2 in faktorisiert werden.

In[16]:= FactorInteger[2, GaussianIntegers -> True]

Out[16]=

Hier sind die Faktoren einer ganzen Gaußschen Zahl.

In[17]:= FactorInteger[111 + 78 I, GaussianIntegers -> True]

Out[17]=

Einige zahlentheoretische Funktionen

Die Modulopotenz-Funktion PowerMod[a, b, n] liefert dieselben Ergebnisse wie Mod[a^b, n] für . PowerMod ist jedoch wesentlich effizienter, da es vermeidet, die vollständige Form von a^b zu erzeugen.

Mit PowerMod können Sie nicht nur positive Modulopotenzen, sondern auch Moduloinverse finden. Für negative b ergibt PowerMod[a, b, n], falls möglich, eine ganze Zahl , so daß gilt. (Wenn eine derartige ganze Zahl existiert, ist sie modulo eindeutig.) Wenn keine solche ganze Zahl existiert, läßt Mathematica PowerMod unevaluiert.

PowerMod ist äquivalent zur Benutzung von Power und dann von Mod, ist aber wesentlich effizienter.

In[18]:= PowerMod[2, 13451, 3]

Out[18]=

Dies liefert die modulare Inverse (Moduloinverse) von 3 modulo 7.

In[19]:= PowerMod[3, -1, 7]

Out[19]=

Multiplikation der Inversen mit 3 modulo 7 ergibt, wie erwartet, 1.

In[20]:= Mod[3 %, 7]

Out[20]=

Die Eulersche Funktion liefert die Anzahl der ganzen Zahlen kleiner als , die zu teilerfremd sind. Eine wichtige Beziehung (Kleiner Fermatscher Satz) ist, daß für alle gilt, die zu teilerfremd sind.

Die Möbiussche Funktion ist nach Definition , wenn ein Produkt von verschiedenen Primzahlen ist und , wenn einen quadrierten Faktor (ungleich 1) enthält. Eine wichtige Beziehung ist die Möbiussche Umkehrformel, die besagt, daß mit für alle auch gilt, wobei die Summe über alle positiven ganzen Zahlen läuft, die teilen.

Die Teiler-Funktion ist die Summe der -ten Potenzen der Teiler von . Die Funktion liefert die Gesamtzahl der Teiler von und wird oft mit bezeichnet. Die Funktion ist gleich der Summe der Teiler von und wird oft mit bezeichnet.

Für Primzahlen ist .

In[21]:= EulerPhi[17]

Out[21]=

Das Ergebnis ist 1, wie es durch den kleinen Fermatschen Satz garantiert wird.

In[22]:= PowerMod[3, %, 17]

Out[22]=

Dies liefert eine Liste aller Teiler von 24.

In[23]:= Divisors[24]

Out[23]=

liefert die Gesamtzahl der verschiedenen Teiler von 24.

In[24]:= DivisorSigma[0, 24]

Out[24]=

Das Jacobi-Symbol JacobiSymbol[n, m] reduziert sich zum Legendre-Symbol , wenn eine ungerade Primzahl ist. Das Legendre-Symbol ist gleich Null, wenn durch teilbar ist, ansonsten ist es gleich , wenn ein quadratischer Rest modulo der Primzahl ist, und sonst . Eine ganze Zahl , die zu teilerfremd ist, heißt ein quadratischer Rest modulo , wenn eine ganze Zahl existiert, so daß gilt. Das vollständige Jacobi-Symbol ist ein Produkt der Legendre-Symbole für jeden der Primfaktoren , so daß ist.

Der erweiterte ggT ExtendedGCD[m, n] liefert eine Liste g, r, s, wobei der größte gemeinsame Teiler von und ist; und sind ganze Zahlen, so daß ist. Der erweiterte ggT ist wichtig beim Bestimmen ganzzahliger Lösungen für lineare diophantische Gleichungen.

Die erste Zahl in der Liste ist der ggT von 105 und 196.

In[25]:= ExtendedGCD[105, 196]

Out[25]=

Das zweite Zahlenpaar erfüllt die Gleichung .

In[26]:= -13 105 + 7 196

Out[26]=

Die multiplikative Ordnungsfunktion MultiplicativeOrder[k, n] liefert die kleinste ganze Zahl , für die gilt. Die Funktion ist zuweilen auch als Index oder diskreter Logarithmus von bekannt. Die Schreibweise wird gelegentlich verwendet.

Die verallgemeinerte multiplikative Ordnungsfunktion MultiplicativeOrder[k, n, , , ... ] liefert die kleinste ganze Zahl , für die für jedes gilt. MultiplicativeOrder[k, n, -1, 1] ist zuweilen auch als die Subordnungsfunktion von modulo bekannt, die als geschrieben wird.

Die Carmichael-Funktion oder der kleinste universelle Exponent liefert die kleinste ganze Zahl , für die für alle jene ganzen Zahlen gilt, die relativ prim (teilerfremd) zu sind.

Die Gitterreduktionsfunktion LatticeReduce[, , ... ] wird in mehreren Arten moderner Algorithmen verwendet. Die Grundidee besteht darin, die ganzzahligen Vektoren als Definition eines mathematischen Gitters zu betrachten. Jeder Vektor für die Darstellung eines Punktes im Gitter kann als Linearkombination in der Form geschrieben werden, wobei die ganze Zahlen sind. Es gibt viele Möglichkeiten, in einem bestimmten Gitter die „Basisvektoren" auszuwählen. LatticeReduce findet nun für das Gitter eine reduzierte Menge von Basisvektoren mit gewissen speziellen Eigenschaften.

Drei Einheitsvektoren längs der drei Koordinatenachsen bilden bereits eine reduzierte Basis.

In[27]:= LatticeReduce[{{1,0,0},{0,1,0},{0,0,1}}]

Out[27]=

Dies gibt die reduzierte Basis für ein Gitter im vierdimensionalen Raum an, das durch drei Vektoren erzeugt wird.

In[28]:= LatticeReduce[{{1,0,0,12345}, {0,1,0,12435},
{0,0,1,12354}}]

Out[28]=

Beachten Sie, daß im letzten Beispiel LatticeReduce Vektoren, die nahezu parallel waren, durch Vektoren ersetzt, die eher senkrecht aufeinanderstehen. In diesem Prozeß findet es einige ziemlich kurze Basisvektoren.

Kettenbrüche

So werden die ersten 10 Terme der Kettenbruchdarstellung von erzeugt.

In[29]:= ContinuedFraction[Pi, 10]

Out[29]=

So wird die Zahl rekonstruiert, die durch die Liste der Kettenbruch-Terme repräsentiert wird.

In[30]:= FromContinuedFraction[%]

Out[30]=

Das Ergebnis liegt nahe bei .

In[31]:= N[%]

Out[31]=

Kettenbrüche tauchen in vielen zahlentheoretischen Zusammenhängen auf. Rationale Zahlen haben abbrechende Kettenbruchdarstellungen. Quadratische irrationale Zahlen haben Kettenbruchdarstellungen, die periodisch werden.

Vollständige Darstellungen für Zahlen

Die Kettenbruchdarstellung von beginnt mit dem Term 8 und hat dann eine Folge von Termen, die sich ohne Ende wiederholt.

In[32]:= ContinuedFraction[Sqrt[79]]

Out[32]=

So wird die Zahl aus ihrer Kettenbruchdarstellung rekonstruiert.

In[33]:= FromContinuedFraction[%]

Out[33]=

Dies zeigt die sich wiederholende Folge von Dezimalziffern in .

In[34]:= RealDigits[3/7]

Out[34]=

FromDigits rekonstruiert die ursprüngliche Zahl.

In[35]:= FromDigits[%]

Out[35]=

Zifferzählfunktion

Hier sind die Ziffern bei der Basis-2-Darstellung der Zahl 77.

In[36]:= IntegerDigits[77, 2]

Out[36]=

So wird die Anzahl der Einsen in der Basis-2-Darstellung direkt berechnet.

In[37]:= DigitCount[77, 2, 1]

Out[37]=

Die Darstellung der Zifferzählfunktion ist selbst-ähnlich.

In[38]:= ListPlot[Table[DigitCount[n, 2, 1], {n, 128}],
PlotJoined->True]

Out[38]=

Bit-weise Operationen

Bit-weise Operationen sind auf ganze Zahlen anwendbar, die binär dargestellt werden. BitAnd[,,... ] liefert die ganze Zahl, deren Binärdarstellung Einsen an den Stellen hat, an denen die Binärdarstellungen aller Einsen hat. BitOr[, , ... ] liefert die ganze Zahl, die Einsen an den Stellen hat, an denen zumindest einer der eine Eins hat. BitXor[, ] liefert die ganze Zahl, die Einsen an den Stellen hat, an denen oder , aber nicht beide zugleich Einsen haben. BitXor[, , ... ] hat Einsen an den Stellen, an denen eine ungerade Anzahl der Einsen haben.

So wird das bit-weise AND der Zahlen 23 und 29, eingegeben in der Basis 2, ermittelt.

In[39]:= BaseForm[BitAnd[2^^10111, 2^^11101], 2]

Out[39]//BaseForm=

Bit-weise Operationen werden in diversen kombinatorischen Algorithmen eingesetzt. Sie werden auch weithin eingesetzt in maschinennahen Computersprachen bei der Manipulation von Bit-Feldern. In derartigen Sprachen haben jedoch ganze Zahlen normalerweise eine begrenzte Stellenanzahl, typischerweise ein Mehrfaches von 8. Bit-weise Operationen in Mathematica erlauben hingegen, daß ganze Zahlen eine unbegrenzte Anzahl Stellen haben. Wenn eine ganze Zahl negativ ist, wird sie in Zweierkomplementform dargestellt, mit einer unendlichen Folge von Einsen auf der linken Seite. So wird es möglich, daß BitNot[n] einfach zu äquivalent ist.

PseudozufallszahlenKombinatorische Funktionen