modulo

04.01.2007, 12:05

*isa*

modulo

hi,
ich habe ne frage
ich zerbreche mir schon ewig den kopf darüber
wie ich z.b x ist kongruent zu 12^13 mod 77 ausrechnen kann
gruß isa

04.01.2007, 12:21

therisen

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \equiv \end{eqnarray*}$ ist transitiv und es gilt $\begin{eqnarray*} 12^{13} \equiv 12 \pmod {77} \end{eqnarray*}$

Gruß, therisen

04.01.2007, 12:27

*isa*

Auf diesen Beitrag antworten »

was heißt transitiv
und wie siehts dann aus mit 69^13mod77?

04.01.2007, 12:33

Menelaos

Auf diesen Beitrag antworten »

$\begin{eqnarray*} x \equiv 12^{13} \ (mod \ 77) \Leftrightarrow 77~|~(x-12^{13}) \end{eqnarray*}$

Transitiv heisst $\begin{eqnarray*} a \equiv b \ (mod \ m), b \equiv c \ (mod \ m) \Rightarrow a \equiv c \ (mod \ m) \end{eqnarray*}$ .

04.01.2007, 12:36

therisen

Auf diesen Beitrag antworten »

Wegen $\begin{eqnarray*} 12^{13} \equiv 12 \pmod {77} \end{eqnarray*}$ (das musst du begründen!) kannst du statt $\begin{eqnarray*} x \equiv 12^{13} \pmod {77} \end{eqnarray*}$ einfach $\begin{eqnarray*} x \equiv 12 \pmod {77} \end{eqnarray*}$ lösen.

Weiter ist $\begin{eqnarray*} 69^{13} \equiv 27 \pmod {77} \end{eqnarray*}$ (das musst du auch zeigen Augenzwinkern

)

Gruß, therisen

04.01.2007, 14:25

*isa*

Auf diesen Beitrag antworten »

danke erstmal
was ich nicht ganz verstanden habe ist wie man übehaupt auf die 27 kommt, könntest du mir dazu den rechenweg angeben? das wäre super

04.01.2007, 16:30

therisen

Auf diesen Beitrag antworten »

Hallo,

es ist $\begin{eqnarray*} 69 \equiv -8 \equiv (-2)^3 \pmod {77} \end{eqnarray*}$ , also $\begin{eqnarray*} 69^{13} \equiv (-2)^{39} \pmod {77} \end{eqnarray*}$ . Nun ist $\begin{eqnarray*} (-2)^{30} \equiv ((-2)^6)^5 \equiv 1^5 \equiv 1 \pmod 7 \end{eqnarray*}$ und $\begin{eqnarray*} (-2)^{30} \equiv ((-2)^5)^6 \equiv 1^6 \equiv 1 \pmod {11} \end{eqnarray*}$ . Wegen $\begin{eqnarray*} \mathrm{ggT}(7,11)=1 \end{eqnarray*}$ folgt $\begin{eqnarray*} (-2)^{30} \equiv 1 \pmod {77} \end{eqnarray*}$ . Es gilt also $\begin{eqnarray*} (-2)^{39} \equiv (-2)^9 \pmod {77} \end{eqnarray*}$ . Das kann man jetzt einfach ausrechnen: $\begin{eqnarray*} (-2)^9 = -512 \end{eqnarray*}$ und $\begin{eqnarray*} -512-27 = -539 = -7 \cdot 77 \end{eqnarray*}$ , also $\begin{eqnarray*} (-2)^9 \equiv 27 \pmod {77} \end{eqnarray*}$ .

Gruß, therisen

PS: $\begin{eqnarray*} 30 \end{eqnarray*}$ ist die kleinste natürliche Zahl mit $\begin{eqnarray*} (-2)^{30} \equiv 1 \pmod {77} \end{eqnarray*}$ .

04.01.2007, 16:37

Auf diesen Beitrag antworten »

Zitat:

Original von therisen (leicht verändert)
$\begin{eqnarray*} k=30 \end{eqnarray*}$ ist die kleinste positive natürliche Zahl mit $\begin{eqnarray*} (-2)^k \equiv 1 \pmod {77} \end{eqnarray*}$ .

Nichts für ungut Augenzwinkern

Neue Frage »

Antworten »

modulo

Verwandte Themen