Lösen von Kongruenzen: Für welche ganzzahligen n ist 4n^2 +1 durch 5 teilbar?

Question

Aufgabe:

Sie wissen, dass zwei ganze Zahlen a,b ∈ ℤ restgleich bezüglich m heißen (a≡b (mod m)), wenn a-b durch m teilbar ist. Man kann nun mit Kongruenzen fast wie mit ganzen Zahlen rechnen.

Es seien a≡b (mod m) und c≡d (mod m)

Lösen Sie nun folgende Kongruenzen:

a) Für welche ganzzahligen n ist 4n² +1 durch 5 teilbar?

b) Beweisen Sie, dass n⁷ - n stets durch 42 teilbar ist.

Hinweis: Eine geschickte Faktorisierung bei b) sowie (Rest-)Werttabellen können hilfreich sein.

Problem/Ansatz:

Benötige mind. einen Lösungsansatz. Danke.

Answer 1

a) Für welche ganzzahligen n ist 4n^{2 }+1 durch 5 teilbar?

Es soll soll "mit den Kongruenzen gerechnet" werden, also zum Beispiel so:

5 | 4n^2+1 ⇔

0 ≡ 4n^2+1 mod 5 ⇔

0 ≡ 4n^2-4 mod 5 ⇔

0 ≡ 4*(n+1)*(n-1) mod 5 ⇔

0 ≡ n+1 mod 5 oder 0 ≡ n-1 mod 5 ⇔

-1 ≡ n mod 5 oder 1 ≡ n mod 5.

An einigen Stellen muss man begründen können, warum die Umformung richtig ist.

 

Man kann auch so anfangen:

5 | 4n^2+1 ⇔

0 ≡ 4n^2+1 mod 5 ⇔

0 ≡ 1-n^2 mod 5 ⇔

(...)

PS:

b) Beweisen Sie, dass n^{7 }- n stets durch 42 teilbar ist.

Zu zeigen ist $$42 \:\vert\: n^7-n$$Dies entspricht der Bestimmungskongruenz$$n^7-n \equiv 0 \text{ mod } 42$$die wir leicht durch Einsetzen der 42 verschiedenen Reste lösen könnten. Wir folgen stattdessen dem Tipp und versuchen es mit Faktorisieren: $$(n-1)\cdot n\cdot (n+1)\cdot \left(n^2-n+1\right)\cdot \left(n^2+n+1\right) \equiv 0 \text{ mod } 6\cdot 7$$Offenbar ist (n-1)*n*(n+1) immer durch 6 teilbar (warum?), so dass wir vereinfachen können zu $$(n-1)\cdot n\cdot (n+1)\cdot \left(n^2-n+1\right)\cdot \left(n^2+n+1\right) \equiv 0 \text{ mod } 7$$und nur noch 7 verschiedene Reste probieren müssten. Stattdessen formen wir die linke Seite ein wenig (mod 7) um zu $$(n-1)\cdot n\cdot (n+1)\cdot \left(n^2-n-6\right)\cdot \left(n^2+n-6\right) \equiv 0 \text{ mod } 7$$und faktorisieren erneut: $$(n-1)\cdot n\cdot (n+1)\cdot (n+2)\cdot (n-3) \cdot (n-2)\cdot (n+3) \equiv 0 \text{ mod } 7$$Der leichteren Lesbarkeit wegen sortieren wir die Faktoren in aufsteigender Form: $$(n-3) \cdot (n-2) \cdot (n-1) \cdot n \cdot (n+1) \cdot (n+2) \cdot (n+3) \equiv 0 \text{ mod } 7.$$Jetzt sind wir fertig. (Warum?)

Comments

Ist -1 ≡ n mod 5 gleichzusetzen mit 4 ≡ n mod 5? 

Damit komme ich ja dann auf die Restklassen von [1]₅ und [4]₅

Reicht das bereits als Begründung, dass n mit Endung auf 1,4,6,9 durch 5 teilbar ist?

Danke für den Rechenweg :)

---

Ist -1 ≡ n mod 5 gleichzusetzen mit 4 ≡ n mod 5? 

Ja, denn es gilt -1 ≡ (-1+5) ≡ 4 mod 5, beide Zahlen repräsentieren also dieselbe Restklasse.

Reicht das bereits als Begründung, dass n mit Endung auf 1,4,6,9 durch 5 teilbar ist?

Es muss heißen:

4n^{2}+1 ist genau dann durch 5 teilbar,

wenn -1 ≡ n mod 5 oder 1 ≡ n mod 5.

(-1 kannst du auch durch 4 ersetzen.)

Man kann das auch wieder auf die Teilbarkeit durch 5 beziehen und schreiben:

4n^{2}+1 ist genau dann durch 5 teilbar,

wenn n+1 oder n-1 durch 5 teilbar sind.

(Solange wir uns im 10er-System befinden, ist das genau dann der Fall, wenn n auf eine der Ziffern 1, 4, 6 oder 9 endet. Dies gilt aber etwa im 9er-System nicht, daher würde ich das auch nicht ohne einschränkenden Hinweis schreiben.)

---

So, ich habe noch ein paar Gedanken zu b) unter der Berücksichtigung von Faktorisierungsüberlegungen skizziert.

---

Offenbar ist (n-1)*n*(n+1) immer durch 6 teilbar (warum?), so dass wir vereinfachen können zu

nach Definition kann man Restklassen multiplizieren. Also [3]₆ * [1]₆ * [2]₆ für n=3

Da das für alle n von 1 bis 6 bzw. von 0 bis 5 gilt ist der Term durch 6 teilbar.

Jetzt sind wir fertig. (Warum?)

Nach dem Prinzip von gerade: setzt man für n eine beliebige Zahl ein bekommt man irgendwann ein Vielfaches von 7. z.B. für 4 bei (n+2). Das 'kürzt' sich durch mod7 zu 0, womit die ganze summe 0 ist. Und ist bekanntlich konkruent zu 0 mod7.

Ist die Begründung so richtig?

Auf solch eine Faktorisierung wäre ich lange nicht ekommen. Danke für deine Hilfe :)

---

z.B. für 4 bei (n+2). Das 'kürzt' sich durch mod7 zu 0

Ich meine natürlich bei (n+3)

---

Hm... deine Begründung verstehe ich irgendwie nicht.

Ich würde so argumentieren: Von k aufeinander folgenden, ganzen Zahlen ist immer genau eine Zahl durch k teilbar. Daher muss auch das Produkt dieser Zahlen durch k teilbar sein.

Answer 2

a) Für welche ganzzahligen n ist 4n² +1 durch 5 teilbar?

Die kleinsten natürlichen Lösungen n=1  und n=4  sieht man sofort. Darüber hinaus sind es alle n deren Quadrate auf 1 oder 6 enden, also wenn n auf 1, 4, 6, 9 endet.

Answer 3

Es scheint, als würdest du auch grade in der Mathe-Vorlesung in Leipzig sitzen. Hab die gleichen Aufgaben.
Bei b) hab ich noch keinen Ansatz, der was mit Faktorisierung zu tun hat, aber man könnte es auch über Induktion machen. Es wurde ja gesagt, dass n normalerweise eine natürliche Zahl ist

Comments

Zeige zunächst per Induktion über n, dass n⁷ - n durch 7 teilbar ist. Anschließend betrachte die Zerlegung
\(n^7-n=\underbrace{(n-1)\cdot n\cdot(n+1)}_{\in6\mathbb Z}\cdot(n^4+n^2+1)\).
Schließe daraus, dass n⁷ - n ∈ 7ℤ ∩ 6ℤ = 42ℤ ist.

Answer 4

"b) Beweisen Sie, dass n⁷ - n stets durch 42 teilbar ist."

Die Teilbarkeit durch 6 sollte nach den letzten Beiträgen gegessen sein.

Für die Teilbarkeit durch 7 könnte man auch folgendes betrachten:

Ist n durch 7 teilbar, dann ist auch  n⁷ - n stets durch 7 teilbar.

Ist n nicht durch 7 teilbar, so ist n mit der Primzahl 7 teilerfremd, und es gilt nach Fermat

\(n^6\equiv \;1\; mod \;7\).Beidseitige Multiplikation mit n liefert auch für diesen Fall

\(n^7\equiv \;7\; \equiv \;0 \;mod \;7\).