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

Avatar 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ß

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

Avatar 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

0 Daumen
1 Antwort
Gefragt 12 Jan 2023 von Weggi2000
0 Daumen
0 Antworten

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community