Teiler bestimmen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:26 Fr 05.01.2007 | | Autor: | Denny22 |
| Aufgabe | Seien
[mm] $n_1=2^{1769}+1$ [/mm] und [mm] $n_2=2^{1769}-1$
[/mm]
Bestimmen Sie jeweils einen Teiler $t$ mit [mm] $1 |
Hallo an alle,
mir fällt gerade nicht mehr ein wie ich einen solchen Teiler finde. wäre toll wenn mir jemand einen Tipp gäbe.
Danke und Gruß
Denny
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:51 Fr 05.01.2007 | | Autor: | felixf |
Hallo Denny!
> Seien
>
> [mm]n_1=2^{1769}+1[/mm] und [mm]n_2=2^{1769}-1[/mm]
>
> Bestimmen Sie jeweils einen Teiler [mm]t[/mm] mit [mm]1
> (Tipp: [mm]1769=29\cdot{61})[/mm]
> Hallo an alle,
>
> mir fällt gerade nicht mehr ein wie ich einen solchen
> Teiler finde. wäre toll wenn mir jemand einen Tipp gäbe.
Tja, da denkt man, dass man eine Idee hat, und es klappt doch nicht... Ich schreib das trotzdem mal auf was ich mir gedacht hab:
Also $t$ ist ja genau dann ein Teiler von [mm] $2^{1769} \pm [/mm] 1$, wenn [mm] $2^{1769} \equiv \mp [/mm] 1 [mm] \pmod{t}$ [/mm] ist. Nun muss $t$ sowieso ungerade sein (da [mm] $n_i$ [/mm] ungerade ist), womit $2$ und $t$ teilerfremd sind; also gilt [mm] $2^{\phi(t)} \equiv [/mm] 1 [mm] \pmod{t}$ [/mm] (wobei [mm] $\phi$ [/mm] die Eulersche [mm] $\phi$-Funktion [/mm] ist), und natuerlich auch [mm] $2^{n \phi(t)} \equiv [/mm] 1 [mm] \pmod{t}$ [/mm] fuer alle $n [mm] \in \IN$.
[/mm]
Tja, nur leider kann man 1769 nicht als $n [mm] \phi(t)$ [/mm] schreiben... Aber vielleicht bringt das jetzt jemand anderen auf ne Idee :)
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:27 Fr 05.01.2007 | | Autor: | statler |
Guten Tag Denny!
> Seien
>
> [mm]n_1=2^{1769}+1[/mm] und [mm]n_2=2^{1769}-1[/mm]
>
> Bestimmen Sie jeweils einen Teiler [mm]t[/mm] mit [mm]1
> (Tipp: [mm]1769=29\cdot{61})[/mm]
Das Einfache zuerst:
Es gilt [mm] 2^{29}-1|n_{2} [/mm] und ebenso [mm] 2^{61}-1|n_{2},
[/mm]
weil [mm] 2^{r}-1|2^{rs}-1 [/mm] gilt.
Über das Schwierige muß ich auch noch mal nachdenken.
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:38 Fr 05.01.2007 | | Autor: | statler |
Guten Tag Denny!
>
> > Seien
> >
> > [mm]n_1=2^{1769}+1[/mm] und [mm]n_2=2^{1769}-1[/mm]
> >
> > Bestimmen Sie jeweils einen Teiler [mm]t[/mm] mit [mm]1
> > (Tipp: [mm]1769=29\cdot{61})[/mm]
>
> Das Einfache zuerst:
>
> Es gilt [mm]2^{29}-1|n_{2}[/mm] und ebenso [mm]2^{61}-1|n_{2},[/mm]
>
> weil [mm]2^{r}-1|2^{rs}-1[/mm] gilt.
>
> Über das Schwierige muß ich auch noch mal nachdenken.
Wenn r und s ungerade sind, gilt doch auch
[mm]2^{r}+1|2^{rs}+1[/mm], oder?
Gruß aus HH-Harburg (zum 2.)
Dieter
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:40 Fr 05.01.2007 | | Autor: | felixf |
Moin Dieter!
> Wenn r und s ungerade sind, gilt doch auch
> [mm]2^{r}+1|2^{rs}+1[/mm], oder?
Es reicht schon, dass $s$ ungerade ist, da [mm] $X^{rs} [/mm] + 1 = [mm] (X^s [/mm] - [mm] X^{s-1}) (X^r [/mm] + 1) + [mm] (X^{r (s - 2)} [/mm] + 1)$ ist. Per Induktion folgt also, dass [mm] $X^{rs} [/mm] + 1 = p [mm] \cdot (X^r [/mm] + 1)$ ist fuer ein Polynom $p [mm] \in \IZ[X]$. [/mm]
LG Felix
|
|
|
|
