0 Daumen
66 Aufrufe

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...

Gefragt von

2 Antworten

0 Daumen

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ß

Beantwortet von
0 Daumen

(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.

Beantwortet von

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.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...