Vollständige Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:45 Do 01.11.2007 | | Autor: | niandis |
| Aufgabe | (a) Es seien [mm] p,q,m\in\IN [/mm] mit p > max(q,1). Zeigen Sie: Sind p - q und p - 1 durch m teilbar, so ist [mm] p^n [/mm] - q für jedes [mm] n\in\IN [/mm] durch m teilbar. Hinweis: Führen Sie eine Induktion nach n durch.
(b) Folgern Sie: Für alle [mm] n\in\IN [/mm] ist [mm] 9^n [/mm] - 5 durch 4 teilbar |
Hallo,
ich soll oben angegebene Aufgabe lösen. Ansich denke ich, ich habe auch das Prinzip der Induktion verstanden. Allerderings fehlt mir bei der Aufgabe jegliche Idee für den Ansatz. Es sind so viele Bedingungen gegeben und ich weiß nicht, wie ich das in einer knappen Formel ausdrücken kann. Allein das "teilbar durch m" weiß ich nich, wie ich das als Formel ausdrücken kann. Kann ich das beispielsweise als [mm] (p^n [/mm] - q)*m = x , [mm] x\in\IN [/mm] schreiben? Oder gibt es da sinnvollere Möglichkeiten?
Und wie kann ich die 3 Aussagen p-q durch m teilbar, p-1 durch m teilbar und [mm] p^n [/mm] - q durch m teilbar in einer Formel kombinieren?
Ich wäre euch echt dankbar für kleine Hilfestellungen.
Lg!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
> (a) Es seien [mm]p,q,m\in\IN[/mm] mit p > max(q,1). Zeigen Sie: Sind
> p - q und p - 1 durch m teilbar, so ist [mm]p^n[/mm] - q für jedes
> [mm]n\in\IN[/mm] durch m teilbar. Hinweis: Führen Sie eine Induktion
> nach n durch.
Hallo,
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") .
Du sollst also zeigen, daß unter den vorgegebenen Bedingungen
[mm] \bruch{p^n-q}{m} [/mm] für jedes n [mm] \in \IN [/mm] eine natürliche Zahl ist.
Anders ausgedrückt: Für jedes [mm] n\in \IN [/mm] findet man ein [mm] \in \IN [/mm] mit [mm] \bruch{p^n-q}{m}=k_n.
[/mm]
Da Du Induktion verstanden hast, weißt Du, daß Du die Gültigkeit jetzt für n=1 zeigen mußt, also glaubhaft versichern, daß
[mm] \bruch{p^1-q}{m} [/mm] eine natürliche Zahl ist.
Im Induktionsschluß zeigen wir nun, daß
[mm] \bruch{p^{n+1}-q}{m} [/mm] eine natürliche Zahl ist.
Es ist
[mm] \bruch{p^{n+1}-q}{m}=\bruch{p*p^{n}-q}{m}=\bruch{((p-1)+1)p^{n}-q}{m}= [/mm] ...
und nun weiter, an geeigneter Stelle Induktionsvoraussetzung und die allgemeinen Voraussetzungen verwenden.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:47 Do 01.11.2007 | | Autor: | niandis |
Super, vielen Dank auf jeden Fall schon mal.
Wenn ich das also alles richtig verstanden habe würde meine Lösung etwa folgendermaßen aussehn:
Vorraussetzung:
p-1 und p-q sind durch m teilbar:
[mm] \bruch{p-1}{m}=k_n [/mm] und [mm] \bruch{p-q}{m}=k_m [/mm] mit [mm] k_n,k_m\in\IN
[/mm]
Annahme:
[mm] \bruch{p^n-q}{m}=k_n [/mm] mit [mm] n,k_n\in\IN
[/mm]
Anfang:
Zeige, dass dies für n=1 gilt.
[mm] \bruch{p^1-q}{m}=\bruch{p-q}{m} [/mm] laut Vorraussetzung ist p-q durch m teilbar -> gilt für n=1
Induktionsschritt:
Zeige für n+1
[mm] \bruch{p^{n+1}-q}{m}=\bruch{p*p^n-q}{m}=\bruch{((p-1)+1)*p^n-q}{m}=\bruch{(p-1)p^n+p^n-q}{m}
[/mm]
Betrachtet man den letzten Bruch, so sind alle Elemente im Zähler durch m teilbar. p-1 ist laut Vorraussetzung durch m teilbar. Das Produkt [mm] (p-1)*p^n [/mm] ist als Vielfaches von (p-1) auch durch m teilbar. Und das [mm] p^n-q [/mm] durch m teilbar ist, wurde im Lauf der Induktion gezeigt.
Ich habe noch etwas Probleme mit der mathematisch korrekten Ausformulierung. Kannst du/könnt ihr mir da vielleicht noch ein Paar Tipps geben?
|
|
|
| |
|
> Super, vielen Dank auf jeden Fall schon mal.
> Wenn ich das also alles richtig verstanden habe würde meine
> Lösung etwa folgendermaßen aussehn:
>
> Vorraussetzung:
>
> p-1 und p-q sind durch m teilbar:
Also gibt es [mm] k_1, k_2 \in \IN [/mm] mit
> [mm]\bruch{p-1}{m}=k_1[/mm] und [mm]\bruch{p-q}{m}=k_2[/mm]
>
> Annahme:
[mm] p^n-q [/mm] ist durch m teilbar, d.h. es gibt ein [mm] k_n \in \IN [/mm] mit
> [mm]\bruch{p^n-q}{m}=k_n[/mm]
>
> Anfang:
>
> Zeige, dass dies für n=1 gilt.
>
> [mm]\bruch{p^1-q}{m}=\bruch{p-q}{m}[/mm] laut Vorraussetzung ist p-q
> durch m teilbar -> gilt für n=1
>
> Induktionsschritt:
>
> Zeige für n+1
>
> [mm]\bruch{p^{n+1}-q}{m}=\bruch{p*p^n-q}{m}=\bruch{((p-1)+1)*p^n-q}{m}=\bruch{(p-1)p^n+p^n-q}{m}[/mm]
> Betrachtet man den letzten Bruch, so sind alle Elemente im
> Zähler durch m teilbar. p-1 ist laut Vorraussetzung durch m
> teilbar. Das Produkt [mm](p-1)*p^n[/mm] ist als Vielfaches von (p-1)
> auch durch m teilbar. Und das [mm]p^n-q[/mm] durch m teilbar ist,
> wurde im Lauf der Induktion gezeigt.
Du hast in der Tat alles verstanden. Das Aufschreiben ist nicht so schwer, guck:
[mm] \bruch{p^{n+1}-q}{m}=\bruch{p*p^n-q}{m}=\bruch{((p-1)+1)*p^n-q}{m}=\bruch{(p-1)p^n+p^n-q}{m}
[/mm]
[mm] =\bruch{(p-1)}{m}p^n+\bruch{p^n-q}{m}=\underbrace{k_1}_{Vorauss.}*p^n [/mm] + [mm] \underbrace{k_n}_{Ind.Vorauss.}
[/mm]
Da beide Summanden natürliche Zahlen sind, ist die Summe auch eine natürliche Zahl, womit die Behauptung bewiesen ist.
Gruß v. Angela
|
|
|
|
