Modulo & Satz von Fermat < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei [mm] $n_{1}=559,$ $n_{2}=561,$ $n_{3}=563.$
[/mm]
a) Berechnen Sie
[mm] $44^{n_{1}-1} \mbox{mod } n_{1}$ [/mm] Hilfsmittel: [mm] $44^{4} \mbox{mod } n_{1}=1$
[/mm]
[mm] $67^{n_{2}-1} \mbox{mod } n_{2}$ [/mm] Hilfsmittel: [mm] $67^{186} \mbox{mod } n_{2}=1$
[/mm]
[mm] $44^{n_{3}-1} \mbox{mod } n_{3}$ [/mm] Hilfsmittel: [mm] $44^{187} \mbox{mod } n_{3}=4$
[/mm]
b) Satz von Fermat ("kleiner Fermat"): Für alle $n [mm] \in \IN$ [/mm] mit $n [mm] \ge [/mm] 2$ gilt: n Primzahl gdw. für alle $a [mm] \in \{1,...,n-1\}$ [/mm] gilt [mm] $a^{n-1}\mbox{mod } [/mm] n = 1$
Für welche der Zahlen [mm] $n_{1}, n_{2}, n_{3}$ [/mm] folgt aus den obigen Ergebnissen, dass die Zahl eine Primzahl ist? Für welche folgt, dass sie keine Primzahl ist? |
Hallo,
es wäre sehr nett, wenn mir jemand erklären könnte, wie das Hilfsmittel in der a) zu verwenden ist, denn ich denke, dass man keinen Taschenrechner benutzen darf.
Bei der ersten Rechnung habe ich
[mm] $44^{558} \mbox{mod } [/mm] 559$ und als Hilfsmittel [mm] $44^{4} \mbox{mod } [/mm] 559=1$
Wie nutze ich nun aber das Hilfsmittel?
Vielen Dank für die Mühe und Unterstützung!
Gruß
el_grecco
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:49 Mi 04.05.2011 | | Autor: | rainerS |
Hallo!
> Sei [mm]n_{1}=559,[/mm] [mm]n_{2}=561,[/mm] [mm]n_{3}=563.[/mm]
>
> a) Berechnen Sie
>
> [mm]44^{n_{1}-1} \mbox{mod } n_{1}[/mm] Hilfsmittel: [mm]44^{4} \mbox{mod } n_{1}=1[/mm]
>
>
> [mm]67^{n_{2}-1} \mbox{mod } n_{2}[/mm] Hilfsmittel: [mm]67^{186} \mbox{mod } n_{2}=1[/mm]
>
>
> [mm]44^{n_{3}-1} \mbox{mod } n_{3}[/mm] Hilfsmittel: [mm]44^{187} \mbox{mod } n_{3}=4[/mm]
>
> b) Satz von Fermat ("kleiner Fermat"): Für alle [mm]n \in \IN[/mm]
> mit [mm]n \ge 2[/mm] gilt: n Primzahl gdw. für alle [mm]a \in \{1,...,n-1\}[/mm]
> gilt [mm]a^{n-1}\mbox{mod } n = 1[/mm]
>
> Für welche der Zahlen [mm]n_{1}, n_{2}, n_{3}[/mm] folgt aus den
> obigen Ergebnissen, dass die Zahl eine Primzahl ist? Für
> welche folgt, dass sie keine Primzahl ist?
> Hallo,
>
> es wäre sehr nett, wenn mir jemand erklären könnte, wie
> das Hilfsmittel in der a) zu verwenden ist, denn ich denke,
> dass man keinen Taschenrechner benutzen darf.
>
> Bei der ersten Rechnung habe ich
>
> [mm]44^{558} \mbox{mod } 559[/mm] und als Hilfsmittel [mm]44^{4} \mbox{mod } 559=1[/mm]
>
> Wie nutze ich nun aber das Hilfsmittel?
Tipp: $558=4*139+2$, und es gilt natürlich
[mm] a^{n_1+n_2} \bmod n = ((a^{n_1} \bmod n)*(a^{n_2} \bmod n)) \bmod n [/mm] .
Viele Grüße
Rainer
|
|
|
| |
|
| Aufgabe | Sei $ [mm] n_{1}=559, [/mm] $ $ [mm] n_{2}=561, [/mm] $ $ [mm] n_{3}=563. [/mm] $
a) Berechnen Sie
$ [mm] 44^{n_{1}-1} \mbox{mod } n_{1} [/mm] $ Hilfsmittel: $ [mm] 44^{4} \mbox{mod } n_{1}=1 [/mm] $
$ [mm] 67^{n_{2}-1} \mbox{mod } n_{2} [/mm] $ Hilfsmittel: $ [mm] 67^{186} \mbox{mod } n_{2}=1 [/mm] $
$ [mm] 44^{n_{3}-1} \mbox{mod } n_{3} [/mm] $ Hilfsmittel: $ [mm] 44^{187} \mbox{mod } n_{3}=4 [/mm] $
b) Satz von Fermat ("kleiner Fermat"): Für alle $ n [mm] \in \IN [/mm] $ mit $ n [mm] \ge [/mm] 2 $ gilt: n Primzahl gdw. für alle $ a [mm] \in \{1,...,n-1\} [/mm] $ gilt $ [mm] a^{n-1}\mbox{mod } [/mm] n = 1 $
Für welche der Zahlen $ [mm] n_{1}, n_{2}, n_{3} [/mm] $ folgt aus den obigen Ergebnissen, dass die Zahl eine Primzahl ist? Für welche folgt, dass sie keine Primzahl ist? |
Hallo Rainer,
> Tipp: [mm]558=4*139+2[/mm], und es gilt natürlich
>
> [mm]a^{n_1+n_2} \bmod n = ((a^{n_1} \bmod n)*(a^{n_2} \bmod n)) \bmod n[/mm]
> .
vielen Dank für die Hilfe. Das hat den Nagel genau auf den Kopf getroffen! 
Es wäre sehr nett, wenn sich jemand bei Gelegenheit meinen Lösungsweg ansehen könnte, denn ich bin mir nicht sicher, ob ich die 139 einfach herausziehen und außerhalb der Klammer schreiben darf.
$ [mm] 44^{558} \mbox{mod } [/mm] 559 $ und als Hilfsmittel $ [mm] 44^{4} \mbox{mod } [/mm] 559=1 $
[mm] $44^{558} \mbox{ mod } [/mm] 559$
$= [mm] 44^{4*139+2} \mbox{ mod } [/mm] 559$
$= [mm] (44^{4*139}*44^{2}) \mbox{ mod } [/mm] 559$
$= [mm] ((44^{4} \mbox{ mod } 559)^{139}*(44^{2} \mbox{ mod } [/mm] 559)) [mm] \mbox{ mod } [/mm] 559$
$= [mm] (1^{139}*(1936 \mbox{ mod } [/mm] 559)) [mm] \mbox{ mod } [/mm] 559$
$= (1*259) [mm] \mbox{ mod } [/mm] 559$
$= 259$
> Viele Grüße
> Rainer
Gruß
el_grecco
|
|
|
| |
|
Hallo grec,
ja, so ist es komplett richtig.
![[winken]](/images/smileys/winken.gif "[winken]")
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:18 Mi 04.05.2011 | | Autor: | el_grecco |
Hallo rev,
vielen Dank für die Korrektur, der Rest der Aufgabe war dann kein Problem mehr.
Gruß
el_grecco
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:24 Do 05.05.2011 | | Autor: | reverend |
> vielen Dank für die Korrektur
Aber das war doch gar nichts mehr zu korrigieren. ![[kopfkratz3]](/images/smileys/kopfkratz3.gif "[kopfkratz3]")
Du hast Rainers Hinweise doch komplett befolgt. Alles gut also.
Gute Nacht,
le rev (mais pas le rêve)
|
|
|
|
![[saumuede]](/images/smileys/saumuede.gif "[saumuede]"){kind=small}
