Zahlentheorie - Modulo - Letzten kleinen Fragen (morgen Klausur)

07.02.2011, 17:09

p.BA/MA.L.MAIN.2010

Zahlentheorie - Modulo - Letzten kleinen Fragen (morgen Klausur)

Hallo,

der letzte Tag vor der Klausur ist gekommen und ich habe noch ein paar offene Fragen.

Und zwar.

1) Zeigen Sie: Falls p eine Primzahl ist, so ist p%30 auch eine Primzahl.

Klar, für alle p < 30.

Aber darüber? Angenommen wir gernerien ein beliebgies p' mit p' = (30 * n) + x, jetzt müsste ich eigentl. irgendwie darauf schließen, dass x nur primzahlen enthält.

evtl. weil 30 nur durch die einziffrigen Zahlen 1,2,3,5 teilbar ist und das bis auf die 1 eine Primzahl sind? ...

2) a%14=10, Berechnen sie (15a^3 + 28a^2 - 3a -43)%7, wie ich hier herangehen soll, weiß ich überhaupt nicht.

Vllt. findet sich ja noch ein Helfer in letzter Not smile

07.02.2011, 17:11

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von p.BA/MA.L.MAIN.2010
1) Zeigen Sie: Falls p eine Primzahl ist, so ist p%30 auch eine Primzahl.

Für Leute, die des C/C++/Java unkundig sind, ziemlich unverständlich. Im Mathematikerboard schreib deshalb besser $\begin{eqnarray*} p\bmod 30 \end{eqnarray*}$ . Augenzwinkern

Zum fachlichen: Beweise die Behauptung doch einfach indirekt!

Nimm an, dass es eine Primzahl $\begin{eqnarray*} p \end{eqnarray*}$ gibt, so dass $\begin{eqnarray*} m = p \bmod 30 \end{eqnarray*}$ keine Primzahl ist. Jetzt nimm dir mal den kleinsten Primteiler $\begin{eqnarray*} q \end{eqnarray*}$ von $\begin{eqnarray*} m \end{eqnarray*}$ unter die Lupe - was fällt auf?

07.02.2011, 17:47

Mystic

Auf diesen Beitrag antworten »

RE: Zahlentheorie - Modulo - Letzten kleinen Fragen (morgen Klausur)

Zitat:

Original von p.BA/MA.L.MAIN.2010
1) Zeigen Sie: Falls p eine Primzahl ist, so ist p%30 auch eine Primzahl.

C# meldet, dass 31%30 und 61%30 keine Primzahlen sind... Wie ist das zu erklären? verwirrt

07.02.2011, 17:52

p.BA/MA.L.MAIN.2010

Auf diesen Beitrag antworten »

RE: Zahlentheorie - Modulo - Letzten kleinen Fragen (morgen Klausur)

Zitat:

Original von Mystic

Zitat:

Original von p.BA/MA.L.MAIN.2010
1) Zeigen Sie: Falls p eine Primzahl ist, so ist p%30 auch eine Primzahl.

C# meldet, dass 31%30 und 61%30 keine Primzahlen sind... Wie ist das zu erklären? verwirrt

Sollte das jetzt eine Hilfestellung sein, oder einfach nur eine Nebenbemerkung?

Naja, irgendwie komm ich nicht ganz weiter. Der kleinste Primteiler von m muss doch p mod 30 sein, da es ja sonst keine Primzahl wäre?

07.02.2011, 17:53

jester.

Auf diesen Beitrag antworten »

Es gibt bis 10000 sogar 152 Gegenbeispiele laut Maple,

Zitat:

{31, 61, 151, 181, 211, 241, 271, 331, 421, 541, 571, 601, 631, 661, 691, 751, 811, 991, 1021, 1051, 1171, 1201, 1231, 1291, 1321, 1381, 1471, 1531, 1621, 1741, 1801, 1831, 1861, 1951, 2011, 2131, 2161, 2221, 2251, 2281, 2311, 2341, 2371, 2521, 2551, 2671, 2731, 2791, 2851, 2971, 3001, 3061, 3121, 3181, 3271, 3301, 3331, 3361, 3391, 3511, 3541, 3571, 3631, 3691, 3931, 4021, 4051, 4111, 4201, 4231, 4261, 4441, 4561, 4591, 4621, 4651, 4801, 4831, 4861, 4951, 5011, 5101, 5281, 5431, 5521, 5581, 5641, 5701, 5791, 5821, 5851, 5881, 6091, 6121, 6151, 6211, 6271, 6301, 6361, 6421, 6451, 6481, 6571, 6661, 6691, 6781, 6841, 6871, 6961, 6991, 7321, 7351, 7411, 7561, 7591, 7621, 7681, 7741, 7951, 8011, 8101, 8161, 8191, 8221, 8311, 8431, 8461, 8521, 8581, 8641, 8731, 8761, 8821, 8941, 8971, 9001, 9091, 9151, 9181, 9241, 9391, 9421, 9511, 9601, 9631, 9661, 9721, 9781, 9811, 9871, 9901, 9931}

Diese erfüllen alle, dass $\begin{eqnarray*} p \equiv 1 \mod 30 \end{eqnarray*}$ ...

07.02.2011, 18:03

p.BA/MA.L.MAIN.2010

Auf diesen Beitrag antworten »

Aber, es geht doch nicht darum, dass die letzte Stelle 1, sondern, dass bei Division einer Primzahl mit Rest - der Rest wieder eine Primzahl ist.

07.02.2011, 18:11

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von p.BA/MA.L.MAIN.2010
Aber, es geht doch nicht darum, dass die letzte Stelle 1, sondern, dass bei Division einer Primzahl mit Rest - der Rest wieder eine Primzahl ist.

Eigentlich wollten wir ja nur darauf hinweisen, dass dein obiger Satz "p%30 ist immer prim", eben nicht immer gilt sondern (in deiner Diktion!) nur für p%30!=1... Augenzwinkern

Edit: Auch von mir noch ein fachlicher Tipp, damit du nicht glaubst, ich will dich hier nur verulken...

1. Primzahlen p>30 haben keinen Primteiler <7 und sind daher insbesondere zu 30 teilerfremd...
2. p mod 30 ist weiterhin zu 30 teilerfremd, d.h., weder durch 2, noch durch 3, noch durch 5 teilbar...
3. Du muss also nur noch zeigen, dass eine natürliche Zahl n<30, welche zu 30 teilerfremd ist, entweder 1 oder prim ist (hat was mit Sieb des Eratosthenes zu tun!)...

07.02.2011, 19:05

p.BA/MA.L.MAIN.2010

Auf diesen Beitrag antworten »

Ok,

dann hatte ich wohl einfach ein Brett vorm Kopf. Danke, dann werde ich mich einmal mit Sieb des Eratosthenes beschäftigen.

hat jemand noch eine Idee für a%14=10, Berechnen sie (15a^3 + 28a^2 - 3a -43)%7?

07.02.2011, 19:15

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von p.BA/MA.L.MAIN.2010
Der kleinste Primteiler von m muss doch p mod 30 sein, da es ja sonst keine Primzahl wäre?

Du erzählst Unsinn: Der Widerspruchsbeweis ging von der These aus, dass $\begin{eqnarray*} m \end{eqnarray*}$ keine Primzahl ist!

Was ich meinte ist, dass (den Fall m=1 ausschließend) $\begin{eqnarray*} q\leq \sqrt{m} \leq \sqrt{30} \end{eqnarray*}$ , also $\begin{eqnarray*} q\leq 5 \end{eqnarray*}$ ist, anders formuliert $\begin{eqnarray*} q\in\{2,3,5\} \end{eqnarray*}$ . Damit ist $\begin{eqnarray*} q|30 \end{eqnarray*}$ und folglich auch $\begin{eqnarray*} q|p \end{eqnarray*}$ , Widerspruch.

07.02.2011, 19:29

p.BA/MA.L.MAIN.2010

Auf diesen Beitrag antworten »

Jaa, da hab ich in meiner Unwissenheit mist erzählt. Mir fehlt halt noch ein bisschen der Durchblick ( 1. Semester). War wohl etwas zu faul. Naja aus Fehlern lernt man.

Bzgl.

a mod 14=10, Berechnen sie (15a^3 + 28a^2 - 3a -43) mod 7

Falls a mod 14 = 10 ist, gilt wohl für alle a % 7 = 3? Hab es jetzt nur an Beispielen getestet. Liege ich da evtl. richtig, da

(15a^3 + 28a^2 - 3a -43) mod 7 = (15a^3 mod 7 + 28a^2 mod 7 - 3a mod 7 -43 mod 7 ) mod 7, da bis auf 43 mod 7 für alle a mod 14 = 10 bzw. a mod 7 = 3 gilt, da es vielfache sind?

(3 + 3 - 3 -1) %7 = 2?

Korrektur:

( [15 mod 7 * a mod 7 * a mod 7 * a mod 7] mod 7 + [28 mod 7 * a mod 7 * a mod 7] mod 7 - [3 mod 7 * a mod 7] mod 7 - [43 mod 7] ) mod 7
= ( [1 * 3 * 3 * 3] mod 7 - [ 0] - [3 * 3 ] mod 7 - [1] ) = ( 6 - 0 - 2 - 1 ) mod 7 = 3

07.02.2011, 20:12

Mystic

Auf diesen Beitrag antworten »

Das Ergebnis der korrigierten Version stimmt, du solltest das aber viel kürzer abhandeln z.B.

$\begin{eqnarray*} a \equiv 10 \mod 14 \Rightarrow a \equiv 3 \mod 7 \Rightarrow 15a^3+28a^2-3a-43 \equiv \\ \equiv 1\cdot 3^3+0\cdot 3^2 -3\cdot 3-1 \equiv 6+0-2-1 \equiv 3 \mod 7 \end{eqnarray*}$

reicht hier vollkommen... Augenzwinkern

Neue Frage »

Antworten »

Zahlentheorie - Modulo - Letzten kleinen Fragen (morgen Klausur)

Verwandte Themen