Welchen Rest lässt (21212124 ^ 2448) mod 7. Modulares Potenzieren

Question

also, meine Aufgabe ist: Welchen Rest lässt (21212124 ^ 2448) mod 7?

Ich hab erstmal 21212124 so aufgeteilt : (21000000+ 210000+ 2100 + 21 + 3) mod 7)^2448 mod 7

und komme dann ja quasi auf (3 mod 7 )^2448 mod 7. Ist das bis hierhin richtig? Wenn ja, wie geht es jetzt weiter? :S

!

Answer 1

Ja, 3^2448 mod 7 ergibt das selbe Ergebnis.

Ich nutze gern den universellen Pow-Mod-Algorithmus siehe Iterationsrechner Beispiel 122

Nach 12 Schritten kommt 1 heraus. (auch bei a=3 und selbe Schrittzahl i=12)

Wer sich für die große Potenz interessiert:

http://www.lamprechts.de/gerd/php/RechnerMitUmkehrfunktion.php

mit pow-Funktion und N=1000000000000000000000000000000 ergibt

3.006193022766442699868823640324814... e17935
mod N =527695531858883592247759077376

Also eine Zahl mit 17936 Stellen, die mit 3006... beginnt und mit  ...59077376 endet.

Übrigens ist  (59077376) mod 7 =1

Answer 2

 Alle Quersummen gehen modulo; für Teilbarkeit durch 7 hast du die A3, die alternierende Quersumme 3. Ordnung.



  21 212 124  =  124  -  212  +  21  =  ( - 67  )  =  3  mod  7    (  1  )



    Man liest so häufig, bei der Quersumme sei es egal, ob du bei dem " rechtesten " Block  mit Plus oder Minus beginnst, Nein du musst grundsätzlich mit Plus anfangen; sonst kommt ja das Vorzeichen des Restes falsch heraus.
   Von Daher ist also klar, dass a = 3 .

Comments

  Ich darf bei Hyper nicht kommentieren. Seine Zahl


   59 077 376


   also die mittlere 077 können wir schon mal weglassen.


    59  =  3  mod  7


  376  +  3  =  379


   Was passiert jetzt? Ich bin der Erste, der die allgemeine 100-er Regel formuliert hat; du prüfst auf Teilbarkeit durch p , indem du fragst: Was gibt 100 mod p ? Für p = 7 führt das auf die ===> Babylonische Teilbarkeitsregel



   100  =  2  mod  7

    100  a  +  b  =  2  a  +  b  modd  7



   Bei 379 setze a = 3 ; b = 79


   79  +  6  =  85  =  1  mod  7  ;  ok