de som van gemeenschappelijke delers

Moderators: dirkwb, Xilvo

Reageer
Berichten: 415

de som van gemeenschappelijke delers

Naar aanleiding van perfecte getallen. (6 28 496 8128 ...)

Kan de som van de gemeenschappelijke delers van twee (of meer) verschillende telgetallen gelijk zijn aan de som van die getallen?
Bij n = 1 x n wordt de 1 wel meegerekend bij de som maar de n niet.

Met programmeren is dat antwoord vast wel te vinden. Maar kan het probleem ook met een algoritme opgelost worden?
Is er een voorbeeld bekend? Of kan aangetoond worden, dat het probleem geen oplossing heeft?

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.
Berichten: 232

Re: de som van gemeenschappelijke delers

Stel m = 2*n, dan zijn alle delers van n tevens delers van m.
Nu zoeken we een overvloedige n
(zie https://nl.wikipedia.org/wiki/Overvloedig_getal)
zodanig dat de som van de delers van n (zonder n zelf) gelijk is aan m + n = 3*n

Via de computer vind ik als eerste mogelijkheid:
n=30240, m=60480
som van de delers van n = 120960
som van de delers van n zonder n zelf = 120960 - 30240 = 90720
n + m = 30240 + 60480 = 90720

verder ook:
n=32760, m=65520
n=2178540, m=4357080

NOOT: dit zijn alleen getallen n en m in de vorm m = 2*n, er bestaan waarschijnlijk ook nog andere oplossingen.

Berichten: 415

Re: de som van gemeenschappelijke delers

Knap werk!
Zou je dat verschil 120960 - 30240 nader kunnen uitleggen?

Berichten: 415

Re: de som van gemeenschappelijke delers

Hoe kwam je op het idee om m = 2*n te kiezen?
Het is duidelijk dat alle delers van n tegelijk de gemeenschappelijke delers zijn.

Berichten: 232

Re: de som van gemeenschappelijke delers

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).

Berichten: 232

Re: de som van gemeenschappelijke delers

AANVULLING:
Hier nog een oplossing voor 3 verschillende getallen n, m en k, waarbij de som van alle delers die een echte deler zijn van zowel n als m als k gelijk is aan n + m + k.

Neem m=2n en k=3n, dan is g = ggd(n,m,k) = n
De som van alle echte delers van (g = n) is nu s(n) = σ(n) - n
We zoeken dus een n waarvoor
s(n) = σ(n) - n = n + 2n + 3n = 6n
ofwel
σ(n) = 7n
ofwel
σ(n)/n = 7

Kies n = 141310897947438348259849402738485523264343544818565120000
= 2^32⋅3^11⋅5^4⋅7^5⋅11^2⋅13^2⋅17⋅19^3⋅23⋅31⋅37⋅43⋅61⋅71⋅73⋅89⋅181⋅2141⋅599479

dan is σ(n) = 989176285632068437818945819169398662850404813729955840000 = 7n
en s(n) = 847865387684630089559096416430913139586061268911390720000 = 6n

Dit geeft de 3 verschillende getallen
n = 141310897947438348259849402738485523264343544818565120000
m = 2n = 282621795894876696519698805476971046528687089637130240000
k = 3n = 423932693842315044779548208215456569793030634455695360000
waarbij
n + m + k = 847865387684630089559096416430913139586061268911390720000 = s(n)

Reageer