Doppelpost! Zahlentheorie: Eigenschaften ggt, Legendre, Eulerkriterium, QNR |
| 01.10.2012, 14:33 | lustigerunde | Auf diesen Beitrag antworten » |
| Zahlentheorie: Eigenschaften ggt, Legendre, Eulerkriterium, QNR Hallo Zahlentheoretiker, ich habe noch ein paar Altklausurfragen, die ich noch nicht sicher beantworten kann. Vielleicht könnt ihr mir ja helfen: Aufgabe A: Bei welchem Folgezeichen steckt der Fehler (Es kann mehere Fehler geben). Dabei ist an jeder Stelle davon auszugehen, dass die Voraussetzung richtig ist (auch wenn vorher eine falsche Deduktion vorkam). a,b \el\ \IN beliebig , p sei eine beliebige ungerade Primzahl ggt(a,p)= 1 und ggt(b,p)=1 (1) => ggt(ab,p)=1 (2) => (ab)^((p-1)/2)==((ab)/p) mod p (3) => (ab)^((p-1)/2)==(a/p)(b/p) mod p (4) => (ab)^((p-1)/2)==(a/p)(b/p)^(-1) mod p (5) => (ab)^((p-1)/2)==(a/p)-(b/p) mod p Aufgabe B: Bei welchem Folgezeichen steckt der Fehler (Es kann mehere Fehler geben). Dabei ist an jeder Stelle davon auszugehen, dass die Voraussetzung richtig ist (auch wenn vorher eine falsche Deduktion vorkam). a,b \el\ \IN beliebig , p sei eine beliebige ungerade Primzahl ggt(a,p)= 1 und ggt(b,p)=1 (1) => ggt(ab,pb)=b und ggt(ab,pa)=a (2) => ggt(ab,pb+pa)=a+b (3) => \exists\ x,y \el\ \IZ mit xab+y(pb+pa)=a+b (4) => ab\IZ+(pb+pa)\IZ \superset\ (a+b)\IZ (5) => ab\IZ+pb\IZ+pa\IZ \superset\ (a+b)\IZ Aufgabe C: Sei ggt(a,n)=1 und a Primitivwurzel mod n. n \el \IN. Dann gilt: (1) ord_n(a)=\phi(n) (2) ord_n(a) \| \phi(n) (3) a ist Quadratischer Nichtrest (4) ab==1 mod n => b ist PW mod n (5) a ist Quadratischer Rest mod n Meine Ideen: Aufgabe A (1) ist richtig (Eindeutigkeit der Primfaktorzerlegung). (2) ist richtig (Euler-Kriterium) (3) ist richtig (Das Legendresymbol ist streng multiplikativ. (4) kann ich nicht sicher beantworten. Das Problem, dass ich habe, ist, dass fed-Code einblendenfed-Code ausblenden \( b/p )fed-Code ausblenden fed-Code im Editor öffnen auch 0 sein kann. Das ist genau dann der Fall, wenn der ggt(b,p) nicht eins ist. Dann wäre fed-Code einblendenfed-Code ausblenden \( b/p )^(-1)fed-Code ausblenden fed-Code im Editor öffnen nicht definiert. (5) ist falsch. Hier lässt sich ein einfaches Gegenbeispiel finden. Aufgabe B: Ich habe mir schon einige GEdanken über diese Aufgabe gemacht. (1) ist auf jeden Fall richtig und zu (2) kann man sich ein einfaches Gegenbeispiel überlegen. (3) lässt sich aus dem euklidischen Algorithmus folgern. Bei den anderen beiden, möchte ich meine Vermutungen noch nicht äußern, um die Antworten nicht zu verfälschen. Aufgabe C: Dass die Teile (1) und (2) richtig sind, ist mir bewusst: Wenn a eine PW mod n ist, ist sie auch Erzeuger der Einheitengruppe und hat damit volle Ordnung. Wenn (1) richtig ist, folgt entsprechend, dass (2) auch richtig ist. Bei dir (4) habe ich lediglich eine Tendenz, dass sie richtig ist. Ich habe es bei einigen Zahlen und deren Primitivwurzeln ausprobiert und da hat es immer geklappt. Schwierig sind für mich noch die Aufgaben (3) und (5). In der Vorlesung bzw. in der Übung haben wir bewiesen, dass wenn n eine Primzahl ist, dass aus "a ist eine Primitivwurzel" auch folgt, dass "a Quadratischer Nichtrest" ist. Das haben wir aber wie gesagt nur für Primzahlen gezeigt. Hier handelt es sich ja bei n um eine natürliche Zahl. |
||
| 01.10.2012, 15:15 | jester. | Auf diesen Beitrag antworten » |
Wegen crossposting geschlossen. http://matheplanet.com/matheplanet/nuke/...um.php?forum=90 |
||
|
|
