Priemgetallen in het 13 tallig stelsel

[dragonitor]

Als je wil weten of een getal een priemgetal is in een 10 tallig stelsel vallen de getallen die op de volgende cijfers eindigen af(als het op 1 van de volgende cijfers eindigen is het geen priemgetal(met uitzondering de priemgetallen onder 8)):

0, 2, 4, 5, 6, 8

Maar als je priemgetallen berekent in het 13-tallig stelsel vallen de getallen die op de volgende cijfers eindigen af(als het op 1 van de volgende cijfers eindigen is het geen priemgetal(met uitzondering de priemgetallen onder C)):

0, 2, 3, 4, 6, 8, 9, A, C

Dit streept veel meer priemgetallen weg!

[EvilBro]

32 = 3*13 + 2 = 39 + 2 = 41 is een priemgetal.

[dragonitor]

32 = 3*13 + 2 = 39 + 2 = 41 is een priemgetal.

Oeps ik bedoelde het 12 tallig stelsel, foutje

Als je wil weten of een getal een priemgetal is in een 10 tallig stelsel vallen de getallen die op de volgende cijfers eindigen af(als het op 1 van de volgende cijfers eindigen is het geen priemgetal(met uitzondering de priemgetallen onder 8)):

0, 2, 4, 5, 6, 8

Maar als je priemgetallen berekent in het 12-tallig stelsel vallen de getallen die op de volgende cijfers eindigen af(als het op 1 van de volgende cijfers eindigen is het geen priemgetal(met uitzondering de priemgetallen onder C)):

0, 2, 3, 4, 6, 8, 9, A

Dit streept veel meer priemgetallen weg!

[jazzer]

49 = 4*12 + 9 = 48 + 9 = 57 is een priemgetal ! Dus ten onrechte weggestreept.

[dragonitor]

49 = 4*12 + 9 = 48 + 9 = 57 is een priemgetal ! Dus ten onrechte weggestreept.

Hmm, dan heb ik een grote fout begaan ja,

ik zat te denken: 12 kan je delen door 4 dus dan heb je 3 en 6 en 9 die kunnen wegworden gestreept

want 10 kan je delen door 2 dus dan heb je 5, maar dat is verkeerd gedacht want delen werkt ook anders in een meertallig stelsel

[Safe]

57 (10 tst) is geen priemgetal.

[EvilBro]

Even voor de toekomst: zo kun je dit misschien bekijken zodat je beter ziet wat er gebeurt (ik doe het voor een zestallig-stelsel):

\(6\cdot a + 0 = 2\cdot (3 \cdot a)\)

: nooit een priemgetal.

\(6\cdot a + 1\)

: misschien een priemgetal.

\(6\cdot a + 2 = 2 \cdot (3 \cdot a + 1)\)

: nooit een priemgetal.

\(6\cdot a + 3 = 3 \cdot (2 \cdot a + 1)\)

: nooit een priemgetal.

\(6\cdot a + 4 = 2 \cdot (3 \cdot a + 2)\)

: nooit een priemgetal.

\(6\cdot a + 5\)

: misschien een priemgetal.

Kortom in een zestallig-stelsel hoef je alleen de getallen te controleren die eindigen op een 1 of een 5. Misschien kun je hetzelfde een keer doen voor een twaalftallig-stelsel. Je zal dan ook een verband zien met het zestallig-stelsel.

[dragonitor]

ah dan klopt mijn theorie toch wel:

0 -

1

2 -

3 -

4 -

5

6 -

7

8 -

9 -

A -

B

dus alles dat eindigt op de 1 de 5, de 7 en de B is dus een priemgetal

dat zijn er 4 op de 12

bij het 6 tallig-stelsel is het dan

2 op de 6

dat scheelt in beide gevallen dus evenveel

[EvilBro]

dat scheelt in beide gevallen dus evenveel

En dat is niet zo raar, want 12 = 2*6.

[Erik Leppen]

Het is eigenlijk best logisch dat dit zo werkt. Als je van je getal in het N-tallig talstelsel het laatste cijfer weghaalt is het resultaat een getal dat eindigt op 0 in het N-tallig stelsel, en dus deelbaar is door N (net zoals decimaal 93 - 3 = 90 op een nul eindigt en dus deelbaar is door tien). Dit voorstuk heeft dus alle delers van N als deler. Als je laatste cijfer nou een deler van N als deler heeft, heeft je hele getal, dat de som is van dat voorstuk en laatste cijfer, die deler, en is het dus geen priemgetal.

Een priemgetal in het 12-tallig stelsel kan dus niet eindigen op 9, want dan is het 12 a + 9 voor een zekere a, en dus deelbaar door 3.

Het laatste cijfer van een priemgetal in basis N, is dus een cijfer dat geen delers gemeenschappelijk heeft met N.

Voor N = 12 zijn dat 1, 5, 7 en B (11). Deze vier getallen noemen we overigens onderling ondeelbaar of relatief priem met N. Het zijn de getallen die modulo 12 een inverse hebben.

En dat is niet zo raar, want 12 = 2*6.

Dat is niet de (hele) reden. Zoals hier boven laten zien is het aandeel getallen dat overblijft als kandidaat-priemgetallen, gelijk aan het aandeel cijfers dat relatief priem is en dat aantal is

\(N \prod_{p | N \ priem} (p - 1)/p\)

en omdat 6 en 12 dezelfde priemdelers hebben hebben ze ditzelfde aandeel (nl. (2-1)/2 * (3-1)/3 en dat is inderdaad 1/3).

[dragonitor]

Het is eigenlijk best logisch dat dit zo werkt. Als je van je getal in het N-tallig talstelsel het laatste cijfer weghaalt is het resultaat een getal dat eindigt op 0 in het N-tallig stelsel, en dus deelbaar is door N (net zoals decimaal 93 - 3 = 90 op een nul eindigt en dus deelbaar is door tien). Dit voorstuk heeft dus alle delers van N als deler. Als je laatste cijfer nou een deler van N als deler heeft, heeft je hele getal, dat de som is van dat voorstuk en laatste cijfer, die deler, en is het dus geen priemgetal.

Een priemgetal in het 12-tallig stelsel kan dus niet eindigen op 9, want dan is het 12 a + 9 voor een zekere a, en dus deelbaar door 3.

Het laatste cijfer van een priemgetal in basis N, is dus een cijfer dat geen delers gemeenschappelijk heeft met N.

Voor N = 12 zijn dat 1, 5, 7 en B (11). Deze vier getallen noemen we overigens onderling ondeelbaar of relatief priem met N. Het zijn de getallen die modulo 12 een inverse hebben.

Dat is niet de (hele) reden. Zoals hier boven laten zien is het aandeel getallen dat overblijft als kandidaat-priemgetallen, gelijk aan het aandeel cijfers dat relatief priem is en dat aantal is

\(N \prod_{p | N \ priem} (p - 1)/p\)

en omdat 6 en 12 dezelfde priemdelers hebben hebben ze ditzelfde aandeel (nl. (2-1)/2 * (3-1)/3 en dat is inderdaad 1/3).

Jep, maar het kan het proces vergemakkelijken omdat je die cijfers dan niet hoeft na te checken.

[McMotion]

Jep, maar het kan het proces vergemakkelijken omdat je die cijfers dan niet hoeft na te checken.

maar is het dan echt het proces vergemakkelijken? even ter illustratie: als je het getal N in het (N+1)-tallig stelsel opschrijft, dan kan je álle priemgetallen wegstrepen door alleen naar het laatste cijfer te kijken.