primzahlen und restklassen
-
Hallo,
ich hab von hier http://www.c-plusplus.net/forum/286485-20 das von camper gelesen:
Alle Primzahlen ausßer 2, 3 haben bei der Division durch 6 entweder den Rest 1 oder 5. Es genügt also, nur diese Restklassen zu betrachten - damit ist die Zahlenmenge schon mal auf ein Drittel reduziert.
Oder man eliminiert auch noch die 5 und betrachtet nur noch die Restklassen
{1,7,11,13,17,19,23,29} mod 30 - das ist dann nur noch 4/15 der Ausgangsmenge, usw.jetzt hab ich einige fragen dazu:
wie kommt man auf die restklassen?
kann man als divident jede beliebige zahl nehmen, oder wie muss man sie auswählen und warum eliminiert sich die 5 dann mod 30?
tut mir leid wenn ich das so frage, aber in der schule hatten wir noch nichts der gleichen gemacht
mfg und danke schon mal
-
Naja, 6=2*3, 30=2*3*5.
Wenn eine Zahl beim Teilen durch 6 den Rest 0, 2 oder 4 lässt, ist sie durch 2 teilbar, wenn sie den Rest 3 lässt, ist sie durch 3 teilbar, also keine Primzahl (wenns nicht 2 oder 3 selber sind). Analog dann für die 30er-Reste.
-
das heißt, man könnte auch 42 nehmen, da 2 * 3 * 5 * 7 = 42 ist und die restklassen wären dann: 1, 11, 13, 17, 19 , 23, 29, 31, 37 und 41.
see ich das so richtig?
-
2 * 3 * 5 * 7 = 42
Willst du das nicht lieber noch einmal nachrechnen?
-
42=2*3*7. Und da die 5 fehlt, musst Du auch die 5, 15, 25 und 35 noch dazunehmen. Ansonsten aber richtig.
-
wer rechnen kann ist klar im vorteil
also wenn man jetzt die 22 = 2 * 11 nimmt, sind die restklassen: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, und 21?
-
Ohne die 11
-
ah ja natürlich ist klar
jetzt hab ich es aber verstanden
-
