arithmetik

16.11.2007, 08:04

guest222

arithmetik

also, hab da ein paar kurze fragen:
1)Begründe: wenn x*a+y*b eine Vielfachensumme des ggT(a,b) ist, dann ist auch

$\begin{eqnarray*} (x-\frac{t}{ggT(a,b)}*b)*a + (y+ \frac{t}{ggT(a,b)}*a)*b (t \in Z) \end{eqnarray*}$

eine Vielfachensumme des ggT(a,b).

hat da einer nen Tip? mir fehlt jeder Ansatz..

2)Jede natürliche Zahl ist in der Form 17x+4y mit ganzen Zahlen x,y darstellbar. Nun soll untersucht werden, welche natürlichen Zahlen in dieser Form mit nicht-negativen Werten x,y darstellbar sind.
a) zeige, dass 47 nicht als $\begin{eqnarray*} 17x+4y /mit /x,y \in \mathbb N _0 \end{eqnarray*}$ darstellbar ist, dass aber 48 eine solche Dartsellung besitzt.
Dazu hab ich einfach 17x+4y=47 bzw =48 gesetzt, doch wenn man dann nach x oder y auflöst fallen x und y weg und ich hab dann 47=47 raus. hab ich irgendwas vergessen in die gleichung einzufügen?

3) drei hier reinzustellen ist mir fast peinlich, aber ich steh total auf dem schlauch...
es gibt Theaterkarten zu 7€ und zu 12€. Jemand kauft Karten für genau 100€. Wie viele Karten von jeder der beiden Sorten hat er gekauft?
meine Gleichung 7x+12y=100 stellt dieselbe problematik dar wie bei 2 und ich komm einfach nicht drauf, wie man das anders umstellen soll. auch der hinweis, dass für eine ganze zahl t auch $\begin{eqnarray*} x_0+tb, y_0-ta \end{eqnarray*}$ eine Lösung der gleichung ist, bringt mir nix.
hat einer vielleicht einen ansatz zu einer der sachen??

16.11.2007, 10:21

Auf diesen Beitrag antworten »

Zitat:

Original von guest222
wenn x*a+y*b eine Vielfachensumme des ggT(a,b)

Ich kann mit dem Begriff "Vielfachensumme einer Zahl" nichts anfangen - der ggT ist ja nur eine Zahl. Kannst du den Begriff bitte mal erklären?

Festzustellen ist, dass $\begin{eqnarray*} xa+yb \end{eqnarray*}$ stets ein Vielfaches von ggT(a,b) ist, dafür etwa braucht es kein "wenn".

Zitat:

Original von guest222
2)Jede natürliche Zahl ist in der Form 17x+4y mit ganzen Zahlen x,y darstellbar. Nun soll untersucht werden, welche natürlichen Zahlen in dieser Form mit nicht-negativen Werten x,y darstellbar sind.
a) zeige, dass 47 nicht als $\begin{eqnarray*} 17x+4y /mit /x,y \in \mathbb N _0 \end{eqnarray*}$ darstellbar ist, dass aber 48 eine solche Dartsellung besitzt.

Die Darstellung für 48 gibt man einfach an. Die Unmöglichkeit der Darstellung für 47 haben wir hier schon mal andiskutiert. Auch wenn der dortige Fragesteller das Interesse verloren hatte, kann man da anknüpfen.

Zitat:

Original von guest222
meine Gleichung 7x+12y=100 stellt dieselbe problematik dar wie bei 2 und ich komm einfach nicht drauf, wie man das anders umstellen soll.

Das ist eine der einfachsten Diophantischen Gleichungen, die es gibt - habt ihr für sowas denn überhaupt keine Beispiele betrachtet? Nun gut: Eine Standardlösungsmethode (im vorliegenden Fall nicht unbedingt die kürzeste) ist erstmal die Gewinnung einer Lösung von

$\begin{eqnarray*} 7x' +12y' = \operatorname{ggT}(7,12) = 1 \end{eqnarray*}$

mit dem EEA (Erweiterter Euklidischer Algorithnmus). Dann hast du durch $\begin{eqnarray*} x_0=100x',y_0=100y' \end{eqnarray*}$ schon mal eine ganzzahlige Lösung deiner Gleichung $\begin{eqnarray*} 7x +12y = 100 \end{eqnarray*}$ . Daraus kannst du nun alle ganzzahligen Lösungen $\begin{eqnarray*} (x,y) \end{eqnarray*}$ gemäß $\begin{eqnarray*} x=x_0+12t,y=y_0-7t \end{eqnarray*}$ mit Scharparameter $\begin{eqnarray*} t\in\mathbb{Z} \end{eqnarray*}$ gewinnen - das meinte der Hinweis. Nun musst du eben ein solches $\begin{eqnarray*} t \end{eqnarray*}$ finden, so dass beide Werte $\begin{eqnarray*} x,y \end{eqnarray*}$ nicht nur ganzzahlig, sondern sogar nichtnegativ sind!

16.11.2007, 11:01

guest 222

Auf diesen Beitrag antworten »

Tja, also mit dem erklären ist das bei mir so ne Sache ;-)
Laut Script (ich zitiere mal kurz) kann man durch Rückwärtseinsetzten im euklidischen Algorithmus eine Darstellung von ggT (a,b) in der Form xa+yb mit ganzen zahlen x,y erhalten. Eine solche Darstellung nennt man Vielafachensumme von a und b. es gilt also der folgende Satz:
Für alle a,b $\begin{eqnarray*} \in \mathbb N \end{eqnarray*}$ existieren ganze Zahlen x,y mit ggT(a,b)= xa+yb. Diese Zahlen sind nicht eindeutig bestimmt.
Soweit die Theorie. Als Beispiel ist ja ggT(741,1001)=13
Löst man den euklidischen Algorithmus dann quasi rückwärts auf 13=39-1*
Etc. (Hab das vollständig hier liegen, wollte aber nicht alles aufschreiben- falls das Beispiel aber unklar sein sollte schreib ich den euklidischen Algorithmus und das „Rückwärtsverfahren“ vollständig auf)
Daraus ergibt sich dann irgendwann: 20*1001-27*741=13, als eine mögliche Vielfachensummendarstellung. Frag mich nicht was einem das nützen soll…
Was das „wenn“ betrifft- es handelt sich um die Abschrift unseres Übungszettels- denk mal der prof hat sich da schon was bei gedacht.

Zu 2:
Super hab ich gar nicht geshen- damit wär der erste Teil erledigt;-) nur bei 47 hab ich genau wie mein vodermann keinen plan. Teilerfremd sind zahlen doch, wenn der ggT=1 ist, also z.B alle primzahlen –richtig?

Zu3:
Nein leider keine beispiele, daher die frage.
Ich geh jetzt ganz schrittweise vor- ohne jetzt auch noch zu fragen was zum teufel Diophantischen Gleichungen und Scharparameter sind ;-)
Also, die striche über x und y bedeuten nichts anderes als das man das von x unterscheiden kann- sozusagen ne variante von x –oder?
Und was ist mit $\begin{eqnarray*} x_0 \end{eqnarray*}$ ?

So, auf jeden Fall schonmal nen mega Dank für die schnelle hilfe!

16.11.2007, 11:12

Auf diesen Beitrag antworten »

Ich ahne jetzt, was du bei 1) meinst. Ich würde es exakter so formulieren - mal etwas zu ausführlich des besseren Verständnisses wegen:

Zitat:

Für die ganzen Zahlen $\begin{eqnarray*} a,b,c \end{eqnarray*}$ mit $\begin{eqnarray*} a\neq 0,b\neq 0 \end{eqnarray*}$ wird die Diophantische Gleichung $\begin{eqnarray*} xa+yb = c \end{eqnarray*}$ betrachtet.
Diese Gleichung ist genau dann lösbar, falls $\begin{eqnarray*} c \end{eqnarray*}$ ein Vielfaches von $\begin{eqnarray*} \operatorname{ggT}(a,b) \end{eqnarray*}$ ist.
In diesem Fall gilt für eine Lösung $\begin{eqnarray*} (x,y) \end{eqnarray*}$ dieser Gleichung auch

$\begin{eqnarray*} \left( x - \frac{b}{\operatorname{ggT}(a,b)}t \right)\cdot a + \left( y + \frac{a}{\operatorname{ggT}(a,b)}t \right)\cdot b = c \end{eqnarray*}$ für alle $\begin{eqnarray*} t\in\mathbb{Z} \end{eqnarray*}$ ,

d.h., auch die Paare $\begin{eqnarray*} \left( x - \frac{b}{\operatorname{ggT}(a,b)}t , y + \frac{a}{\operatorname{ggT}(a,b)}t \right) \end{eqnarray*}$ sind Lösung dieser Diophantischen Gleichung.

Umgekehrt kann man sogar sagen, dass sämtliche Lösungen dieser Gleichung sich in der letztgenannten Art darstellen lassen - aber das gehört nicht mehr zu der Aufgabe. Augenzwinkern

P.S.: Diophantische Gleichung heißt nur, dass es ausschließlich um ganzzahlige Lösungen x,y geht, also nicht etwa beliebig reelle ...

EDIT: Tippfehler in der Formel korrigiert.

16.11.2007, 11:22

guest 222

Auf diesen Beitrag antworten »

thanx, man lernt doch nie aus ;-)

Neue Frage »

Antworten »

arithmetik

Verwandte Themen