0 Daumen
615 Aufrufe

ich soll alle x Element Z20 für die Gleichung 9887^8899 * x = 11 (mod 20) bestimmen...

für Zahlen ohne Potenzen bekomm ich das mittlerweile hin aber wie mache ich das wenn ich so eine große Potenz habe???

Avatar von

Zahlen ohne Potenzen " soll denn das x auch noch im Exponenten stehen? 

1 Antwort

0 Daumen
 
Beste Antwort

lass Dich von den großen Zahlen nicht erschrecken. Die kriegen wir ganz schnell klein!

Wenn Du einen Ausdruck hast, wie

$$(20 k + n)^m \equiv y \mod 20 \quad k,n,m, y \in \mathbb{N}$$

Dann könntest Du die Potenz \((20k + n)^m\) nach dem Binomischen Lehrsatz auflösen. Du bekämst \(m+1\) Summanden von denen die ersten \(m\) Summanden alle Produkte von \(20\) wären. Damit fallen sie durch den Modulo alle raus. Kannst Du ja mal für \(m=2\) ausprobieren .. D.h.:

$$(20 k + n)^m \equiv n^m \equiv y \mod 20$$

Damit verkleinert sich das Problem von

$$9887^{8899} \cdot x \equiv 11 \mod 20$$

auf:

$$(9880+7)^{8899} \cdot x \equiv 7^{8899} \cdot x \equiv 11 \mod 20$$

Da \(9880\) durch \(20\) teilbar ist. Jetzt betrachten wir mal, was passiert, wenn man bei einer Potenz mit der Basis \(7\) den Exponenten erhöht.

$$7^0 \equiv 1 \mod 20$$

$$7^1 \equiv 7 \mod 20$$

$$7^2 \equiv 9 \mod 20$$

$$7^3 \equiv 3 \mod 20$$

$$7^4 \equiv 1 \mod 20$$

$$7^5 \equiv 7 \mod 20$$

wie man sieht wiederholt sich der Wert ab einer Potenz von \(4\). Man kann also allgemein schreiben:

$$7^{4k+n} \equiv 7^n \mod 20$$

oder ganz konkret

$$7^{8899} \cdot x \equiv  7^{8896 + 3} \cdot x \equiv 7^3 \cdot x\equiv 11 \mod 20$$

weil \(8896\) durch \(4\) teilbar ist. Und da \(7^3 \equiv 3 \mod 20\) ist, bleibt am Ende übrig:

$$3 \cdot x \equiv 11 \mod 20$$

Und dies kannst Du ja nach eigener Aussage selbst lösen. \(x=17\) - das ist IMHO auch die einzige Lösung.

Gruß Werner

Avatar von 48 k

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

+1 Daumen
1 Antwort
0 Daumen
1 Antwort
0 Daumen
2 Antworten
0 Daumen
1 Antwort

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community