WisFaq!

Bewijs van een ggd

Hoi, ik wil volgende stelling bewijzen:
Voor alle a,b natuurlijke getallen geldt: ggd((2^a)-1,(2^b)-1) = (2^ggd(a,b))-1. Ik heb me er al onnozel op gezocht. Ik heb zoekmethodes al geprobeerd:
1) (2^a)-1 en (2^b)-1 binair schrijven , mss handig omdat dat dan allemaal enen zijn.
2) Stel ggd(a,b)=p1* .. *pn , dan geldt (2^p1)-1 deelt (2^a)-1, ..., (2^pn)-1 deelt (2^a)-1,(2^p1)-1 deelt (2^b)-1 enz. Daarbij had ik het vermoeden dat als pi en pj priem zijn,ggd((2^pi)-1,(2^pj)-1)=1.
Ik zit echt muurvast, alle hulp is welkom.

Dank bij voorbaat.

Jan-Willem
21-12-2005

Antwoord

Dag Jan-Willem,

Je eerste observatie is zeker correct, al denk ik dat het een beetje gevaarlijk is om zo te werken, want hoeft een deler van een getal met allemaal enen daarom een getal te zijn met allemaal enen, of zelfs een getal dat een bepaalde periode heeft? Dikwijls wel, zoals in 111111=1001*111=11*10101, maar bewijzen dat dit altijd zo is, lijkt mij andere koek.

Je tweede zoekmethode is zeker wel juist, dat is een rekenregel. Het vermoeden dat erbij hoort is mij onbekend, het lijkt mij sterk...

Zo zou ik de opgave aanpakken:
Stel G=ggd(a,b)
Dan geldt a=mG en b=nG met ggd(m,n)=1.
Het linkerlid wordt dan:
ggd(2^mG-1,2^nG-1)
= ggd((2^G-1)(2^G(m-1)+2^G(m-2)+...+1),(2^G-1)(2^G(n-1)+2^G(n-2)+...+1))
= (2^G-1) ggd(2^G(m-1)+2^G(m-2)+...+1,2^G(n-1)+2^G(n-2)+...+1)

waarbij die eerste overgang een toepassing is van de formule x^r-1=(x-1)(x^r-1+x^r-2+...+x+1)

Dus als je nog kan bewijzen dat heel die ggd uit de laatste uitdrukking gelijk is aan 1, dan ben je er. Noem misschien 2^G=t, dan moet je bewijzen dat åtⁱ (i=0 tot n-1) en åtⁱ (i=0 tot m-1) ggd 1 hebben als m en n ggd 1 hebben.

Ik heb er een bewijsje voor gevonden, tis wel nogal omslachtig, misschien kan het eenvoudiger maar dat zie ik toch niet meteen. Goed, stel dat er een priem p bestaat die een deler is van åtⁱ (i=0 tot n-1) en van åtⁱ (i=0 tot m-1). Dan is p zeker oneven (immers, t is een macht van 2, dus je telt telkens allemaal even getallen op, plus 1)

Stel mn. p is een deler van die twee uitdrukkingen, dus ook van hun verschil, dus p is een deler van åtⁱ (i=n tot m-1), dus p is een deler van tⁿåtⁱ (i=0 tot m-n-1), dus p is een deler van åtⁱ (i=0 tot m-n-1). En door dan telkens het juiste verschil te nemen van zulke uitdrukkingen waarvan p een deler is, kan je aantonen dat p een deler is van åtⁱ (i=0 tot ...) waarbij op die puntjes een steeds lagere exponent komt. Dan is het nog aan jou om aan te tonen dat, als m en n ggd 1 hebben, je die exponent tot nul kan laten zakken (wat dus een strijdigheid geeft p|1). Dit lukt niet als m en n een gemeenschappelijke factor hebben.

Als je voor een bepaalde stap een eenvoudiger bewijs vindt mag je het altijd laten weten...

Groeten,
Christophe.

Christophe
28-12-2005