WisFaq!

Modulo rekenen en bewijzen

Ik heb daarnet ook al eens gemaild. Maar nu heb ik nog een bewijs gezien namelijk het volgende:

Het getal p is een priemgetal. h en k zijn niet-negatieve gehele getallen waarvoor geldt: h+k=p-1.
Bewijs nu dat: h!*k!º(-1)^(k+1)mod p

Hoe moet ik dit dan gaan bewijzen??

Groetjes

Van de Velde
4-1-2004

Antwoord

NB: Johan (aka Andros) heeft mij gemeld dat hij ongeveer dezelfde vraag onlangs ook heeft opgelost, zie dus ook:
showrecord3.asp?id=17387

Hieronder volgt mijn oorspronkelijke antwoord.

Hallo,

Als je modp werkt kan je h! anders schrijven:
1·2·...·h $\equiv$ -(p-1)·(-(p-2))·(-(p-3))·...·(-(p-h))
$\equiv$ (-1)^h·(p-h)(p-h+1)...(p-1)

Maar p-h=k+1
Dus k!h! = 1·2·...·k·h!
$\equiv$ 1·2·...·k·(k+1)·(k+2)·...·(p-1)·(-1)^h
= (p-1)!(-1)^h

p is oneven (voor p=2 is de bewering triviaal correct), dus h en k zijn ofwel beide even, ofwel beide oneven, dus (-1)^h=(-1)^k.

Rest nog te bewijzen dat (p-1)!$\equiv$-1 modp...

Dat is wel mogelijk, maar met nogal een lastig argument vrees ik...

Als je naar de structuur van $\mathbf{Z}$/p$\mathbf{Z}$ kijkt weet je dat elk element a een uniek invers b heeft, dus zodanig dat
ab$\equiv$1 mod p. Bovendien verschilt die a telkens van de b, behalve wanneer a=1 of p-1. (wegens eigenschappen van een veld: X²=1 heeft hoogstens twee oplossingen)

Dus in dat product (p-1)! krijg je:
1·(a·b)·(c·d)·(e·f)·...·(p-1)
waarbij ab, cd, ef,... telkens 1 zijn modp.

Vb p=7:
6!=1·(2·4)·(3·5)·6

Vb p=11:
10!=1·(2·6)·(3·4)·(5·9)·(7·8)·10

Dus dit geeft inderdaad (p-1) mod p, dus -1 mod p.

Hiermee is de stelling bewezen. Misschien was er wel een eenvoudiger bewijs voor die (p-1)!, maar dat is mij dan toch ontgaan...

Groeten,

Christophe
4-1-2004