telprobleem

Opgave - NWO 2004 vraag 1

Bepaal het aantal paren van positieve gehele getallen $(a,b)$ met $a\leq b$ waarvoor het kleinste gemeen veelvoud van $a$ en $b$ 2004 is.

Oplossing

Het kgv van twee getallen vind je door de twee getallen te ontbinden in priemfactoren:
Het kgv is het product van alle voorkomende priemfactoren met hun grootste exponent
$2004=2^2*3*167$

doordat $b\geq a$ is $b=2^x*3^y*167$
$x \in \{0,1,2\}$
$y \in \{0,1\}$
wat voor $b$ de mogelijkheden geeft:
$2^0*3^0*167$
$2^0*3^1*167$
$2^1*3^0*167$
$2^1*3^1*167$
$2^2*3^0*167$
$2^2*3^1*167$

$a$ mag geen grotere exponenten hebben dan $b$
en moet bij $2$ exponent $2$ hebben indien bij $b$ $x\neq2$ en exponent $1$ bij $3$ indien $y\neq1$ bij $b$
dat geeft de volgende mogelijkheden voor:
$b=2^0*3^0*167$
$\rightarrow 2^2*3^1$
$b=2^0*3^1*167$
$\rightarrow 2^2*3^1$
$\rightarrow 2^2*3^0$
$b=2^1*3^0*167$
$\rightarrow 2^2*3^1$
$b=2^1*3^1*167$
$\rightarrow 2^2*3^0*167$
$\rightarrow 2^2*3^0$
$\rightarrow 2^2*3^1$
$b=2^2*3^0*167$
$\rightarrow 2^0*3^1*167$
$\rightarrow 2^0*3^1$
$\rightarrow 2^1*3^1$
$\rightarrow 2^2*3^1$
$b=2^2*3^1*167$
$\rightarrow 2^0*3^0*167$
$\rightarrow 2^0*3^1*167$
$\rightarrow 2^1*3^0*167$
$\rightarrow 2^1*3^1*167$
$\rightarrow 2^2*3^0*167$
$\rightarrow 2^2*3^1*167$
$\rightarrow 2^0*3^0$
$\rightarrow 2^0*3^1$
$\rightarrow 2^1*3^0$
$\rightarrow 2^1*3^1$
$\rightarrow 2^2*3^0$
$\rightarrow 2^2*3^1$

m.a.w
$(a,b)$
$(1,2004)$
$(2,2004)$
$(3,668)$
$(3,2004)$
$(4,501)$
$(4,1002)$
$(4,2004)$
$(6,668)$
$(6,2004)$
$(12,167)$
$(12,334)$
$(12,501)$
$(12,668)$
$(12,1002)$
$(12,2004)$
$(167,2004)$
$(334,2004)$
$(501,668)$
$(501,2004)$
$(668,1002)$
$(668,2004)$
$(1002,2004)$
$(2004,2004)$
***
opm.: het antwoord was dus $23$, merk op dat een kortere manier van tellen,
kan met het gebruik van de formule $N(p_1^{e_1}\cdotP_2^{e_2} \cdots P_n^{e_n})=(e_1+1)(e_2+1)\cdots(e_n+1)$

Bvb voor $b=2004$ geeft dit snel $12$ als nr. van mogelijkheden voor $a.$