---

Hej,

Er der nogen der kan lave et elementært bevis for følgende:

/ n+2 \ { n/3 hvis 3|n }
| | == { } mod n
\ n-1 / { 0 ellers }

hvor == betegner "kongruens" (sædvanligvis skrevet med tre vandrette
streger)?

Søren

---

Søren Galatius Smith wrote:
>
> Hej,
>
> Er der nogen der kan lave et elementært bevis for følgende:
>
> / n+2 \ { n/3 hvis 3|n }
> | | == { } mod n
> \ n-1 / { 0 ellers }
>
> hvor == betegner "kongruens" (sædvanligvis skrevet med tre vandrette
> streger)?

Jeg håber, følgende er elementært nok, og at det er et bevis(!).
Måske tænker du på noget andet med "elementært"?

Nå, venstresiden skriver jeg som

/ n+2 \ (n+2)!
| | = ------------ = n(n+1)(n+2)/6.
\ n-1 / (n-1)!*3!

Antag først, at m = n/3 er et helt tal, og lad S(k) betegne summen
af de første k naturlige tal. Regner vi modulo 3, er da

S(n) = 1 + ... + 3m
== 1 + 2 + 0 + 1 + 2 + 0 + ... + 0 == 0 (mod 3),

så 3 | S(n), hvoraf n = m*3 | m*S(n), dvs

m*S(n) == 0 (mod n).

Regner vi videre på denne kongruens ved at lægge m*(n+1) til på
højre og venstre side,

m*(S(n) + n+1) == m*(n+1) (mod n),

og bruger vi S(n) + n+1 = S(n+1) = (n+1)(n+2)/2 og m*(n+1) == m
(mod n), får vi som ønsket

n/3*(n+1)(n+2)/2 == n/3 (mod n).


Hvis på den anden side 3 ikke går op i n, må 3 | (n+1)(n+2) (fordi
3 går op i den ene faktor), ligesom 2 | (n+1)(n+2). Da 2 og 3 er
primiske, går således 2*3 op i (n+1)(n+2), hvorfor trivielt

n | (n+1)(n+2)/(2*3) * n,

eller omformuleret: n(n+1)(n+2)/6 == 0 (mod n). q.e.d.

--
Jonas Møller Larsen

---

Jonas Møller Larsen <jml@phys.au.dk> writes:

> eller omformuleret: n(n+1)(n+2)/6 == 0 (mod n). q.e.d.

Æh, ja. Det var jo simpelt nok.

---

galatius+usenet@imf.au.dk (Søren Galatius Smith) writes:

> Hej,
>
> Er der nogen der kan lave et elementært bevis for følgende:
>
> / n+2 \ { n/3 hvis 3|n }
> | | == { } mod n
> \ n-1 / { 0 ellers }
>
> hvor == betegner "kongruens" (sædvanligvis skrevet med tre vandrette
> streger)?

Venstresiden er n*(n+1)*(n+2)/6 (se evt. Jonas' bevis hvis det ikke er
klart).

Hvis 3|n:
Vi starter med at forkorte med 3 og få (n/3*(n+1)*(n+2))/2 på
venstresiden, dernæst ganger vi ind i parentesen og får
(n^3/3+n^2)/2+n/3. Uanset om n er lige eller ulige ser man let at
parentesen er lige (begge addender er enten lige eller ulige), og første
led er følgeligt deleligt med n, og udtrykket er derfor kongruent med n/3.

Hvis 3 ikke går op i n:
3 vil gå op i enten (n+1) eller (n+2) og desuden vil det ene af disse
tal være lige. Følgelig går 6 op i de to faktorer, og det ses at
vesntresiden er kongruent med 0.

Så tror jeg ikke det bliver mere elementært.

..Henrik

--
"The ultimate goal of mathematics is to eliminate all need for
intelligent though" - Graffiti af ukendt i 'Concrete Mathematics'