0 Daumen
1,1k Aufrufe

Bestimmen Sie eine nat. Zahl 0 <= k <= 6, sodass 22222^55555+55555^22222≡k mod 7

Ich bin bei dieser Aufgabe nicht weiter gekommen und habe mit mit dem Taschenrechner erst einmal das Ergebnis ausgeben lassen, welches 1 mod 7 ist. Jedoch sollen wir es ohne Taschenrechner und mit Begründung lösen.

Also habe ich es mit dem kleinen fermatischen Satz probiert, bin aber nicht weiter als diese Formen gekommen:

22222^55554≡1 mod 55555

55555^22221≡1 mod 22222

Leider weiß ich nicht wie ich weiter rechnen soll, oder was ich machen soll.
Wäre über jeden Tipp dankbar.

Avatar von

Nach dem kleinem fertmatischen Satz komme ich ja nur auf diese Form:

22222^55554 kongruent zu 1 mod 55555

55555^22221 kongruent zu 1 mod 22222

Jedoch bringt mir dass ja nichts um herauszufinden welche Zahl für k einzusetzen ist oder?

Unfug, 55555 und 22222 sind keine Primzahlen.  Da kann Fermat also nicht angewendet werden.
Es gibt in der ganzen Aufgabenstellung eine einzige Primzahl.

und wie soll ich es dann lösen ?

2 Antworten

0 Daumen

Ich mag weder das ≡ noch Sätze, sondern nehme den universellen Algorithmus:

x^y mod m = 55555^22222 mod 7

l = 1;

x = x % m;

solange (y > 0)

{  if (y % 2 == 1)

{  l = (l * x) % m;

y =y - 1;

}

x = x² % m;

y = y / 2;

}

Ergebnis =l

------------------

1. Summand:

l=1

x=55555 %7 =3

y=22222 -> %2=0

x=3²%7=2

y=11111

---

y % 2 =1 (also ungerade)

{ l= 1*2 %7 =2

y= 11111-1=11110

}

x=3² %7=4

y=11110/2=5555

...

----

{l=1*4 %7 =4

y=1-1=0

}

Ergebnis l=4

analog 2. Summand:

22222^55555 mod 7 auch 4

( 4 + 4) mod 7 = 8 mod 7 = 1 = Endergebnis (bei Dir das gesuchte k) 

Test mit http://www.lamprechts.de/gerd/php/RechnerMitUmkehrfunktion.php  bestätigt mit N=7 die 4:

Bild Mathematik

Avatar von 5,7 k

Was soll das prozent zeichen bedeuten?

Das Prozent ist Modulo in der Programmierung

0 Daumen

Schritt 1: Reduzieren der Basis

\( 22222 \equiv 4 \mod 7 \)  und \( 55555 \equiv 3 \mod 7 \)

Schritt 2: Verwenden des kleinen Satz von Fermat:

55555=9259 *6+1 und 22222= 3703*6 +4

Damit ist \( 22222^{55555} +55555^{22222} \equiv (4^6)^{9259} \cdot 4 + (3^6)^{3703}\cdot 3^4 \equiv 4+4 \equiv 1 \mod 7 \)

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community