Rest berechnen < Lin. Algebra/Vektor < Oberstufe < Schule < Mathe < Vorhilfe
|
| Aufgabe | | Berechne den Rest von 3^15 und 15^83 bei Division durch 13 |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Klar könnte ich einfach 3^15/13 rechnen doch ist das recht zeitaufwendig zumindest bei 15^83 ... ?
Gibt es da irgendeinen Trick?
|
|
| |
|
Hallo,
ja gibt es: Kongruenzen!!
bei der Bestimmung des Restes von [mm] 3^{15} [/mm] bei Division durch 13 zB.
Es ist [mm] 3^{15}=\left(3^3\right)^5 [/mm] [Edit: Hab's verbessert - danke  ]
Und [mm] 3^3=27\equiv [/mm] 1 modulo(13)
Also....
Gruß
schachuzipus
|
|
|
| |
|
Hmm,... irgendwie verstehe ich nicht genau wie mir das weiterhelfen soll.
Ist es nicht egal, ob ich [mm] 3^{15} [/mm] / 13 oder [mm] 27^{5} [/mm] / 13 berechne???
Und die 83 kann ich in nichts zerlegen??? Was mache ich hier am Besten?
|
|
|
| |
|
Hoi,
hattet ihr keine Sätze zum Rechnen mit Kongruenzen?
Dieser hier ist nützlich:
[mm] $a\equiv [/mm] b mod(m) [mm] \Rightarrow a^n\equiv b^n [/mm] mod(m)$ für alle [mm] $n\in\IN$
[/mm]
Nun also mit [mm] $3^{15}=\left(3^3\right)^5$ [/mm] gilt doch
[mm] $3^3\equiv [/mm] 1 mod(13)$, denn $13|27-1$
Also [mm] $\left(3^3\right)^5\equiv$ [/mm] .....
Nun klar(er)?
Gruß
schachuzipus
|
|
|
| |
|
Also ist dann...
[mm] 3^{3^{5}} \equiv 1^{5} [/mm] mod 13
also ist hierbei dann der Rest 1 ???
|
|
|
| |
|
Hallo,
zum Rest von [mm] 15^{83} [/mm] bei Division durch 13 guck dir mal den Rest von [mm] 15^3 [/mm] an. [mm] (15^3\equiv [/mm] ... mod(13))
Bedenke auch [mm] 15^{83}=15^{81}\cdot{}15^2=\left(15^3\right)^{27}\cdot{}15^2
[/mm]
Damit solltest du hinkommen
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Korrektur) kleiner Fehler  | | Datum: | 17:00 Mi 21.03.2007 | | Autor: | comix |
[mm] 3^{15} [/mm] = [mm] (3^{3})^5
[/mm]
|
|
|
|
