Kongruenzen

01.01.2007, 17:18

Rho

Kongruenzen

Hallo,

ich habe gerade mit dem Thema Kongruenzen angefangen und bin mit der Definition

$\begin{eqnarray*} a \equiv b \ (mod \ m) :\Leftrightarrow m~|~(a-b) \end{eqnarray*}$

soweit klar gekommen, womit sollte ich nun weitermachen?

Z.B. reicht bei folgender Aufgabe mein Wissen wohl noch nicht ganz: "Zeige, dass $\begin{eqnarray*} z=43^7-87^{13} \end{eqnarray*}$ durch $\begin{eqnarray*} 44 \end{eqnarray*}$ teilbar ist."

Also muss ich $\begin{eqnarray*} z \equiv 0 \ (mod \ 44) \end{eqnarray*}$ zeigen, aber wie mache ich das? ?

01.01.2007, 17:40

sqrt(2)

Auf diesen Beitrag antworten »

Du solltest dir die Rechenregeln mal anschauen (und an ein paar Beispielen durchdenken), dann wirst du mit

$\begin{eqnarray*} 43 &\equiv& -1 \pmod{44} \\ 87 &\equiv& -1 \pmod{44} \end{eqnarray*}$

einiges anfangen können.

01.01.2007, 18:08

Rho

Auf diesen Beitrag antworten »

Wie kommst du denn auf -1?

01.01.2007, 18:13

therisen

Auf diesen Beitrag antworten »

Weil $\begin{eqnarray*} 43-(-1) \end{eqnarray*}$ und $\begin{eqnarray*} 87-(-1) \end{eqnarray*}$ durch $\begin{eqnarray*} 44 \end{eqnarray*}$ teilbar sind Augenzwinkern

01.01.2007, 18:25

Rho

Auf diesen Beitrag antworten »

Oh... stimmt. Big Laugh

Ich hatte gedacht, dass 43 und -1 durch mod geteilt ja den selben Rest lassen müssen, wie kann man das dann bei -1 feststellen?

Naja, jedenfalls wäre dann

$\begin{eqnarray*} z \equiv (-1)^7-(-1)^{13}=0 \ (mod \ 44) \end{eqnarray*}$

q.e.d. ?

01.01.2007, 18:38

therisen

Auf diesen Beitrag antworten »

Zitat:

Original von Rho
Oh... stimmt. Big Laugh

Ich hatte gedacht, dass 43 und -1 durch mod geteilt ja den selben Rest lassen müssen, wie kann man das dann bei -1 feststellen?

Naja, das folgt eben einfach aus der Definition $\begin{eqnarray*} a\equiv b \pmod n :\Leftrightarrow n|a-b \end{eqnarray*}$ .

Zitat:

Original von Rho
Naja, jedenfalls wäre dann

$\begin{eqnarray*} z \equiv (-1)^7-(-1)^{13}=0 \ (mod \ 44) \end{eqnarray*}$

q.e.d. ?

Richtig.

Gruß, therisen

01.01.2007, 18:41

sqrt(2)

Auf diesen Beitrag antworten »

Zitat:

Original von Rho
Ich hatte gedacht, dass 43 und -1 durch mod geteilt ja den selben Rest lassen müssen

Naja, das ist eben etwas schwammig. Wenn links und rechts Zahlen mit gleichen Vorzeichen stehen, dann kannst du das sehen.

Zitat:

Original von Rho
wie kann man das dann bei -1 feststellen?

In gewisser Weise lassen 43 und -1 den gleichen Rest: Wenn du sie durch 44 teilst, bekommst du die Reste 43 und -1, und die sind modulo 44 ja kongruent. (Damit man hier nicht im Kreis schließt, verwendet man eben die Definition von dir oben.)

Zitat:

Original von Rho
$\begin{eqnarray*} z \equiv (-1)^7-(-1)^{13}=0 \ (mod \ 44) \end{eqnarray*}$

q.e.d. ?

Ja.

02.01.2007, 14:14

Rho

Auf diesen Beitrag antworten »

Moin,

folgende lineare Kongruenz:

$\begin{eqnarray*} 323x \equiv 120 \ (mod \ 1001) \end{eqnarray*}$

Nach der Definition wäre das ja äquivalent zu

$\begin{eqnarray*} \Leftrightarrow 1001y=323x-120 \end{eqnarray*}$

Da hier ja nur ganzzahlige Werte in Frage kommen ist das doch quasi eine diophantische Gleichung, oder? Wie macht man nun weiter?

02.01.2007, 14:25

sqrt(2)

Auf diesen Beitrag antworten »

Wikipedia ist toll: http://de.wikipedia.org/wiki/Lineare_Diophantische_Gleichung

03.01.2007, 12:57

Auf diesen Beitrag antworten »

Kleine Frage:

Wenn ich mit dem euklidischen Algorithmus den $\begin{eqnarray*} ggT(a,b) \end{eqnarray*}$ berechnen soll, $\begin{eqnarray*} b \end{eqnarray*}$ jedoch $\begin{eqnarray*} > \end{eqnarray*}$ als $\begin{eqnarray*} a \end{eqnarray*}$ ist, dann würde ja schon mal $\begin{eqnarray*} 0 \end{eqnarray*}$ Rest $\begin{eqnarray*} b \end{eqnarray*}$ rauskommen, oder kann ich auch $\begin{eqnarray*} b:a \end{eqnarray*}$ rechnen?

z.B. $\begin{eqnarray*} ggT(297,363) \end{eqnarray*}$

03.01.2007, 12:59

Auf diesen Beitrag antworten »

Uuups, logischerweise ist $\begin{eqnarray*} ggT(a,b)=ggT(b,a) \end{eqnarray*}$ . Hammer

Neue Frage »

Antworten »

Kongruenzen

Verwandte Themen