1+2+3+4+5...+n

[obscenedude]

Bepaal de kleinste waarde van n waarvor geldt:

1+2+3+4+5...+n is een veelvoud van 1000

[arie]

Er moet gelden:
1000 | (1/2)*n*(n+1)

2000 | n*(n+1)

(2^4 * 5^3) | n*(n+1)

dan moet ofwel (1):
125 | n+1
16 | n
ofwel (2):
125 | n
16 | n+1

ofwel (3):
25 | n+1
80 | n
ofwel (4):
25 | n
80 | n+1

ofwel (5):
5 | n+1
400 | n
ofwel (6):
5 | n
400 | n+1

ofwel (7):
2000 | n+1

ofwel (8):
2000 | n


Stel (1), dan zijn er een gehele x en y zodat:

n = 125x-1
n = 16y

waaruit volgt:

125x - 16y = 1

Via Euclides geldt:
127=7*16+13
16=1*13+3
13=4*3+1
3=3*1+0
en terugwerkend:
1=13-4*3
=13-4*(16-1*13)
=-4*16+5*13
=-4*16+5*(125-7*16)
=5*125-39*16

Dus een enkele oplossing van (1) is
x0=5
y0=39
en de algemene oplossing:
x = x0 + 16t = 5 + 16t
y = y0 +125t = 39 + 125t
en n = 16*39 + 16*125*t = 624 + 2000t
voor t=0 levert dit de kleinste positieve n: n=624

Uit (2) volgt vergelijkbaar:

-125x + 16y = 1
met als oplossingen (direct uit bovenstaande afleiding):
x0=-5
y0=-39
en algemene oplossing:
x = -5 + 16t = 11 + 16t'
y = -39 + 125t = 86 + 125t'
en n = 125*x = 125*(11 + 16t') = 1375 + 2000t'
voor t=0 levert dit als kleinste positieve oplossing n=1375

Mogelijkheden 3 t/m 6 leveren geen oplossing omdat de ggd(a,b) in ax+by=1 groter is dan de uitkomst 1.
Uit (7) volgt direct n=1999+2000t
Uit (8) volgt direct n=2000+2000t

Het antwoord is dus n=624.

Alle positieve n waarvoor dit geldt zijn:
{624, 1375, 1999, 2000, 2624, 3375, 3999, 4000, 4624, 5375, 5999, 6000, 6624, 7375, 7999, 8000, ...}