efdee schreef: ↑za 28 nov 2020, 00:04
Zou je dat verschil 120960 - 30240 nader kunnen uitleggen?
We willen de som van de echte delers van n, dus n zelf niet meegerekend.
Voorbeeld:
de delers van 6 zijn 1, 2, 3, 6
de som van deze delers = σ(6) = 1 + 2 + 3 + 6 = 12
de echte delers van 6 zijn 1, 2, 3
de som van deze echte delers = s(6) = 1 + 2 + 3 = 6
De som s(n) van de echte delers van n is de aliquotsom van n
zie bv.
https://nl.wikipedia.org/wiki/Aliquotsom#Voorbeelden
er geldt:
s(n) = σ(n) - n
Voor de eerste oplossing van jouw vraag, n = 30240, is σ(30240) = 120960,
dus s(30240) = σ(30240) - 30240 = 120960 - 30240 = 90720
Op de wiki-pagina staat iets verder naar beneden ook de formule om σ(n) vanuit de priemontbinding van n te bepalen.
Voor n = 30240 = 2^5 * 3^3 * 5 * 7 levert dat:
\(\sigma(n) = \frac{2^6-1}{2-1}\cdot \frac{3^4-1}{3-1}\cdot \frac{5^2-1}{5-1}\cdot \frac{7^2-1}{7-1} = 63\cdot 40 \cdot 6 \cdot 8 = 120960\)
Met deze formule kan je eenvoudig σ(n) berekenen, en daarmee bepalen we vervolgens s(n) = σ(n) - n
Terug naar het oorspronkelijke probleem:
We zoeken 2 verschillende getallen n en m, zodanig dat de som van hun gemeenschappelijke echte delers gelijk is aan n+m.
Maar de gemeenschappelijke delers van n en m zijn precies de delers van g = ggd(n, m) = de grootste gemene deler van n en m.
Voorbeeld:
330 = 2 * 3 * 5 * 11 heeft delers: 1, 2, 3, 5, 6, 10, 11, 15, 22, 30, 33, 55, 66, 110, 165, 330
350 = 2 * 5^2 * 7 heeft delers 1, 2, 5, 7, 10, 14, 25, 35, 50, 70, 175, 350
de gemeenschappelijke delers zijn: 1, 2, 5, 10
en inderdaad: g = ggd(330, 350) = 10, met delers 1, 2, 5, 10
De som van de gemeenschappelijke delers σ(g) is in dit voorbeeld 1 + 2 + 5 + 10 = 18, terwijl we dit gelijk willen hebben aan 330 + 350 = 680. We komen zo dus nog veel te kort. We willen daarom een n en m, zodanig dat g = ggd(n,m) een grote σ(g) heeft.
Als we uitgaan van g (met grote σ(g)), dan kunnen we n = g stellen en m = 2g = 2n
Dan weten we zeker: n ≠ m en ggd(n, m) = ggd(g, 2g) = g
De echte delers van n zijn dan bovendien de echte delers van m die n en m gemeenschappelijk hebben.
We zoeken nu n waarvoor de som van de echte delers = s(n) = σ(n) - n gelijk is aan n + m = 3n,
dus een n waarvoor σ(n) = 4n, ofwel σ(n)/n = 4
De eerste n die voldoet is n = 30240, dan is m = 2n = 60480,
en is de som van de echte delers van n =
s(n) = s(30240) = σ(30240) - 30240 = 120960 - 30240 = 90720 = n + m
efdee schreef:
Hoe kwam je op het idee om m = 2*n te kiezen?
Zouden we uitgaande van g voor n = a*g en m = b*g kiezen (a, b en g onderling relatief priem, a>1, b>1),
dan was nog steeds n ≠ m en ggd(n,m) = ggd(a*g, b*g) = g, maar:
nu zou σ(g) = n + m = a*g + b*g = (a+b)*g moeten zijn, ofwel: σ(g)/g gelijk aan (a+b).
Voor a>1 en b>1 en ggd(a,b)=1 zou dit minimaal a=2 en b=3 betekenen, en dan zoeken we een
g zodanig dat minimaal σ(g) = 5g
Dus als we σ(g)/g zo klein mogelijk willen houden, dan gaat dat het best door a=1 en b=2 te stellen.
Die a=1 gaat dan wel ten koste van n=g in de som σ(g): we moeten nu s(n) = σ(n)-n gelijk stellen aan 3n,
ofwel σ(n) = 4n, ofwel σ(n)/n = 4 maar dat is altijd nog kleiner dan σ(g)/g = 5
Terzijde:
De eerste n waarvoor σ(n)/n = 5 ofwel σ(n) = 5n is n = 14182439040 = 2^7 * 3^4 * 5 * 7 * 11^2 * 17 * 19.
σ(14182439040) = 70912195200
s(14182439040) = 70912195200 - 14182439040 = 56729756160
We kunnen nu kiezen:
- ofwel:
n = 14182439040; m = 3n = 42547317120
dan is n + m = 4n = 56729756160 = s(n) = de som van de echte delers van n
- ofwel:
g = 14182439040; n = 2g = 28364878080; m = 3g = 42547317120
nu is n + m = 5g = 70912195200 = σ(g) = de som van alle delers van g (nu zijn alle delers van g, inclusief g zelf, precies alle echte delers van zowel n als m).