nochmal Kongruenzen

17.06.2005, 21:22	heiko	Auf diesen Beitrag antworten »
nochmal Kongruenzen Zeige fuer $\begin{eqnarray} m\geq2 \end{eqnarray}$ : $\begin{eqnarray} (\prod_{i=1}^{m}{i})^2 \end{eqnarray}$ $\begin{eqnarray} \equiv1 \end{eqnarray}$ $\begin{eqnarray} mod(m) \end{eqnarray}$ wobei das Produkt nur ueber die i laeuft fuer die ggT(i,m) = 1 gilt.
17.06.2005, 21:37	AD	Auf diesen Beitrag antworten »
RE: nochmal Kongruenzen Wenn du den Beweis http://www.matheboard.de/thread.php?postid=175737#post175737 begriffen hast, ist diese Aufgabe nicht viel mehr als eine Folgerung der dort angewandten Prinzipien: Wenn M die Menge der zu m teilerfremden Zahlen aus {1,2,...,m} ist, dann kann man M in zwei disjunkte Teilmengen Q und N zerlegen: $\begin{eqnarray} Q = \left\{ r\in M \bigm\| r^2\equiv 1\mod m\right\} \end{eqnarray}$ $\begin{eqnarray} N = \left\{ r\in M \bigm\| r^2\not\equiv 1\mod m\right\} \end{eqnarray}$ In N geht's weiter wie in http://www.matheboard.de/thread.php?postid=175737#post175737 . Und Q sollte kein Problem sein.
18.06.2005, 15:16	heiko	Auf diesen Beitrag antworten »
RE: nochmal Kongruenzen ich versteh nicht, was deine Einteilung soll? Fuer Primzahlen kann ich doch sagen, dass gelten muss: $\begin{eqnarray} (m-1)!^2 = 1 (m) \end{eqnarray}$ $\begin{eqnarray} \Leftrightarrow m \| (m-1)!^2 - 1 \end{eqnarray}$ $\begin{eqnarray} \Rightarrow{m}\not\|{(m-1)!^2} \end{eqnarray}$ $\begin{eqnarray} \Rightarrow ggT(m, (m-1)!^2) = 1 \end{eqnarray}$ und gabs dazu nicht einen Satz? Fuer m nicht prim hab ich noch keine Ahnung...
18.06.2005, 16:04	AD	Auf diesen Beitrag antworten »
Richtig, für Primzahlen m ist das einfach der Satz von Wilson, nur quadriert. Und für alle anderen m habe ich ja eben die Beweisskizze mit dieser Einteilung vorgenommen!!! (Die funktioniert natürlich auch für Primzahlen m.) EDIT: Damit keine Missverständnisse aufkommen, sollte man deine Behauptung gleich so schreiben $\begin{eqnarray} \prod\limits_{\substack{i=1\\ \mathrm{ggT}(i,m)=1}}^{m-1}~i^2\equiv1 \mod m \end{eqnarray}$
18.06.2005, 21:47	heiko	Auf diesen Beitrag antworten »
Tut mir leid, ich hab echt ewig ueberlegt, aber ich weiss einfach nicht, wie ich mit deinem Ansatz zu ner Loesung kommen soll. Kannst du das vielleicht an einem Beispiel naeher erlaeutern?
18.06.2005, 22:00	AD	Auf diesen Beitrag antworten »
Ich weiß nicht, ob ein Beispiel nützt - aber bitte, nehmen wir mal als nichttriviales Beispiel n=15. Dann ist mit meinen obigen Bezeichnungen $\begin{eqnarray} M=\{1,2,4,7,8,11,13,14\} \end{eqnarray}$ . Die teilen sich auf in $\begin{eqnarray} Q=\{1,4,11,14\} \end{eqnarray}$ , weil $\begin{eqnarray} 1^2\equiv 4^2\equiv 11^2\equiv 14^2\equiv 1\mod 15 \end{eqnarray}$ , und $\begin{eqnarray} N=\{2,7,8,13\} \end{eqnarray}$ , der Rest. Und dieser Rest N läßt sich jetzt zu zwei Paaren gruppieren: (2,8) und (7,13), für die gilt $\begin{eqnarray} 2\cdot 8\equiv 7\cdot 13\equiv 1\mod 15 \end{eqnarray}$ , fertig! EDIT: Schreibfehler 9 in 8 geändert, sorry. EDIT 2: Mir fällt grad auf, dass ich das zwar richtig, aber ziemlich umständlich gemacht habe - bin halt von Haus aus kein Zahlentheoretiker. Na OK, hier die einfacher verdauliche Variante: $\begin{eqnarray} M \end{eqnarray}$ sei wieder die Menge der zu $\begin{eqnarray} m \end{eqnarray}$ teilerfremden Zahlen aus $\begin{eqnarray} \{1,2,\ldots,m\} \end{eqnarray}$ . Zu jedem $\begin{eqnarray} r\in M \end{eqnarray}$ gibt es nun ein eindeutiges Inverses $\begin{eqnarray} r'\in M \end{eqnarray}$ , also mit der Eigenschaft $\begin{eqnarray} rr'\equiv 1\mod m \end{eqnarray}$ . Zu zwei verschiedenen $\begin{eqnarray} r_1,r_2\in M \end{eqnarray}$ gehören auch zwei verschiedene Inverse $\begin{eqnarray} r_1',r_2'\in M \end{eqnarray}$ . Wenn also $\begin{eqnarray} r \end{eqnarray}$ die gesamte Menge $\begin{eqnarray} M \end{eqnarray}$ durchläuft, dann durchläuft auch $\begin{eqnarray} r' \end{eqnarray}$ die gesamte Menge $\begin{eqnarray} M \end{eqnarray}$ , wenn auch i.a. in völlig anderer Reihenfolge. Also gilt $\begin{eqnarray} \left(\prod\limits_{r\in M} r\right)^2 = \left(\prod\limits_{r\in M} r\right) \cdot \left(\prod\limits_{r'\in M} r'\right) = \prod\limits_{r\in M} (rr') \equiv 1\mod m \end{eqnarray}$
Anzeige

18.06.2005, 22:30	heiko	Auf diesen Beitrag antworten »
ok, danke auch wenn du keine Zahlentheoretiker bist, machste das echt gut ;-) mir hat die erste Variante so auch gut gefallen und es ist ja auch nicht verkehrt, wenn man zwei Wege kennt... Also noch nen schoenen Abend!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »