Frage zur Lösung... Kongruenzen und Restmenge

Question

Zu folgender Aufgabe habe ich die passende Lösung: Berechne in den folgenden Fällen die Reste bei Division von a^k durch n für alle k = 1, 2, 3, . . . , n − 1 . Was fällt auf? Führe die Rechnungen ohne Taschenrechner aus und benutze die Rechenregeln für Kongruenzen.

a) n = 11 : a = 2 , a = 3 und a = 10

Lösung für a = 2 :

a¹ ≡ 2 (mod 11) =⇒ r₁₁(a¹ ) = 2

a² ≡ 4 (mod 11) =⇒ r₁₁(a ² ) = 4

a³ ≡ 8 (mod 11) =⇒ r₁₁(a³ ) = 8

a⁴ ≡ 5 (mod 11) =⇒ r₁₁(a⁴ ) = 5

 a⁵ ≡ −1 (mod 11) =⇒ r₁₁(a⁵ ) = 10

 a⁶ ≡ −2 (mod 11) =⇒ r₁₁(a⁶ ) = 9 

a⁷ ≡ −4 (mod 11) =⇒ r₁₁(a⁷ ) = 7 

a⁸ ≡ −8 (mod 11) =⇒ r₁₁(a ⁸ ) = 3 

a ⁹ ≡ 6 (mod 11) =⇒ r₁₁(a ⁹ ) = 6 

a ¹⁰ ≡ 1 (mod 11) =⇒ r₁₁(a¹⁰) = 1 

Die Reste sind paarweise verschieden, und es gilt r₁₁(a¹⁰) = 1 .

Ich würde gerne wissen, wie man schnell auf die blauen Lösungen und insbesondere die fettgedruckten Zahlen kommt... Das würde mir wirklich sehr weiterhelfen!!!

Answer 1

wenn du hast a^4 kongruent 5 mod 11  Dann ist

a^5 kongruent 5*a mod 11

und für a=2 ist 5*2=10 und das ist kongruent -1 mod 11

Answer 2

Ich würde gerne wissen, wie man schnell auf die blauen Lösungen und insbesondere die fettgedruckten Zahlen kommt...

Rechne einfach das vorhergehende Resultat "MAL 2" und dann das Resultat modulo 11.

a² ≡ 4 (mod 11) =⇒ r₁₁(a ² ) = 4

4*2 = 8

a³ ≡ 8 (mod 11) =⇒ r₁₁(a³ ) = 8

8*2 = 16 modulo 11 gibt 5

a⁴ ≡ 5 (mod 11) =⇒ r₁₁(a⁴ ) = 5

10 modulo 11

==> -1

 a⁵ ≡ −1 (mod 11) =⇒ r₁₁(a⁵ ) = 10

-1 *2 = -2

 a⁶ ≡ −2 (mod 11) =⇒ r₁₁(a⁶ ) = 9 

-2 * 2 = 4 

usw.

Comments

DANKE!!! So langsam verstehe ich, wie das funktioniert :D...

---

Bitte. Gern geschehen.