Matroids Matheplanet Forum Index
Moderiert von Wauzi
Teilbarkeit » Kongruenzen » Übungen mit Kongruenzen
Autor
Universität/Hochschule J Übungen mit Kongruenzen
OliverFuchs
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 25.03.2020
Mitteilungen: 191
Wohnort: Wien, Österreich
  Themenstart: 2021-08-24

\(\begingroup\)\(\newcommand{\al}{\alpha} \newcommand{\be}{\beta} \newcommand{\bs}{\backslash} \newcommand{\ga}{\gamma} \newcommand{\de}{\delta} \newcommand{\ep}{\varepsilon} \newcommand{\ze}{\zeta} \newcommand{\et}{\eta} \newcommand{\io}{\iota} \newcommand{\ka}{\kappa} \newcommand{\la}{\lambda} \newcommand{\rh}{\rho} \newcommand{\si}{\sigma} \newcommand{\ta}{\tau} \newcommand{\ph}{\varphi} \newcommand{\ch}{\chi} \newcommand{\ps}{\psi} \newcommand{\om}{\omega} \newcommand{\Ga}{\Gamma} \newcommand{\De}{\Delta} \newcommand{\Th}{\Theta} \newcommand{\La}{\Lambda} \newcommand{\Si}{\Sigma} \newcommand{\Ph}{\Phi} \newcommand{\Ps}{\Psi} \newcommand{\Om}{\Omega} \newcommand{\NN}{\mathbb N} \newcommand{\ZZ}{\mathbb Z} \newcommand{\QQ}{\mathbb Q} \newcommand{\RR}{\mathbb R} \newcommand{\CC}{\mathbb C} \newcommand{\HH}{\mathbb H} \newcommand{\DD}{\mathbb D} \newcommand{\TT}{\mathbb T} \newcommand{\KK}{{\mathbb K}} \newcommand{\oo}{{\infty}} \newcommand{\PP}{\mathbb P} \newcommand{\BB}{\mathbb B} \newcommand{\MM}{\mathbb M} \newcommand{\alt}{\operatorname{alt}} \newcommand{\dom}{\operatorname{Dom}} \newcommand{\ceil}{\operatorname{ceil}} \newcommand{\Diff}{\operatorname{Diff}} \newcommand{\ev}{\operatorname{ev}} \newcommand{\floor}{\operatorname{floor}} \newcommand{\ggT}{\operatorname{ggT}} \newcommand{\grad}{\operatorname{grad}} \newcommand{\graph}{\operatorname{Graph}} \newcommand{\im}{\operatorname{Im}} \newcommand{\id}{\operatorname{id}} \newcommand{\incl}{\operatorname{incl}} \newcommand{\kgV}{\operatorname{kgV}} \newcommand{\li}{\operatorname{li}} \newcommand{\ord}{\operatorname{ord}} \newcommand{\ptp}{\operatorname{ptp}} \newcommand{\rang}{\operatorname{rang}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\sym}{\operatorname{sym}} \newcommand{\trg}{\operatorname{Trg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\card}{\operatorname{card}} \newcommand{\R}{\Rightarrow} \newcommand{\L}{\Leftarrow} \newcommand{\gdw}{\Leftrightarrow} \) Hallo, Wieder schlage ich mich mit Übungsbeispielen aus der Zahlentheorie herum. Diesmal lautet die Angabe wie folgt: Jedes $x\in \ZZ$ erfüllt mindestens eine der folgenden Kongruenzen: Beispiel. $x\equiv 0 \mod 2, x\equiv 1\mod 4, x\equiv 1\mod 6$ $x\equiv 0\mod 3, x\equiv 1\mod 5, x\equiv -1\mod 12$ Beweis: Da ich in diesen Sachen keine Übung habe und sie für mich neu sind, habe ich mich einfach durchgeschlagen. 1) Die erste Kongruenz ist $x\equiv 0\mod 2$. Das heißt, die geraden $x=2k$ erfüllen diese Kongruenz. Die $x=2k+1$ erfüllen diese Kongruenz nicht und bleiben über. 2) Dann kommt $x\equiv 1\mod 6$. Ich setze ein $(2k+1)\equiv 1\mod 6$. und erhalte für ein $s\in\ZZ$, $2k+1=1+6s,$. Also $2k=6s\> k=3s$. Das ist die Bedingung dafür, dass diese Kongruenz erfüllt ist. Also ist sie für die $x=2k+1=2(3s)+1=6s+1$ erfüllt. Das sind auch ungerade Zahlen. Welche ungeraden Zahlen bleiben dann über ? Das sind die $x\in\ZZ$ wo $x=2k+1$ und $x\not=6s+1$. Ich kann die Teilbarkeit durch $6$ betrachten. Dann zerfällt $\ZZ$ in $6s,6s+1,6s+2,6s+3,6s+4,6s+5$. Da die erste Bedingung sagt, dass $x$ ungerade sein muss, bleiben nur die Fälle $6s+1,6s+3,6s+5$ über. Der Fall $6s+1$ wird durch die zweite Bedingung ausgeschlossen, also bleiben die $x=6s+3$ und $x=6s+5$ über. 3) Jetzt kommt die Kongruenz $x\equiv 1\mod 6$. Zuerst prüfe ich $6s+3\equiv 1\mod 6$. Diese Kongruenz ist genau dann erfüllt, wenn es ein $t\in\ZZ$ gibt, mit $6s+3=1+6t\gdw 6s=6t-2\gdw 3s=3t-1$. Das setze ich bei $x$ ein und erhalte $x=6s+3=2(3s)+3=2(3t-1)+3= 6t-2+3=6t+1$. Damit erfüllen die $x$ von dieser Form die Kongruenz. Jetzt rechne ich $6s+5\equiv 1\mod 6\gdw \exists t\in\ZZ: 6s+5=6t+1\gdw \exists t\in\ZZ: 6s=6t-4\gdw \exists t\in\ZZ: 3s=3t-2$. Das setze ich ein und erhalte, dass $x=6s+5=2(3s)+5=2(3t-2)+5=6t-4+5=6t+1$. Das sind also wieder die gleichen $x$. Ich habe keinen Informationsgewinn. Welche $x$ die in der Vorausscheidung durch gekommen sind, erfüllen also diese Kongruenz nicht. Dazu bemerke ich, dass jedes $x\in\ZZ$ in der Form $6t,6t+1,6t+2,6t+3,6t+4,6t+5$ geschrieben werden kann. Was habe ich bisher gezeigt. In 1)\&2) habe ich gezeigt, dass die $x$ der Form $6s+3$ und $6s+5$ keine der beiden Kongruenzen erfüllen. Jetzt habe ich geprüft, ob eines der beiden $x$ die Kongruenz $x\equiv 1\mod 6$ erfüllen würde. Dabei habe ich fest gestellt, dass das nur der Fall ist, wenn die Zusatzbedingung $x=6s+1$ auch erfüllt ist. Diese Fälle schließen aber einander aus. Also liefert diese Kongruenz an dieser Stelle keine weitere Einschränkung. Keine der noch in Frage kommenden $x$ erfüllen sie. ad 4) Ich sehe mir $x\equiv 0\mod 3$ an und prüfe die $x$ die nach 1)\&2) noch über geblieben sind. Das heißt es muss ein $k\in\ZZ$ geben mit, $6s+3\equiv 0\mod 3\gdw 6s+3=3k\gdw 2s=k-1$. Das setze ich ein und erhalte $x=6s+3=3(2s)+3=3(k-1)+3= 3k-3+3=3k$.Es gilt aber $x=6s+3=3(2s+1)$. Also sind mit $k=2s+1$ alle diese $x$ von dieser Form und erfüllen die Kongruenz. Das könnte ich auch so rechnen. $6s+3\equiv 0\mod 3\gdw 3(2s+1)\equiv 0\mod 3$. Da $3\equiv 0\mod 3$ ist, ist das für alle diese $x$ erfüllt. Dann kommt $6s+5\equiv 0\mod 3$. Dann gibt es ein $k\in\ZZ$ mit $6s+5=3k\gdw 6s=3k-5$. Ich setze ein und erhalte $x=6s+5=(3k-5)+5=3k$. Das ist aber klar. Das sagt ja nur, das $3\vert x$ gelten muss. Das kann man auch direkt aus der Kongruenz ablesen. Es soll aber $3\vert 6s+5$ gelten, wobei $3\vert 6s$ gilt. Daraus würde $3\vert 5$ folgen, was falsch ist. Daher bleiben die $6s+5$ über. Diese Kongruenz hat also eine weiter Einschränkung gebracht. ad 5) Ich betrachte $x\equiv 1\mod 5$. Also muss ich $6s+5\equiv 1\mod 5\gdw 6s\equiv 1\mod 5$ untersuchen. Es muss also ein $u\in\ZZ$ geben mit $6s=5u+1$. Eingesetzt ergibt das $x=6s+5=(5u+1)+5=5u+6$. Hier hat sich also die Einschränkende Bedingung für die $x$ etwas gewandelt. ad 6} Ich betrachte $x\equiv -1\mod 12$ für diese $x$. Das ergibt $5u+6\equiv -1\mod 12$. Es muss also ein $w\in\ZZ$ geben mit $5u+6=12w-1\gdw 5u=12w-5$. Ich setze ein und erhalte. $x=5u+6=(12w-5)+6=12w+1$. Das sind nun die $x$ die noch keine Kongruenz erfüllen. Nun haben wir die Kongruenz 3) eigentlich noch nicht verwendet. Daher versuche ich das einmal und erhalte. ad 3) $x\equiv 1\mod 6$. Das ergibt $12w+1\equiv 1\mod 6\gdw 12w\equiv 0\mod 6$ und das ist für alle $w$ wahr.\\ Damit bleiben keine $x$ über und die Aussage ist bewiesen. $\square$ Dazu habe ich zwei Fragen: 1. Habe ich richtig gerechnet? 2. Gibt es einen einfacheren Lösungsweg? Danke lg Oliver🙂\(\endgroup\)


   Profil
Kuestenkind
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 12.04.2016
Mitteilungen: 2430
  Beitrag No.1, eingetragen 2021-08-24

Huhu Oliver, ich habe deinen Text nicht wirklich zu Ende gelesen (ich habe wenig Zeit und fand es etwas anstrengend). Systematischer solltest du nachweisen, dass jede Restklasse Modulo 12 (kgV der Moduln) mindestens einer Kongruenz deines Systems genügt. Als Beispiel können wir die Restklasse \([7]\) uns anschauen. Sei also \(x\in [7]\). Dann gilt nach Voraussetzung \(x\equiv7\pmod {12}\), was sich zu \(12\mid x-7\) übersetzt. Offensichtlich gilt aber auch \(6\mid 12\). Damit: \(6\mid 12\, \wedge \, 12 \mid x-7 \Rightarrow 6\mid x-7\). Wir haben also die Transitivität der Teilerrelation ausgenutzt. \(6\mid x-7\) übersetzt sich nun wieder aber \(x\equiv 7\equiv 1 \pmod 6\). Gruß, Küstenkind edit: Ich sehe nun erst, dass dort auch noch \(x\equiv 1 \pmod 5\) steht. Das ist überflüssig. Wenn man das nicht sieht, müsste man natürlich auf das kgV 60 gehen. Das wäre etwas mehr Schreibarbeit, aber auch kein Problem. Solch ein Kongruenzsystem nennt sich übrigens covering system - siehe für das reduzierte System auch dort.


   Profil
OliverFuchs hat die Antworten auf ihre/seine Frage gesehen.
OliverFuchs hat selbst das Ok-Häkchen gesetzt.
OliverFuchs wird per Mail über neue Antworten informiert.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]