De digitale vraagbaak voor het wiskundeonderwijs

home |  vandaag |  gisteren |  bijzonder |  prikbord |  gastenboek |  wie is wie? |  contact

HOME

samengevat
vragen bekijken
een vraag stellen
hulpjes
zoeken
FAQ's
links
twitter
boeken
help

inloggen

colofon

  \require{AMSmath} Printen

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-Wi
Student universiteit Belgi - woensdag 21 december 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(2mG-1,2nG-1)
= ggd((2G-1)(2G(m-1)+2G(m-2)+...+1),(2G-1)(2G(n-1)+2G(n-2)+...+1))
= (2G-1) ggd(2G(m-1)+2G(m-2)+...+1,2G(n-1)+2G(n-2)+...+1)

waarbij die eerste overgang een toepassing is van de formule xr-1=(x-1)(xr-1+xr-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 2G=t, dan moet je bewijzen dat ti (i=0 tot n-1) en ti (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 ti (i=0 tot n-1) en van ti (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 ti (i=n tot m-1), dus p is een deler van tnti (i=0 tot m-n-1), dus p is een deler van ti (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 ti (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
Vragen naar aanleiding van dit antwoord? Klik rechts..!
woensdag 28 december 2005



klein |  normaal |  groot

home |  vandaag |  bijzonder |  twitter |  gastenboek |  wie is wie? |  colofon

©2001-2021 WisFaq - versie 3