0 Daumen
80 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...

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ß

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.

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

Ähnliche Fragen

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...