Bijektive Modulo Funktion

16.12.2020, 18:40	MasterWizz	Auf diesen Beitrag antworten »
Bijektive Modulo Funktion Hey Leute Mich interessiert ein Zusammenhang, den ich beobachten konnte, den ich aber nicht bewiesen kriege. Könnt ihr mir bitte helfen? Seien $\begin{eqnarray} p,q\in\mathbb{N}_{\geq1} \end{eqnarray}$ teilerfremd. Die Abbildung $\begin{eqnarray} \varphi:\ \{0,1,\dots,q-1\}\rightarrow\{0,1,\dots,q-1\} \end{eqnarray}$ mit $\begin{eqnarray} m\mapsto (p\cdot m)\,\text{mod}\,q \end{eqnarray}$ ist bijektiv. Ich habe es zumindest in sofern verstanden, dass ich die Aussage so konkret formulieren konnte. Es bedeutet also, dass die Funktion $\begin{eqnarray} \varphi \end{eqnarray}$ lediglich eine Umsortierung vornimmt. Jedoch weiß ich hier nicht weiter.
16.12.2020, 19:10	HAL 9000	Auf diesen Beitrag antworten »
Versuch es doch mal mit einem indirekten Beweis, d.h., nimm an dass $\begin{eqnarray} \varphi \end{eqnarray}$ nicht injektiv oder nicht surjektiv ist (letzteres führt übrigens im vorliegenden Fall sofort zu ersterem). Mit elementaren Teilbarkeitseigenschaften kommt man damit sehr rasch zu einem Widerspruch.
16.12.2020, 19:11	Elvis	Auf diesen Beitrag antworten »
$\begin{eqnarray} pa\equiv pb\mod q\Rightarrow q\|p(a-b)\Rightarrow q\|a-b \end{eqnarray}$ ,also injektiv surjektiv ? zeige $\begin{eqnarray} \forall a\mod q \end{eqnarray}$ ex. $\begin{eqnarray} b\mod q \end{eqnarray}$ mit $\begin{eqnarray} pb\equiv a\mod q \end{eqnarray}$ man nehme $\begin{eqnarray} b\equiv p^{-1}a\mod q \end{eqnarray}$ Ich denke, das genügt.
16.12.2020, 21:14	MasterWizz	Auf diesen Beitrag antworten »
Ich musste erst mal eine Weile drüber nachdenken, aber ich hab es jetzt verstanden! Sowohl den Nachweis der Injektivität (auf indirektem Weg), als auch Elvis' direkten Beweis für die Surjektivität. Ich hab auch verstanden, dass in diesem Fall aus der Surjektivität auch die Injektivität folgt, weil $\begin{eqnarray} \varphi \end{eqnarray}$ eine Selbstabbildung mit endlich vielen Elementen in Definitionsbereich, bzw. Wertevorrat ist. Vielen lieben Dank ihr beide!!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »