Question

Es gilt n^p-1 ≡ 1 mod p, wenn p eine Primzahl ist und n∈ℕ.

Wie berechne ich diese Aufgaben?

a) Berechnen Sie effizient: (12345³² mod 17)∈{0, ..., 16}.

b) Beweisen Sie n^p  ≡ n mod p.

c) Berechnen Sie effizient: (3³⁴ mod 17) ∈ {0, ..., 16}.

d) Bestimmen Sie das multiplikative Inverses von [3¹⁵]₁₇∈ℤ₁₇

Vielen Dank

Answer 1

a) $12345^{32}=12345^{2(17-1)}=\left( {12345^2} \right) ^{17-1} \equiv 1 \mod 17$

b) dividiere durch $n$

c) $3^{34}=\left( {3^2} \right) ^{17-1} \cdot 3^2 \equiv 1 \cdot 9 = 9 \mod 17$

d) Die multiplikative Inverse sei $x$. Dann muss $3^{15} \cdot x \equiv 1 \mod 17$ sein. Aus $3^{17-1}= 3^{15} \cdot 3^1 \equiv 1 \mod 17$ folgt, dass $x=3$ ist.

Answer 2

a) Berechnen Sie effizient: (12345³² mod 17)∈{0, ..., 16}.

12345¹⁶ ≡1 mod 17 quadrieren

12345³²  ≡1 mod 17