Koprimzahlen – Definition, Beispiele und Eigenschaften. Koprimzahlen

Was ist gegenseitig? Primzahlen?

Definition von teilerfremden Zahlen

Definition von Koprimzahlen:

Koprimzahlen sind ganze Zahlen, die außer eins keinen gemeinsamen Teiler haben.

Beispiele für teilerfremde Zahlen

Beispiel für Koprimzahlen:

2 und 3 haben außer eins keinen weiteren gemeinsamen Teiler.

Ein weiteres Beispiel für teilerfremde Zahlen:

3 und 7 haben außer einem keinen weiteren gemeinsamen Faktor.

Ein weiteres Beispiel für teilerfremde Zahlen:

11 und 13 haben außer einem keinen weiteren gemeinsamen Faktor.

Jetzt können wir die Frage beantworten, was Koprimzahlen bedeuten.

Was bedeuten Koprimzahlen?

Dabei handelt es sich um ganze Zahlen, die außer Eins keinen gemeinsamen Teiler haben.

Zwei teilerfremde Zahlen

Jedes dieser Paare besteht aus zwei relativ Primzahlen.

11 und 15
15 und 16
16 und 23

Gemeinsame Teiler von teilerfremden Zahlen

Der gemeinsame Teiler von teilerfremden Zahlen ist nur eins, wie aus der Definition von teilerfremden Zahlen hervorgeht.

Größter gemeinsamer Teiler von teilerfremden Zahlen

Der größte gemeinsame Teiler von Koprimzahlen ist eins, wie aus der Definition von Koprimzahlen hervorgeht.

Sind Zahlen teilerfremd?

Sind die Zahlen 3 und 13 teilerfremd? Ja, weil sie außer einem keinen gemeinsamen Teiler haben.

Sind die Zahlen 3 und 12 teilerfremd? Nein, denn ihre gemeinsamen Teiler sind 1 und 3. Und nach der Definition von teilerfremden Zahlen sollte der gemeinsame Teiler nur eins sein.

Sind die Zahlen 3 und 108 teilerfremd? Nein, denn ihre gemeinsamen Teiler sind 1 und 3. Und nach der Definition von teilerfremden Zahlen sollte der gemeinsame Teiler nur eins sein.

Sind die Zahlen 108 und 5 teilerfremd? Ja, weil sie außer einem keinen gemeinsamen Teiler haben.

Die Informationen in diesem Artikel behandeln das Thema „ Koprimzahlen" Zunächst wird die Definition von zwei teilerfremden Zahlen sowie die Definition von drei oder mehr teilerfremden Zahlen gegeben. Anschließend werden Beispiele für teilerfremde Zahlen gegeben und es wird gezeigt, wie man beweist, dass gegebene Zahlen teilerfremd sind. Im Folgenden werden die grundlegenden Eigenschaften von teilerfremden Zahlen aufgeführt und bewiesen. Abschließend werden paarweise Primzahlen erwähnt, da sie eng mit Koprimzahlen verwandt sind.

Seitennavigation.

Es gibt oft Aufgaben, bei denen man beweisen muss, dass gegebene ganze Zahlen relativ teilerfremd sind. Der Beweis läuft darauf hinaus, den größten gemeinsamen Teiler der gegebenen Zahlen zu berechnen und den ggT zu prüfen, um zu sehen, ob er gleich eins ist. Es ist auch nützlich, vor der Berechnung des GCD einen Blick auf die Tabelle der Primzahlen zu werfen: Plötzlich sind die ursprünglichen ganzen Zahlen Primzahlen, und wir wissen, dass der größte gemeinsame Teiler der Primzahlen gleich eins ist. Schauen wir uns die Beispiellösung an.

Beispiel.

Beweisen Sie, dass die Zahlen 84 und 275 relativ prim sind.

Lösung.

Offensichtlich sind diese Zahlen keine Primzahlen, daher können wir nicht sofort über die relative Primzahl der Zahlen 84 und 275 sprechen und müssen den ggT berechnen. Wir verwenden den euklidischen Algorithmus, um GCD zu finden: 275=84·3+23, 84=23·3+15, 23=15·1+8, 15=8·1+7, 8=7·1+1, 7 =7 ·1, also ggT(84, 275)=1. Dies beweist, dass die Zahlen 84 und 275 relativ prim sind.

Die Definition von teilerfremden Zahlen kann auf drei oder mehr Zahlen erweitert werden.

Definition.

Es werden ganze Zahlen a 1 , a 2 , …, a k , k>2 aufgerufen gegenseitig prim, wenn der größte gemeinsame Teiler dieser Zahlen gleich eins ist.

Aus der angegebenen Definition folgt, dass, wenn eine bestimmte Menge von ganzen Zahlen einen anderen positiven gemeinsamen Teiler als eins hat, diese ganzen Zahlen nicht teilerfremd sind.

Lassen Sie uns Beispiele nennen. Drei ganze Zahlen −99, 17 und −27 sind teilerfremd. Jede Sammlung von Primzahlen stellt eine Menge von Koprimzahlen dar, zum Beispiel sind 2, 3, 11, 19, 151, 293 und 677 Koprimzahlen. Und die vier Zahlen 12, −9, 900 und −72 sind nicht teilerfremd, da sie einen positiven gemeinsamen Teiler 3 außer 1 haben. Auch die Zahlen 17, 85 und 187 sind keine teilerfremden Zahlen, da sie jeweils durch 17 teilbar sind.

Es ist normalerweise alles andere als offensichtlich, dass manche Zahlen relativ prim sind, und diese Tatsache muss bewiesen werden. Um herauszufinden, ob bestimmte Zahlen teilerfremd sind, müssen Sie den größten gemeinsamen Teiler dieser Zahlen ermitteln und auf der Grundlage der Definition von teilerfremden Zahlen eine Schlussfolgerung ziehen.

Beispiel.

Sind die Zahlen 331, 463 und 733 relativ prim?

Lösung.

Wenn wir uns die Tabelle der Primzahlen ansehen, werden wir feststellen, dass jede der Zahlen 331, 463 und 733 eine Primzahl ist. Daher haben sie einen einzigen positiven gemeinsamen Teiler – eins. Somit sind die drei Zahlen 331, 463 und 733 relativ Primzahlen.

Antwort:

Ja.

Beispiel.

Beweisen Sie, dass die Zahlen −14, 105, −2 107 und −91 nicht teilerfremd sind.

Lösung.

Um zu beweisen, dass diese Zahlen keine relativen Primzahlen sind, können Sie ihren gcd ermitteln und sicherstellen, dass er nicht gleich eins ist. Das werden wir tun.

Da die Teiler negativer ganzer Zahlen mit den Teilern der entsprechenden Einsen übereinstimmen, dann GCD(−14, 105, 2 107, −91)= GCD(14, 105, 2 107, 91) . Wenn wir uns dem Material im Artikel „Ermitteln des größten gemeinsamen Teilers von drei oder mehr Zahlen“ zuwenden, finden wir heraus, dass GCD(14, 105, 2 · 107, 91) = 7. Daher ist der größte gemeinsame Teiler der ursprünglichen Zahlen sieben, diese Zahlen sind also nicht teilerfremd.

Eigenschaften von teilerfremden Zahlen

Koprimzahlen haben eine Reihe von Eigenschaften. Schauen wir uns das Wichtigste an Eigenschaften von teilerfremden Zahlen.

Die durch Division der ganzen Zahlen a und b durch ihren größten gemeinsamen Teiler erhaltenen Zahlen sind teilerfremd, d. h. a:GCD(a, b) und b:GCD(a, b) sind teilerfremd.

Wir haben diese Eigenschaft bewiesen, als wir die Eigenschaften von GCD untersucht haben.

Die betrachtete Eigenschaft von Koprimzahlen ermöglicht es uns, Paare von Koprimzahlen zu finden. Dazu reicht es aus, zwei beliebige ganze Zahlen zu nehmen und sie durch den größten gemeinsamen Teiler zu dividieren. Die resultierenden Zahlen sind relativ prim.

Damit die ganzen Zahlen a und b teilerfremd sind, ist es notwendig und ausreichend, dass es ganze Zahlen u 0 und v 0 gibt, so dass a·u 0 +b·v 0 =1.

Beweisen wir zunächst die Notwendigkeit.

Die Zahlen a und b seien teilerfremd. Dann ist nach der Definition von teilerfremden Zahlen ggT(a, b)=1. Und aus den Eigenschaften von GCD wissen wir, dass für ganze Zahlen a und b die Bezout-Beziehung a·u 0 +b·v 0 =GCD(a, b) gilt. Daher ist a·u 0 +b·v 0 =1.

Es bleibt der Nachweis der Ausreichendheit.

Es sei die Gleichheit a·u 0 +b·v 0 =1 wahr. Da GCD(a, b) sowohl a als auch b teilt, muss GCD(a, b) aufgrund der Teilbarkeitseigenschaften die Summe a·u 0 +b·v 0 teilen und daher eins sein. Und das ist nur möglich, wenn GCD(a, b)=1. Daher sind a und b relativ Primzahlen.

Die nächste Eigenschaft von teilerfremden Zahlen ist diese: Wenn die Zahlen a und b teilerfremd sind und das Produkt a·c durch b teilbar ist, dann ist c durch b teilbar.

Da a und b tatsächlich teilerfremd sind, ergibt sich aus der vorherigen Eigenschaft die Gleichung a·u 0 +b·v 0 =1. Wenn wir beide Seiten dieser Gleichheit mit c multiplizieren, erhalten wir a·c·u 0 +b·c·v 0 =c. Der erste Term der Summe a·c·u 0 +b·c·v 0 wird durch b geteilt, da a·c gemäß der Bedingung durch b geteilt wird, der zweite Term dieser Summe wird ebenfalls durch b geteilt, da Einer der Faktoren ist gleich b, daher wird die gesamte Summe durch b geteilt. Und da die Summe a·c·u 0 +b·c·v 0 gleich c ist, ist c durch b teilbar.

Wenn die Zahlen a und b teilerfremd sind, dann ist gcd(a c, b) = gcd(c, b) .

Zeigen wir erstens, dass gcd(a c, b) gcd(c, b) teilt, und zweitens, dass gcd(c, b) gcd(a c, b) teilt, dies beweist die Gleichheit GCD(a c, b) =GCD(c, b) .

GCD(a c, b) teilt sowohl a c als auch b, und da gcd(a c, b) b teilt, teilt es auch b c. Das heißt, gcd(a c, b) teilt sowohl a c als auch b c und teilt daher aufgrund der Eigenschaften des größten gemeinsamen Teilers auch gcd(a c, b c), was gemäß den Eigenschaften von gcd gleich c ist GCD(a, b)=c . Somit teilt gcd(ac, b) sowohl b als auch c und teilt daher auch gcd(c, b).

Andererseits teilt GCD(c, b) sowohl c als auch b, und da es c teilt, teilt es auch a·c. Somit teilt gcd(c, b) sowohl a c als auch b und daher auch gcd(a c, b).

Wir haben also gezeigt, dass gcd(a c, b) und gcd(c, b) sich gegenseitig dividieren, was bedeutet, dass sie gleich sind.

Wenn jede der Zahlen a 1 , a 2 , …, a k mit jeder der Zahlen b 1 , b 2 , …, b m teilerfremd ist (wobei k und m einige natürliche Zahlen sind), dann sind die Produkte a 1 · a 2 · … · a k und b 1 · b 2 ·…·b m sind teilerfremde Zahlen, insbesondere wenn a 1 =a 2 =…=a k =a und b 1 =b 2 =…=b m =b, dann sind a k und b m Koprimzahlen.

Die vorherige Eigenschaft von teilerfremden Zahlen ermöglicht es uns, eine Reihe von Gleichungen der Form zu schreiben GCD(a 1 · a 2 ·…·a k , b m)= GCD(a 2 ·…·a k , b m)=…=GCD(a k , b m)=1, wobei der letzte Übergang möglich ist, da a k und b m aufgrund der Bedingung gegenseitig Primzahlen sind. Also, GCD(a 1 · a 2 ·…·a k , b m)=1.

Wenn wir nun a 1 ·a 2 ·…·a k =A bezeichnen, gilt:
GCD(b 1 ·b 2 ·…·b m , a 1 ·a 2 ·…·a k)= GCD(b 1 b 2…b m , A)=
=GCD(b 2 ·…·b m , A)=… =GCD(b m , A)=1
(Der letzte Übergang ist aufgrund der letzten Gleichheit aus dem vorherigen Absatz gültig.) So haben wir die Gleichberechtigung erreicht GCD(b 1 ·b 2 ·…·b m , a 1 ·a 2 ·…·a k)=1, was beweist, dass die Produkte a 1 ·a 2 ·…·a k und b 1 ·b 2 ·…·b m Koprimzahlen sind.

Damit ist unser Überblick über die grundlegenden Eigenschaften von teilerfremden Zahlen abgeschlossen.

Paarweise Primzahlen – Definitionen und Beispiele

Durch Koprimzahlen ist es gegeben Identifizierung von Primzahlpaaren.

Definition.

Es werden ganze Zahlen a 1, a 2, …, a k genannt, die jeweils teilerfremd zu allen anderen sind paarweise Primzahlen.

Lassen Sie uns ein Beispiel für paarweise Primzahlen geben. Die Zahlen 14, 9, 17 und −25 sind paarweise Primzahlen, da die Zahlenpaare 14 und 9, 14 und 17, 14 und −25, 9 und 17, 9 und −25, 17 und −25 Koprimzahlen sind. Hier stellen wir fest, dass paarweise Primzahlen immer teilerfremd sind.

Andererseits sind relativ Primzahlen nicht immer paarweise Primzahlen, wie das folgende Beispiel bestätigt. Die Zahlen 8, 16, 5 und 15 sind keine paarweisen Primzahlen, da die Zahlen 8 und 16 keine Koprimzahlen sind. Allerdings sind die Zahlen 8, 16, 5 und 15 relativ prim. Somit sind 8, 16, 5 und 15 relativ Primzahlen, aber keine paarweisen Primzahlen.

Besonders hervorzuheben ist die Sammlung einer bestimmten Anzahl von Primzahlen. Diese Zahlen sind immer sowohl teilerfremd als auch paarweise prim. Beispielsweise sind 71, 443, 857, 991 sowohl paarweise Primzahlen als auch Koprimzahlen.

Es ist auch klar, wann wir reden über etwa zwei ganze Zahlen, dann stimmen für sie die Konzepte „paarweise Primzahl“ und „gegenseitige Primzahl“ überein.

Referenzliste.

Vilenkin N.Ya. und andere. 6. Klasse: Lehrbuch für allgemeinbildende Einrichtungen.
Winogradow I.M. Grundlagen der Zahlentheorie.
Mikhelovich Sh.H. Zahlentheorie.
Kulikov L.Ya. und andere. Sammlung von Problemen in Algebra und Zahlentheorie: Lernprogramm für Studierende der Physik und Mathematik. Spezialitäten pädagogischer Institute.

Mathematiklehrbücher sind manchmal schwer zu verstehen. Die trockene und klare Sprache der Autoren ist nicht immer leicht zu verstehen. Und die Themen dort sind immer miteinander verbunden und folgenreich füreinander. Um ein Thema zu meistern, muss man mehrere vorherige aufgreifen und manchmal sogar das gesamte Lehrbuch durchblättern. Schwierig? Ja. Gehen wir das Risiko ein, diese Schwierigkeiten zu umgehen und versuchen, einen nicht standardmäßigen Ansatz für das Thema zu finden. Machen wir eine Art Ausflug ins Land der Zahlen. Wir lassen die Definition jedoch unverändert, da die Regeln der Mathematik nicht aufgehoben werden können. Koprimzahlzahlen sind also natürliche Zahlen mit einem gemeinsamen Teiler gleich eins. Das ist klar? Ganz.

Für ein anschaulicheres Beispiel nehmen wir die Zahlen 6 und 13. Beide sind durch eins teilbar (koprime). Aber die Zahlen 12 und 14 können keine solchen sein, da sie nicht nur durch 1, sondern auch durch 2 teilbar sind. Die folgenden Zahlen, 21 und 47, passen ebenfalls nicht in die Kategorie der „koprimen Zahlen“: Sie können nicht geteilt werden nur um 1, sondern auch um 7.

Koprimzahlen werden wie folgt bezeichnet: ( A, y) = 1.

Man kann es noch einfacher sagen: Der gemeinsame (größte) Teiler ist hier gleich eins.
Warum brauchen wir solches Wissen? Gründe gibt es genug.

Gegenseitig in einigen Verschlüsselungssystemen enthalten. Wer mit Hill-Chiffren oder Caesars Substitutionssystem arbeitet, weiß: Ohne dieses Wissen kommt man nicht weiter. Wenn Sie von Generatoren gehört haben, werden Sie es kaum zu leugnen wagen: Auch dort werden relativ Primzahlen verwendet.

Lassen Sie uns nun über Möglichkeiten sprechen, solche einfachen zu erhalten. Wie Sie wissen, können sie nur zwei Teiler haben: Sie sind durch sich selbst und durch eins teilbar. Nehmen wir an, 11, 7, 5, 3 sind Primzahlen, 9 jedoch nicht, da diese Zahl bereits durch 9, 3 und 1 teilbar ist.

Und wenn A- Die Zahl ist eine Primzahl und bei- aus dem Set (1, 2, ... A- 1), dann ist es garantiert ( A, bei) = 1, oder teilerfremde Zahlen - A Und bei.

Dabei handelt es sich vielmehr nicht einmal um eine Erklärung, sondern um eine Wiederholung oder Zusammenfassung dessen, was gerade gesagt wurde.

Die Ermittlung von Primzahlen ist möglich; für große Zahlen (zum Beispiel Milliarden) ist diese Methode zu langwierig, aber im Gegensatz zu Superformeln, die manchmal Fehler machen, ist sie zuverlässiger.

Sie können durch Auswahl arbeiten bei > A. Dazu wird y so gewählt, dass die Zahl on A nicht geteilt. Dazu wird eine Primzahl mit einer natürlichen Zahl multipliziert und eine Größe addiert (oder umgekehrt subtrahiert) (z. B. R), was weniger ist A:

y = R a + k

Wenn zum Beispiel A = 71, R= 3, q=10, dann dementsprechend bei hier ist es gleich 713. Eine andere Auswahl mit Graden ist möglich.

Zusammengesetzte Zahlen sind im Gegensatz zu relativ Primzahlen durch sich selbst, durch 1 und durch andere Zahlen (auch ohne Rest) teilbar.

Mit anderen Worten, (bis auf eines) werden sie in zusammengesetzte und einfache unterteilt.

Primzahlen sind natürliche Zahlen, die keine nichttrivialen (von der Zahl selbst und der Eins verschiedenen) Teiler haben. Ihre Rolle ist besonders wichtig in der heutigen modernen, sich schnell entwickelnden Kryptographie, dank der eine Disziplin, die früher als äußerst abstrakt galt, so gefragt geworden ist: Datenschutzalgorithmen werden ständig verbessert.

Die größte Primzahl wurde vom Augenarzt Martin Nowak gefunden, der zusammen mit anderen Enthusiasten am GIMPS-Projekt (Distributed Computing) teilnahm. Die Berechnungen dauerten sechs seit langen Jahren. Beteiligt waren zweieinhalb Dutzend Computer in Novaks Augenklinik. Das Ergebnis gigantischer Arbeit und Ausdauer war die Zahl 225964951-1, geschrieben mit 7816230 Dezimalstellen. Übrigens, die Platte selbst große Zahl wurde sechs Monate vor dieser Eröffnung aufgeführt. Und es gab eine halbe Million Schilder weniger.

Ein Genie, das eine Zahl nennen will, wo ist die Dauer Dezimalschreibweise Wenn jemand die Zehn-Millionen-Marke „überspringt“, besteht die Chance, nicht nur Weltruhm, sondern auch 100.000 US-Dollar zu erhalten. Für die Zahl, die die Millionengrenze überschritt, erhielt Nayan Khairatwal übrigens einen kleineren Betrag (50.000 US-Dollar).

Zurück vorwärts

Aufmerksamkeit! Folienvorschauen dienen nur zu Informationszwecken und stellen möglicherweise nicht alle Funktionen der Präsentation dar. Wenn Sie an dieser Arbeit interessiert sind, laden Sie bitte die Vollversion herunter.

Diese Arbeit soll die Erläuterung begleiten neues Thema. Der Lehrer wählt die praktischen Aufgaben und Hausaufgaben nach eigenem Ermessen aus.

Ausrüstung: Computer, Projektor, Leinwand.

Fortschritt der Erklärung

Folie 1. Größter gemeinsamer Teiler.

Mündliche Arbeit.

1. Berechnen Sie:

A)
0,7
* 10
: 2
- 0,3
: 0,4
_________
?
B)
5
: 10
* 0,2
+ 2
: 0,7
_______
?

Antworten: a) 8; b) 3.

2. Widerlegen Sie die Aussage: Die Zahl „2“ ist der gemeinsame Teiler aller Zahlen.“

Offensichtlich sind ungerade Zahlen nicht durch 2 teilbar.

3. Wie nennt man Zahlen, die ein Vielfaches von 2 sind?

4. Nennen Sie eine Zahl, die ein Teiler einer beliebigen Zahl ist.

Schriftlich.

1. Zerlegen Sie die Zahl 2376 in Primfaktoren.

2. Finden Sie alles gemeinsame Teiler Nummern 18 und 60.

Was ist der größte gemeinsame Teiler der Zahlen 18 und 60?

Versuchen Sie zu formulieren, welche Zahl der größte gemeinsame Teiler zweier natürlicher Zahlen ist

Regel. Die größte natürliche Zahl, die ohne Rest teilbar ist, wird größter gemeinsamer Teiler genannt.

Sie schreiben: GCD (18; 60) = 6.

Bitte sagen Sie mir, ist die in Betracht gezogene Methode zur Suche nach GCD praktisch?

Die Zahlen sind möglicherweise zu groß und es ist schwierig, alle Teiler aufzulisten.

Versuchen wir, einen anderen Weg zu finden, um GCD zu finden.

Zerlegen wir die Zahlen 18 und 60 in Primfaktoren:

18 =

Nennen Sie Beispiele für Teiler der Zahl 18.

Zahlen: 1; 2; 3; 6; 9; 18.

Nennen Sie Beispiele für Teiler der Zahl 60.

Zahlen: 1; 2; 3; 4; 5; 6; 10; 12; 15; 20; dreißig; 60.

Nennen Sie Beispiele für gemeinsame Teiler der Zahlen 18 und 60.

Zahlen: 1; 2; 3; 6.

Wie findet man den größten gemeinsamen Teiler von 18 und 60?

Algorithmus.

1. Teilen Sie die angegebenen Zahlen in Primfaktoren.

2. Vergleichen Sie die Faktoren von Zahlen und streichen Sie verschiedene durch.

3. Berechnen Sie das Produkt der verbleibenden Faktoren.

Folie 4. Koprimzahlen.

Übung. Finden Sie den gcd der Zahlen 24 und 35.

Regel. Ganze Zahlen heißen Koprime, wenn ihr größter gemeinsamer Teiler 1 ist.

Das ist interessant!

Teiler von 18: 1; 2; 3; 6; 9; 18.
Teiler von 60: 1; 2; 3; 4; 5; 6; 10; 12; 15; 20; dreißig; 60.
GCD (18;60) = 6.
Teiler von 6: 1; 2; 3; 6.
Beachten Sie, dass die Zahlen 1 sind; 2; 3; 6 sind gemeinsame Teiler der Zahlen 18 und 60.
Zum Beispiel ist GCD (108;196) = 4. Das bedeutet, dass wir sofort sagen können, dass die gemeinsamen Teiler der Zahlen 108 und 196 die Teiler der Zahl 4 sind, also 1; 2; 4.

Jeder Teiler der Zahl GCD (a;b) ist ein gemeinsamer Teiler der Zahlen a und b und umgekehrt ist jeder ihrer gemeinsamen Teiler ein Teiler der Zahl GCD (a;b).

Es könnte nützlich sein zu lesen: