Klopt dit:
Als
dan geldt:
Als ik wil bewijzen, kom ik zo uit:
stel ggd(n,k)=a
dan a|n, a|k, a|n-k a|n!
een factor uit k! deelt niet n, n|n nPr k dus a|n nPr k dus ggd{n,k}|{n choose k} voor k\not=n en k\not=n
n nPr k wil zeggen dat je vanaf n, k factoren met elkaar vermenigvuldigd met verschil 1. Hoe zeg je dat mooi?
Vb: 5 nPr 3=5*4*3=60, 10 nPr 7=10*9*8*7*6*5*4=604800
Je zou dit kunnen gebruiken voor priemfactorisatie, maar dat kost denk ik uiteindelijk net zoveel rekenkracht als een getal delen door de priemgetallen tot