Zeige, dass 134^6789 − 6 durch 11 teilbar ist.

Question

Aufgabe:

Zeige, dass 134^6789 − 6 durch 11 teilbar ist.

Problem/Ansatz:

soll ich erst 134^6789 mit dem Satz von Euler ''ausrechnen'' und dann -6 mod 11?

Ich wiß, dass 6789 keine Primzahl ist, daher könnte ich es so aufschreiben : 134^678 = 134^(3*31*73)

wäre das so richtig? Wie sollte ich hier am besten vorgehen ?

Ich wäre sehr dankbar wenn mir jemand einen Tipp geben könnte. :)

Answer 1

Hallo,

Ich wiß, dass 6789 keine Primzahl ist, ...

aber \(11\) ist eine. Und mit dem kleinen Satz von Fermat kann man schreiben$$\begin{aligned} 134^{6789} - 6 &\equiv x \mod 11 &&|\, 134^{k\cdot (11-1)} \equiv 1 \mod 11 \\134^{9} -6 &\equiv x \mod 11 &&|\, 134 = 12\cdot 11 + 2 \\ 2^9 - 6&\equiv x \mod 11\\ 506 &\equiv 0 \mod 11 \\ \end{aligned}$$ist also durch \(11\) teilbar.

Gruß Werner

Answer 2

Kleiner Satz von Fermat: 134¹⁰≡1 mod 11

Potenzieren mit 678: (1) 134⁶⁷⁸⁰≡1 mod 11

Es gilt:                       (2) 134⁹≡6 mod 11

multiplizieren:            134⁶⁷⁸⁹≡6 mod 11

Also  134⁶⁷⁸⁹-6≡0 mod 11.

Answer 3

Der kleine Fermat ist hier sicher die Top-Lösung.

Ohne denselben: Wegen 134 ≡ 2 mod 11 ist nachzuweisen, dass

\(2^{6789} ≡ 6 mod 11\) ist.

Dafür ist es sinnvoll herauszufinden, für welches n
\(2^{n} ≡ 6 mod 11\) erstmalig gilt und in welcher Regelmäßigkeit das wieder passiert.

Da maximal 10 mögliche Reste mod 11 für Zweierpotenzen möglich sind, muss man nicht lange suchen. Es gilt \(2^{9}≡ 512 ≡ 6 mod 11\). Da übrigens auch \(2^{10}≡1024 ≡ 1 mod 11\) gilt, hat man die Regelmäßigkeit gefunden. Alle Potenzen \(2^{9+10k}\) (und damit auch alle Potenzen \(134^{9+10k}\)) lassen bei Teilung durch 11 den Rest 6.

Answer 4

134^6789  mod 11

2^6789  mod 11

2^(10*678+9) mod 11

[ 2^10=2^5*2^5≡(-1)*(-1) mod 11 ≡ 1 mod 11 ]

2^9 mod 11

2^4*2^4*2 mod 11

5*5*2 mod 11

50 mod 11

6 mod 11

:-)