Gesucht Zahl n ≤ 5.000.000, welche ein Kongruenzen-System erfüllen

Question

Aufgabe:

Wieviele natürliche Zahlen \( n \leq 5.000.000 \) gibt es, die das folgende Kongruenzensystem erfüllen? Begründen Sie Ihre Antwort!

\( n ≡ 3 \) mod \( 5 \)

\( n ≡ 5 \) mod \( 7 \)

\( n ≡ 6 \) mod \( 11 \)

\( n ≡ 7 \) mod \(13 \)

(Hinweis: Versuchen Sie nicht, die Lösungsmenge explizit auszurechnen.)

Problem/Ansatz:

Wenn ich das Kongruenzensystem mittels chinesischem Restsatz löse, komme ich auf 28.243.

Dies ist aber nur eine Lösung. Daher meine Frage: Welchen Ansatz soll ich verfolgen OHNE die Lösung explizit auszurechnen und um auf die Anzahl der möglichen Lösungen zu kommen?

Comments

Also ich bekomme als Gesamtzahl aller Lösungen über die Gleichung x=3218+k*5.005<=5.000.000 exakt 999 Lösungen.

---

Also durch umstellen dann quasi:  \( k \leq \frac{5.000.000}{5005} - 3218 \). Und das gibt mir dann die Anzahl aller möglichen Lösungen?

---

Wenn du die Lösung n=3218 noch mit zu k=998 zählst und somit auf eine Gesamtzahl an Lösungen von 999 kommst ja.

Bzw. k*5.005<=4.996.782 und somit gerundet k<=998

---

Vielen Dank! Die Lösung wäre also eig. 999, da wir in der Ungleichung eine Lösung abziehen,  oder?

---

Ich dächte schon.

Answer 1

Ich gebe hier mal meinen Lösungsweg an, als jemand der für diese Aufgabe eher mit Betrachtungen und Musterfindung gearbeitet hat.

1.) Die gegebene Zahl n soll bei Division mit 5 einen Rest von 3 lassen.

Es kommen dafür nur Zahlen in Frage, die an der Einerstelle eine 3 oder 8 stehen haben, also:

3,8,13,18,23,28,33,38,...

Diese Zahlen besitzen jeweils einen Abstand von 5.

2.) Die gegebene Zahl n soll bei Division mit 7 einen Rest von 5 lassen.

Von den Zahlen aus 1.) finden sich davon nur folgende Zahlen:

33,68,103,138,173,208,243,...

Diese Zahlen besitzen jeweils einen Abstand von 5*7=35.

3.) Die gegebene Zahl n soll bei Division mit 11 einen Rest von 6 lassen.

Von den Zahlen aus 2.) finden sich davon nur folgende Zahlen:

138,523,908,1293,1678,2063,...

Diese Zahlen besitzen jeweils einen Abstand von 5*7*11=385.

4.) Die gegebene Zahl n soll bei Division mit 13 einen Rest von 7 lassen.

Von den Zahlen aus 3.) finden sich davon nur folgende Zahlen:

3218,8223,13228,18233,23238,28243,...

Diese Zahlen besitzen jeweils einen Abstand von 5*7*11*13=5005.

Somit komme ich auf die allgemeine (Un-)gleichung n=3128+k*5005<=5.000.000.

Bei Auflösen nach k ist k=998.

Addiert man die Lösung n=3128 dazu finden sich 999 Lösungen.

Bei Fehlern / Nicht beachteten Tatsachen / etc. würde ich mich über eine Korrektur freuen.

Answer 2

Aus den ersten beiden Kongruenzen folgt, dass n auch jeweils kongruent zu -2 (sowohl mod 5 als auch mod 7) ist.

Das geht nur, wenn n kongruent zu -2 mod 35 ist.

Wegen 5.000.000:35=142857,14... gibt es 142857 Zahlen mit dieser Eigenschaft. Jede 11. Zahl davon hat den notwendigen Rest mod 11,  und von den verbleibenden Zahlen hat jede 13. den passenden Rest mod 13.

Comments

Dann komme ich genau auf 999. Darf ich fragen wie du auf -2 kommst?