Division von n durch p mit Rest r < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:02 Sa 15.05.2004 | | Autor: | Frosty |
Hallo,
könnte mir jemand bei dieser Aufgabe helfen? Ich habe es schon durch Induktion, Gegenbeweise und direkte Beweise probiert, bin aber zu keinem Ergebnis gekommen.
Sei p Element der natürlichen Zahlen ohne Null. Zeige:
a) Für jedes n Element der natürlichen Zahlen gibt es q, r Element der natürlichen Zahlen mit n = qp + r, wobei r strikt kleiner als p ist.
b) q, r aus a) sind eindeutig bestimmt.
Ich habe schon sehr lange an dieser Aufgabe rumprobiert, kann aber einfach keinen Ansatz finden.
Dankbar für jede Hilfe
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:38 So 16.05.2004 | | Autor: | Frosty |
@marc: Vielen, vielen Dank für Deine Hilfe. Da wäre ich ja nie drauf gekommen. Der entwprechende Hinweis war, dass r auch gleich n - p. Und bei b) hatte ich mir das schon so ähnlich gedacht, konnte es aber nicht so schön zeigen wie Du. Nochmals Danke.
@Paulus: Ich habe diese Seite und onlinemathe.de erst Samstagmorgen entdeckt und hatte Stress, weil meine Mutter mit mir weg wollte. Da konnte ich den "Codex" nicht ganz durchlesen. Wird nicht mehr vorkommen :)
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 04:32 So 16.05.2004 | | Autor: | Marc |
Hallo Frosty,
willkommen im MatheRaum! 
Da mich deine Frage gereizt hat, weil sie so elementarer Natur ist, habe ich mich mal an ihr versucht.
> könnte mir jemand bei dieser Aufgabe helfen? Ich habe es
> schon durch Induktion, Gegenbeweise und direkte Beweise
> probiert, bin aber zu keinem Ergebnis gekommen.
>
> Sei p Element der natürlichen Zahlen ohne Null. Zeige:
> a) Für jedes n Element der natürlichen Zahlen gibt es q, r
> Element der natürlichen Zahlen mit n = qp + r, wobei r
> strikt kleiner als p ist.
Ich zeige es per Induktion, und nutze dabei aus, dass eine Zahl n bei der Division durch p denselben Rest läßt wie die Zahl n-p:
Induktionsanfang: Für n=1 ist die Sache klar (man wähle q=0 und r=1).
Induktionsschritt [mm] $n\to [/mm] n+1$: Die Behauptung sei wahr für alle [mm] $k\le [/mm] n$.
1. Fall: $n<p$
Wähle q=0 und r=n.
2. Fall: [mm] $n\ge [/mm] p$
Nach Induktionsvoraussetzung existiert für $n-p$ ein $q'$ und $r'$, so dass
$n-p=q'*p+r'$
[mm] $\gdw [/mm] n=q'*p+r'+p$
[mm] $\gdw n=\underbrace{(q'+1)}_{=:q}*p+\underbrace{r'}_{=:r}$ $\Box$
[/mm]
> b) q, r aus a) sind eindeutig bestimmt.
Die Eindeutigkeit folgt auf klassische Art und Weise, indem man sich zwei Lösungen ansieht und dann einsieht, dass es dieselbe sein muß:
Sei [mm] $n=q_1*p+r_1$ [/mm] und [mm] $n=q_2*p+r_2$ [/mm] und [mm] $r_1,r_2
Dann ist doch $0 = [mm] n-n=q_1*p+r_1-(q_2*p+r_2)=(q_1-q_2)*p+(r_1-r_2)$, [/mm] also [mm] $(q_1-q_2)*p=-(r_1-r_2)$.
[/mm]
Das heißt aber, dass $p$ ein Teiler von [mm] $|-(r_1-r_2)|$ [/mm] ist.
Nun ist aber [mm] $|-(r_1-r_2)|=|r_2-r_1|
$p$ kann eine Zahl, die kleiner als $p$ selbst ist, aber nur teilen, wenn diese Zahl $0$ ist, also [mm] $r_2-r_1=0\ \gdw\ r_2=r_1$.
[/mm]
Die obige Gleichung [mm] $(q_1-q_2)*p=-(r_1-r_2)$ [/mm] vereinfacht sich so zu [mm] $(q_1-q_2)*p=0$, [/mm] woraus auch [mm] $q_1=q_2$ [/mm] folgt. [mm] $\Box$
[/mm]
> Ich habe schon sehr lange an dieser Aufgabe rumprobiert,
> kann aber einfach keinen Ansatz finden.
Jetzt habe ich leider schon alles verraten, aber die Lösung sollte auch eher für mich sein.
Viele Grüße,
Marc
|
|
|
|
![[]](/images/popup.gif){kind=small}
http://www.onlinemathe.de/read.php?topicid=1000001037&read=1&kat=Studium&PHPSESSID=5f0bd267c0d7b83fae113a3f8843e3e7