Bestimmen Sie eine nat. Zahl 0 <= k <= 6, sodass 2222255555+5555522222≡k mod 7Ich 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:2222255554≡1 mod 555555555522221≡1 mod 22222Leider weiß ich nicht wie ich weiter rechnen soll, oder was ich machen soll.Wäre über jeden Tipp dankbar.
Nach dem kleinem fertmatischen Satz komme ich ja nur auf diese Form:
2222255554 kongruent zu 1 mod 55555
5555522221 kongruent zu 1 mod 22222
Jedoch bringt mir dass ja nichts um herauszufinden welche Zahl für k einzusetzen ist oder?
und wie soll ich es dann lösen ?
Ich mag weder das ≡ noch Sätze, sondern nehme den universellen Algorithmus:
xy mod m = 5555522222 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:
2222255555 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:
Was soll das prozent zeichen bedeuten?
Das Prozent ist Modulo in der Programmierung
Schritt 1: Reduzieren der Basis
22222≡4mod 7 22222 \equiv 4 \mod 7 22222≡4mod7 und 55555≡3mod 7 55555 \equiv 3 \mod 7 55555≡3mod7
Schritt 2: Verwenden des kleinen Satz von Fermat:
55555=9259 *6+1 und 22222= 3703*6 +4
Damit ist 2222255555+5555522222≡(46)9259⋅4+(36)3703⋅34≡4+4≡1mod 7 22222^{55555} +55555^{22222} \equiv (4^6)^{9259} \cdot 4 + (3^6)^{3703}\cdot 3^4 \equiv 4+4 \equiv 1 \mod 7 2222255555+5555522222≡(46)9259⋅4+(36)3703⋅34≡4+4≡1mod7
Ein anderes Problem?
Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos