Tag archieven: ontbinding in priemfactoren

Ontbinding in priemfactoren van n!

Geplaatst op door
We weten dat n! = n.(n-1)…1. We willen nu onderzoeken wat de exponent is van een priemgetal p in de ontbinding in factoren van n!
  • Schrijf  n in het p-tallig stelsel: n=n_lp^l+n_{n-1}p^{l-1}+\cdots+n_1p+n_0.
  • Elk veelvoud van p tussen 1 en n levert 1 factor p in de ontbinding van n!. Zo zijn er \lfloor \dfrac{n}{p} \rfloor= n_lp^{n-1}+n_{l-1}p^{l-2}+\cdots+n_1, want \dfrac{n_0}{p}<1.
  • Elk veelvoud van p^2 tussen 1 en n levert  een extra factor p in de ontbinding van n!. Zo zijn er \lfloor \dfrac{n}{p^2} \rfloor= n_lp^{n-2}+n_{l-1}p^{l-3}+\cdots+n_2, want \dfrac{n_1}{p}+\dfrac{n_0}{p^2}<1
  • Noteer met v_p(n!) de exponent van p in de ontbinding van n!.
  • Dan is:  v_p(n!)=( n_lp^{n-1}+n_{l-1}p^{l-2}+\cdots+n_1)+(n_lp^{n-2}+n_{l-1}p^{l-3}+\cdots+n_2)+\cdots +(n_lp+n_{l-1})+n_l
  • Herschikking geeft: v_p(n!)=n_l(p^{n-1}+p^{n-2}+\cdots+p+1)+n_{l-1}(p^{l-2}+\cdots+1)+\cdots+n_2(p+1)+n_1
  • Dus v_p(n!)=n_l\dfrac{p^n-1}{p-1}+n_{l-1}\dfrac{p^{n-1}-1}{p-1}+\cdots+n_2\dfrac{p^2-1}{p-1}+n_1.
  • Noteer n_l+n_{l-1}+\cdots+n_1+n_0=s_p(n).
  • Bijgevolg is v_p(n!)=\dfrac{1}{p-1}(n-s_p(n)).

Voorbeeld : 12!=479001600=2^{10}.3^5.5^2.7.11

  • 12 = 1100 in het binair talstelsel, dus is v_2(12!)=12-(1+1+0+0)=10.
  • 12 = 110 in het drietallig stelsel, dus is v_3(12!)=\dfrac{1}{2}(12-(1+1))=5.
  • 12 = 22 in het vijftallig stelsel , dus is v_5(12!)=\dfrac{1}{4}(12-(2+2))=2.
  • 12 = 15 in het zeventallig stelsel , dus is v_7(12!)=\dfrac{1}{6}(12-(1+5))=1.
  • 12 = 11 in het elftallig stelsel , dus is v_{11}(12!)=\dfrac{1}{10}(12-(1+1))=1.

Hoofdstelling van de rekenkunde

Geplaatst op door

Elk samengesteld getal kan geschreven worden als het product van kleinere factoren. Als minstens 1 van beide samengesteld is , kan men die ook weer schrijven als product van kleinere factoren. Zo kan men doorgaan tot er slechts priemgetallen als factoren overblijven. men kan een samengesteld getal in het algemeen op verschillende manieren via een aantal tussenstappen in priemgetallen ontbinden. Het uiteindelijk resultaat, de ontbinding in priemfactoren, is steeds hetzelfde. Dit resultaat staat bekend als de hoofdstelling van de rekenkunde:

    \[\begin{center}De ontbinding in priemfactoren van een \\ natuurlijk getal is eenduidig bepaald.\end{center}\]

Deze eigenschap is in andere getalsysytemen niet noodzakelijk waar. Beschouw de verzameling van de even getallen \left\{2,4,6,\cdots \right\}. Sommige ervan kan men schrijven als het product van even factoren, bijvoorbeeld 20=2.10. Bij andere is dat niet mogelijk. We noemen even getallen die niet het product zijn van even factoren even-priemgetallen. Een even getal is te schrijven als product van even-priemgetallen, maar zo een ontbinding hoeft niet eenduidig te zijn. Zo is 420=6.70=10.42

Als een getal ontbonden is in priemfactoren, dan kan men het aantal delers bepalen. Stel dat n=2^{e_1}.3^{e_2}.5^{e_3}. \ldots .p_k^{e_k} dan heeft n juist (e_1+1)(e_2+1)(e_3+1).\ldots.(e_k+1) delers.

woestijn