Folgendes Problem sieht aus wie eine Knobelaufgabe. Aber Vorsicht: es ist ziemlich schwer und widersetzt sich einer Lösung.
Man nehme einige Primzahlen, z.B. M={11,41,61}, und suche eine Kette von Zahlen, von denen jede durch mindestens eine der gewählten Primzahlen teilbar ist, z.B. 121,122,123 (11 × 11, 61 × 2, 41 × 3). Hier hat die Kette die Länge 3. Da die kleinste Primzahl 11 größer ist als die Anzahl 3 der Primzahlen, ist die Länge der Kette auf die Anzahl der Primzahlen begrenzt. Es gibt keine Mehrfachverwendung.
Die Primzahl 2 spielt eine Sonderrolle und ist deshalb nicht erlaubt. Wir wählen eine maximale Primzahl p und sammeln alle ungeraden Primzahlen bis p inklusive in der Menge M zusammen, z.B. p=7 und M={3,5,7}. Hier findet man z.B. die Kette 48,49,50,51 der Länge 4. Die Teilbarkeit durch 3 wurde zweimal verwendet. Dadurch wird diese Kette länger als die Anzahl der Primzahlen: 4>3.
Oder man wähle p=11 und M={3,5,7,11}. Man findet mit 515,516,517,518,519,520 eine Kette der Länge 6. Diesmal wurden die Primzahlen 3 und 5 jeweils zweimal verwendet. Daher ist die Kette mit 6>4 länger als die Anzahl der Primzahlen.
Die Menge M ist durch die maximale Primzahl p eindeutig bestimmt.
Fragestellung: wie lang kann eine Kette zu gegebener maximaler Primzahl p (und damit gegebener Menge M) maximal werden, in der jede Zahl durch irgendeine Primzahl in M teilbar ist?
Für eine konkret gegebene Primzahl p kann man das ausprobieren, denn das Muster wird sich nach endlich vielen Zahlen wiederholen. Das ganze hat mit modularer Arithmetik zu tun. Man kann dann eine Vermutung aufstellen, weil ein Muster erkennbar wird. Lässt sich diese Vermutung allgemein beweisen?
WP: Modulare Arithmetik
WP: Chinesischer Restsatz
WP: Zyklische Gruppe
WP: Einheitengruppe
WP: Restklassenring