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.