Modulo Rechnung mit großen Zahlen?

Question

1.Ich habe die Aufgabenstellung mit 2^150mod255 gegeben.

Mein Ansatz dazu war.

2^150mod255 = (2^2)^75mod255 = 4^75mod255 dann komme ich Leder nicht weiter


2. Wie kann ich Fakultäten beim Modulo ausrechnen z.B. 6!mod7

3. Wie kann ich 13x9x14mod6 ausrechnen?
Muss ich zuerst multiplizieren und dann mod rechnen oder gibt es dort auch eine Regel zu?


Vielen dank schon mal im voraus .

Comments

zu1) Überlege mal wieviel Mal die 225 in die 150 passt .-)

---

Oh man mit dem aufschreiben habe ich es noch nicht so ganz und zwar soll es heißen.

2^150 mod 255 = (2^2)^75 mod 255 =  4^75 mod 255

Also 0 mal passt die da rein :)

Answer 1

zu 2)

6! = 720

720 mod 7 = ?

102*7 = 714 -> 720 - 714 = 6

=> 6! mod 7 = 6

zu 3)

Wenn mich nicht alles täuscht, kann man erst multiplizieren:

(13x9x14) mod 6 = 1638 mod 6 = 0, denn 273*6 = 1638

Comments

zu 2) 6! mod 7

Rechne mal für einige kleine n

(n-1)! mod n aus und gewinne eine Idee.

Sieh Dir anschließend den Satz von Wilson an.

Hier noch die Rechnung von Bepprich, etwas vereinfacht:
6! = 720 = (721-1) == -1 == 6 mod 6.
 

 

zu 3) (13 * 9 * 14) mod 6

Das Produkt will man nicht ausrechnen, muss man auch nicht, da es anders einfacher geht, etwa so:

(13 * 9 * 14) == (13 * (3 * 3) * (2 * 7)) == (13 * 3 * (3 * 2) * 7) mod 6 ==...

---

Danke hh18, sehr geschickte Lösungsansätze. Dafür muss man einen gewissen Blick haben, den ich mitunter nicht aufzuweisen vermag .-)

Answer 2

zu 1)  2¹⁵⁰ mod 255
Eine Möglichkeit besteht darin,
2^8 = 256 ≡ 1 mod 255 zu verwenden.

Der Ansatz wäre dann:
2^150 = 2^{6+8*18} = ...

Comments

Wie komme ich auf die 8 durch ausprobieren?

Verstehe dann aber leider immer noch nicht wie ich auf die Lösung komme es muss ja eine Zahl raus kommen oder?

---

Es ist praktisch, die Potenzen so zu zerlegen oder zusammenzufassen, dass die einzelnen Bestandteile beim Teilen durch den Modul einen betragsmäßig möglichst kleinen Rest haben, im günstigsten Fall den Rest 1. Ich habe ausgenutzt, dass die mir als solche bekannte 2er-Potenz 256 ziemlich nahe am beteiligten Modul 255 liegt.

Von hier aus
2¹⁵⁰ = 2^6+8*18 = ...

geht es so weiter: 2^6 abspalten und den Exponenten 8 auf die Basis ziehen.