n mod 10 = n^5 mod 10 < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Zeigen Sie, dass $n$ und [mm] $n^5$ [/mm] in der Dezimaldarstellung in der letzten Ziffer überinstimmen.
Benutzen Sie: [mm] $n^p \equiv [/mm] n [mm] (\mod [/mm] p)$ für [mm] $n\in\mathbb{N}$ [/mm] und $p$ prim. |
Hallo,
Also $n$ und [mm] n^5 [/mm] sollen in der Dezimaldarstellung in der letzten Ziffer überinstimmen bedeutet ja: $n [mm] \mod [/mm] 10 [mm] \equiv n^5 \mod [/mm] 10$
Mir ist nun nicht ganz klar, wie ich das zeigen kann. Wenn ich oben für $p=5$ wähle, habe ich zwar [mm] n^5 [/mm] aber ja nicht [mm] $\mod [/mm] 10$, ebenso kann ich ja nicht $p=10$ wählen, wegen [mm] $10\not= [/mm] prim$
Wer kann helfen?
Danke, viele Grüße
Patrick
|
|
| |
|
Hallo XPatrickX,
> Zeigen Sie, dass [mm]n[/mm] und [mm]n^5[/mm] in der Dezimaldarstellung in der
> letzten Ziffer überinstimmen.
>
> Benutzen Sie: [mm]n^p \equiv n (\mod p)[/mm] für [mm]n\in\mathbb{N}[/mm] und
> [mm]p[/mm] prim.
> Hallo,
>
> Also [mm]n[/mm] und [mm]n^5[/mm] sollen in der Dezimaldarstellung in der
> letzten Ziffer überinstimmen bedeutet ja: [mm]n \mod 10 \equiv n^5 \mod 10[/mm]
>
> Mir ist nun nicht ganz klar, wie ich das zeigen kann. Wenn
> ich oben für [mm]p=5[/mm] wähle, habe ich zwar [mm]n^5[/mm] aber ja nicht
> [mm]\mod 10[/mm], ebenso kann ich ja nicht [mm]p=10[/mm] wählen, wegen
> [mm]10\not= prim[/mm]
>
> Wer kann helfen?
Setze hier [mm]n=a_{1}*10+a_{0}[/mm]
wobei [mm]a_{1} \in \IN[/mm]
und [mm]0 \le a_{0} \le 9, \ a_{0} \in \IN_{0}[/mm]
Dann läßt sich das Problem auf die Behauptung
[mm]a_{0}^{5} \equiv a_{0} \ \left(10\right)[/mm]
reduzieren.
An dieser Stelle hilft der ![[]](/images/popup.gif) kleine Fermat weiter.
>
> Danke, viele Grüße
> Patrick
Gruß
MathePower
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:09 Di 07.07.2009 | | Autor: | felixf |
Hallo!
> Setze hier [mm]n=a_{1}*10+a_{0}[/mm]
>
> wobei [mm]a_{1} \in \IN[/mm]
> und [mm]0 \le a_{0} \le 9, \ a_{0} \in \IN_{0}[/mm]
>
> Dann läßt sich das Problem auf die Behauptung
>
> [mm]a_{0}^{5} \equiv a_{0} \ \left(10\right)[/mm]
>
> reduzieren.
Das braucht man gar nicht, kann man aber machen :)
> An dieser Stelle hilft der
> kleine Fermat
> weiter.
Alternativ: Chinesischer Restsatz und den Tipp aus der Aufgabenstellung.
LG Felix
|
|
|
| |
|
Hallo Felix,
>
> Alternativ: Chinesischer Restsatz und den Tipp aus der
> Aufgabenstellung.
>
Kannst du das ein bisschen genauer erläutern, wie du das meinst?
Danke!
Viele Grüße Patrick
> LG Felix
>
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:35 So 12.07.2009 | | Autor: | felixf |
Hallo Patrick,
> > Alternativ: Chinesischer Restsatz und den Tipp aus der
> > Aufgabenstellung.
> >
>
> Kannst du das ein bisschen genauer erläutern, wie du das
> meinst?
> Danke!
Nun, nach dem Chinesischen Restsatz gilt:
[mm] $a^5 \equiv [/mm] a [mm] \pmod{10} \Longleftrightarrow a^5 \equiv [/mm] a [mm] \pmod{2} \wedge a^5 \equiv [/mm] a [mm] \pmod{5}$
[/mm]
Du musst also einmal [mm] $a^5 \equiv [/mm] a [mm] \pmod{2}$ [/mm] zeigen, und einmal [mm] $a^5 \equiv [/mm] a [mm] \pmod{5}$. [/mm] Fuer's zweite benutzt du den Hinweis aus der Aufgabenstellung, fuer's erste ist [mm] $a^5 [/mm] - a = a [mm] \cdot (a^4 [/mm] - 1)$, und das muss durch 2 teilbar sein. Mach z.B. eine Fallunterscheidung $a$ gerade / $a$ ungerade.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:54 Di 14.07.2009 | | Autor: | XPatrickX |
Dankeschön! Das folgt ja dann wirklich direkt aus dem chin. Restsatz.
Für den ersten Teil könnte man übrigens auch [mm] a^5-a [/mm] zerlegen in [mm] a(a-1)(a+1)(a^2+1) [/mm] dann sieht man direkt das der Ausdruck durch 2 teilbar ist.
Viele Grüße
|
|
|
| |
|
Hallo,
>
> Setze hier [mm]n=a_{1}*10+a_{0}[/mm]
>
> wobei [mm]a_{1} \in \IN[/mm]
> und [mm]0 \le a_{0} \le 9, \ a_{0} \in \IN_{0}[/mm]
>
> Dann läßt sich das Problem auf die Behauptung
>
> [mm]a_{0}^{5} \equiv a_{0} \ \left(10\right)[/mm]
>
> reduzieren.
>
> An dieser Stelle hilft der
> kleine Fermat
> weiter.
>
Könnte man das dann so lösen:
[mm] $a_0^{\phi(10)}=a_0^4=1\mod [/mm] 10$
[mm] $\gdw \; a_0^5 [/mm] = [mm] a_0 \mod [/mm] 10$
Warum muss man den Zwischenschritt über die Zerlegung machen? Kann man die ganze Argumentation nicht direkt mit n führen?
Danke,
Gruß Patrick
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:38 So 12.07.2009 | | Autor: | felixf |
Hallo!
> > Setze hier [mm]n=a_{1}*10+a_{0}[/mm]
> >
> > wobei [mm]a_{1} \in \IN[/mm]
> > und [mm]0 \le a_{0} \le 9, \ a_{0} \in \IN_{0}[/mm]
> >
> > Dann läßt sich das Problem auf die Behauptung
> >
> > [mm]a_{0}^{5} \equiv a_{0} \ \left(10\right)[/mm]
> >
> > reduzieren.
> >
> > An dieser Stelle hilft der
> >
> kleine Fermat
> > weiter.
> >
>
> Könnte man das dann so lösen:
>
> [mm]a_0^{\phi(10)}=a_0^4=1\mod 10[/mm]
> [mm]\gdw \; a_0^5 = a_0 \mod 10[/mm]
Nein, das stimmt naemlich nicht. Fuer [mm] $a_0 [/mm] = 0$ gilt zwar [mm] $a_0^5 [/mm] = [mm] a_0$, [/mm] aber nicht [mm] $a_0^4 \equiv [/mm] 1 [mm] \pmod{10}$.
[/mm]
Mach eine Fallunterscheidung [mm] $a_0 \equiv [/mm] 0 [mm] \pmod{10}$ [/mm] und [mm] $a_0 \not\equiv [/mm] 0 [mm] \pmod{10}$.
[/mm]
> Warum muss man den Zwischenschritt über die Zerlegung
> machen? Kann man die ganze Argumentation nicht direkt mit n
> führen?
Ja, man kann das direkt machen, die Zerlegung braucht man nicht.
LG Felix
|
|
|
|
