Modulo berechnen von bel. n aus N

Question

Hi,

meine Aufgabe ist die folgende:

Berechne (n+1)^2  mod n.

Ich weiß wie man bspw. 10 mod 3 berechnet, aber leider bin ich bei n Element der natürlichen Zahlen überfordert...

Answer 1

Hi,

nehmen wir mal n>1

(2+1)² mod 2 = 9 mod 2 = 1

(3+1)² mod 3 = 16 mod 3 = 1

(4+1)² mod 4 = 25 mod 4 = 1

Scheint also immer 1 zu ergeben. Das ganze muss nur noch allgemein gezeigt werden:
Dafür kann man die Regel a*b mod c = ([a mod c] * [b mod c]) mod c

(n+1)² mod n = (n+1)(n+1) mod n = ([(n+1) mod n] *[(n+1) mod n]) mod n = 1*1 mod n = 1

Gruß

Answer 2

(n + 1)^2 = n^2 + 2·n + 1 = n·(n + 2) + 1

Was sind denn jetzt

n·(n + 2) + 1 MOD n

Das solltest du denke ich beantworten können.

Wenn du nicht verstehst wie man auf das Ergebnis 1 kommt, dann frag nochmals nach.

Comments

Vielen Dank schonmal!

Die Umformung zu n*(n + 2) + 1 versteh ich. Allerdings weiß ich leider nicht was das Ergebnis von n*(n + 2) + 1 mod n ist :( Bisher habe ich immer nur den MOD zweier Zahlen berechnet...

Muss ich als nächstes n*(n + 2) + 1 durch n teilen? Wäre das Ergebnis (der Rest) also (n+2) + 1?

Bin da wirklich sehr wackelig :S

---

Setzt doch mal für n ein Paar Werte ein

n·(n + 2) + 1 MOD n

1·(1 + 2) + 1 MOD 1 <-- Das ist sicher eine Ausnahme

2·(2 + 2) + 1 MOD 2

3·(3 + 2) + 1 MOD 3

4·(4 + 2) + 1 MOD 4

5·(5 + 2) + 1 MOD 5

Berechne die Werte und probiere aus den Ergebnissen ein Muster zu bilden. Ich denke nicht das dir das schwerfallen sollte. Versuche dann zu erklären warum das so ist wie es ist.