Satz von Euler: 10^12001 mod 13

Question

 

ich habe folgende Aufgabe gegeben: Bestimmen Sie 10¹²⁰⁰¹ mod 13.

hier kann ich ja den Satz von Euler anwenden. Nur weiß ich nicht, wie er funktioniert und wie man ihn an diesem Beispiel anwenden kann. Könnte mir jemand erklären, wie der Satz von Euler funktioniert und wie ich den hier anwenden kann?

Danke schonmal ;)

Answer 1

10¹²Ξ1 mod13 (kleiner Fermat)

10¹²⁰⁰⁰Ξ1 mod13

10¹²⁰⁰¹Ξ10 mod13

Answer 2

Du kannst ja mal ein paar Beispiele machen

10¹ mod 13 = 10

10² mod 13 = 9


10³ mod 13 = 12

10⁴ mod 13 =  3

10⁵ mod 13 =  4


10⁶ mod 13 =  1

Dann ist z.B. 10¹² mod 13 = 1 * 1 = 1  

etc. Also 10 ^6*n mod = 1   


Da 12000 auch durch 6 teilbar ist, ist also 10¹²⁰⁰⁰  mod 13 = 1

und damit   10¹²⁰⁰¹  mod 13 = 10

Answer 3

Ich habe folgende Aufgabe gegeben: Bestimmen Sie 10¹²⁰⁰¹ mod 13.
Hier kann ich ja den Satz von Euler anwenden.

Ja, aber ich finde es viel lustiger, wenn man es ohne macht: Wir wissen (Klasse 5/6 oder so), dass 13 ein Teiler von 1001 ist. Folglich ist $$1000\equiv -1 \mod 13$$ und wir können dies ausnutzen und rechnen

$$ 10^{12001} = 10 \cdot 1000^{400} \equiv 10 \cdot (-1)^{400} = 10 \mod 13. $$Das finde ich einfacher als die zahlentheoretischen Standardansätze...