Bestimmen Sie eine nat. Zahl 0 ≤ k ≤ 6, sodass 2222255555+5555522222 kongruent zu k mod 7

Question

Bestimmen Sie eine nat. Zahl 0 <= k <= 6, sodass 22222⁵⁵⁵⁵⁵+55555²²²²²≡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⁵⁵⁵⁵⁴≡1 mod 55555

55555²²²²¹≡1 mod 22222

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

Comments

https://de.wikipedia.org/wiki/Kleiner_fermatscher_Satz

---

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

22222⁵⁵⁵⁵⁴ kongruent zu 1 mod 55555

55555²²²²¹ 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 ?

Answer 1

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

x^y mod m = 55555²²²²² 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⁵⁵⁵⁵⁵ 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:

Comments

Was soll das prozent zeichen bedeuten?

---

Das Prozent ist Modulo in der Programmierung

Answer 2

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 \)