Beweis zur Division mit Rest

Question

Unsere Aufgabe lautet:

1. Beweisen oder widerlegen Sie: Wenn a bei Division durch 3 den Rest 1 lässt, so lässt auch a² bei Division durch 3 den Rest 1.

2. Beweisen oder widerlegen Sie: Wenn a bei Division durch 3 den Rest 2 lässt, so lässt auch a² bei Division durch 3 den Rest 2.

 

Ich habe Folgendes versucht:

zu zeigen: a und a² lassen bei Division durch 3 den gleichen Rest

sei: a ≡ a² (mod 3)

Dann gilt aufgrund der Symmetrie:

a² ≡ a (mod 3)

⇒ 3 ι a² - a ("3 teilt...")

⇒ V_t∈ℤ 3t = a² - a

⇒ 3t = a² - (q•m+r)  (laut der Defintion der Division mit Rest a=q•m+r)

⇔ a = √(qm + r + 3t)

Dies stellt einen Widerspruch zur Annahme, dass a und a2 den gleichen Rest bilden dar, denn wenn man die Wurzel aus a² zieht müsste a herauskommen. Damit ist widerlegt, dass a und a² die gleichen Reste bilden können.

 

Mein Problem ist jetzt aber, dass das so allgemein nicht stimmt, denn für konkrete Beispiele ist es so, dass der erste Fall (Rest 1) richtig ist, der zweite (Rest 2) aber nicht.

Nur wie zeige ich das? Wo habe ich einen Fehler gemacht?

Answer 1

Ich machs mal anders:

a lässt bei Division durch 3 den Rest 1

=> a = 3 k + 1 , ( k ∈ N )

=> a ² = ( 3 k + 1 ) ² = 9 k ² + 6 k + 1 = 3 ( 3 k ² + 2 k ) + 1

=> auch a ² lässt bei Division durch 3 den Rest 1

Also ist die Behauptung wahr.

 

a lässt bei Division durch 3 den Rest 2

=> a = 3 k + 2 , ( k ∈ N )

=> a ² = ( 3 k + 2 ) ² = 9 k ² + 12 k + 4 = 3 ( 3 k ² + 4 k + 1 ) + 1

=> a ² lässt bei Division durch 3 den Rest 1

Also ist die Behauptung falsch! Statt dessen gilt:

Wenn a bei Division durch 3 den Rest 2 lässt, dann lässt a ² bei Division durch 3 den Rest 1

Comments

Vielen Dank JotEs!

Diesen Lösungsweg verstehe ich sogar noch besser!

---

Mal für mich zum Verständnis:

Was ist denn an dieser Antwort anders, insbesondere was macht sie verständlicher als die Erste?

---

Vielleicht, weil sie einfach in mehreren Schritten verafsst ist.

Eigentlich steht da ja genau das gleiche, aber die erste Antwort fand ich nicht so schön übersichtlich.


Es hatte rein gar nichts mit dem Inhalt, sondern einfach nur mit der Textverteilung zu tun. Quasi Verständnisförderung über das Auge. :-)

Answer 2

3|a²-a folglich existiert (kein Allquantor) ein natürliche Zahl t mit 3t=a²-a, also a²=3t+a.

Da o.E. a positiv ist gilt a=√(3t+a).

Hier gibt es keinerlei Widerspruch zu irgendwas da nach t so gewählt wurde, dass 3t+a=a².


Beweis ohne Modulo-rechnung (mit ist es ein Einzeiler):

Gelte a=3t+1 für eine ganze Zahl t. Dann ist a²=(3t+1)²=9t²+6t+1=3(3t²+2t)+1; a² hat also wieder Rest 1.

Gilt a=3t+2 für eine ganze Zahl t, so ist a²=(3t+2)²=9t²+12t+4=3(t²+4t+1)+1; a² hat also Rest 1.

Alternativ kann man durch ein beliebiges Gegenbeispiel eine Aussage widerlegen.

Comments

Wie sähe denn der Beweis mit Modulo-Rechnung aus?