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