Modulo rechnen

- Modulo- Methode Multiplizieren & Quadrieren rechnen

Hallo Gast!

Klicke mal https://www.youtube.com/watch?v=ribhv53H288 .

Dort ist Modulo-Rechnen gut und ausführlich erklärt.

Erfolg dabei wünscht

  !

Moin, ich muss \(3^{47} \pmod {91}\) mit der Methode Multiplizieren & Quadrieren rechnen aber irgendwie check is das gar nicht.

\(\begin{array}{|rcll|} \hline && \mathbf{ 3^{47} \pmod {91}} \\\\ & \equiv & 3^{42+5 } \pmod {91} \\ & \equiv & 3^{6\cdot 7 +5 } \pmod {91} \\ & \equiv & 3^{6\cdot 7 } \cdot 3^5 \pmod {91} \\\\ & \equiv & \left(3^{6}\right)^7 \cdot 3^5 \pmod {91} \quad | \quad 3^6 \equiv 1 \pmod {91} \\ & \equiv & \left(1\right)^7 \cdot 3^5 \pmod {91} \\ & \equiv & 1 \cdot 3^5 \pmod {91} \\ & \equiv & 3^5 \pmod {91} \\ & \equiv & 243 \pmod {91} \\ & \equiv & \mathbf{ 61 \pmod {91} } \\ \hline \end{array}\)

Moin, ich muss \(3^{47} \pmod {91}\) mit der Methode Multiplizieren & Quadrieren rechnen aber irgendwie check is das gar nicht.

Methode Multiplizieren & Quadrieren:

\(\begin{array}{|rcll|} \hline && \mathbf{ 3^{47} \pmod {91}} \quad &| \quad 3^{47} = 3\cdot \left( 3^{23}\right)^2 \\\\ & \equiv & 3\cdot \left( 3^{23}\right)^2 \pmod {91} \quad &| \quad 3^{23} = 3\cdot \left(3^{11}\right)^2 \\ & \equiv & 3\cdot \left( 3\cdot \left(3^{11}\right)^2\right)^2 \pmod {91} \quad &| \quad 3^{11} = 177147 \\ & \equiv & 3\cdot \left( 3\cdot \left(177147\right)^2\right)^2 \pmod {91} \quad &| \quad 177147 \pmod {91} \equiv 61 \\ & \equiv & 3\cdot \left( 3\cdot \left(61\right)^2\right)^2 \pmod {91} \quad &| \quad 3\cdot \left(61\right)^2 = 11163 \\ & \equiv & 3\cdot \left( 11163 \right)^2 \pmod {91} \quad &| \quad 11163 \pmod {91} \equiv 61 \\ & \equiv & 3\cdot \left( 61 \right)^2 \pmod {91} \quad &| \quad 3\cdot \left(61\right)^2 = 11163 \\ & \equiv & 11163 \pmod {91} \quad &| \quad 11163 \pmod {91} \equiv 61 \\ & \equiv & \mathbf{ 61 \pmod {91} } \\ \hline \end{array}\)