Springen naar inhoud

Bewijs van een vergelijking


  • Log in om te kunnen reageren

#1

zijtjeszotjes

    zijtjeszotjes


  • >100 berichten
  • 171 berichten
  • Ervaren gebruiker

Geplaatst op 16 december 2005 - 20:53

hoi!
hoe is te bewijzen

ggd(2a-1,2b-1)=-1+2ggd(a,b)
thanx

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 16 december 2005 - 22:11

tip: schrijf de getallen eens binair
In theory, there's no difference between theory and practice. In practice, there is.

#3

Nabuko Donosor

    Nabuko Donosor


  • >25 berichten
  • 94 berichten
  • Ervaren gebruiker

Geplaatst op 21 december 2005 - 18:50

Bedankt voor de tip hoor, TD, maar ken je het bewijs ook? Ik heb me er al het lazarus op gezocht, maar maak weinig vordering. Kan je eventueel nog een tip geven dan? Heeft er eigenlijk nog iemand naar gezocht? Posten die handel !

#4

zijtjeszotjes

    zijtjeszotjes


  • >100 berichten
  • 171 berichten
  • Ervaren gebruiker

Geplaatst op 23 december 2005 - 15:42

dit heet de stelling van Knuth,
ik kreeg van iemand een bewijs voor elk natuurlijk getal groter dan 1.
ggd(ab-1,ac-1)=aggd(b,c)-1
maar ik weet nog niet of het bewijs echt klopt.. ik moet het nog eens lezen..

i think that my last method is not useful, and that we can show gcd(1+A+...+a^(x-1),1+A+...+A^(y-1)) = 1 from ggd(a^b-1,a^c-1) = a^ggd(b,c)-1, not the opposite.

One method very nice that was proposed to me :
we suppose c>b, the c=q_1*b+r_1 , b=q_2*r_1 + r_2, r_1=q_3*r_2 + r_3,..., r_(n-1) =q_(n+1)*r_n
we know that ggd(b,c) =ggd(b,r_1)=ggd(r_1,r_2) = ...=ggd(r_n,0) = r_n

in other hand, we have a^c-1 = a^(b*q_1+r_1)-1 = a^(b*q_1)*a^r_1 - 1
=a^(b*q_1)*a^r_1 - 1 +a^r_1 - a^r_1
= a^r_1 * (a^(b*q_1)-1 ) + (a^r_1 - 1)
=(a^b-1)((a^b)^(q_1-1)+...+(a^r_1)(a^r_1-1)

a^r_1- 1 < a^b-1 , so a^r_1 - 1 is the rest of the eucl. div. of (a^c-1) / (a^b-1)

then : ggd(a^b-1,a^c-1) = ggd(a^b-1,a^r_1-1)

we do the same thing with b instead of c, and r_1 instead of b, and so on, we find :

ggd(a^b-1,a^c-1) = ggd(a^b-1,a^r_1-1)
= ggd(a^r_1-1, a^r_2)
= ...
= ggd(a^r_n-1,a^0-1)
= a^r_n-1

r_n = ggd(b,c)

and we have the solution for every a .

#5

*_gast_PeterPan_*

  • Gast

Geplaatst op 23 december 2005 - 18:51

Geachte mijnheer Knuth, want vindt u van dit bewijs:

tip: schrijf de getallen eens binair

Hiermee kun je eenvoudig aantonen dat
2n.N-1 deelbaar is door 2n-1 voor elke n en N.

Daarmee is het bewijs nog niet gedaan.

Daar ggd(m,n) zowel deler is van m als van n geldt dus dat 2ggd(m,n)-1 deler is van zowel
2m-1 als 2n-1.
We zijn klaar als we kunnen aantonen dat het ook de grootst mogelijke deler is,
m.a.w. als X een deler is van 2m-1 en van 2n-1, dan is X :roll: 2ggd(m,n)-1.
Dat volgt onmiddellijk uit de formule die ik nu afleid:

Zoals bekend is ggd(m,n) = p.m - q.n voor zekere p en q.
(2p.m-1)(2q.n+1) - (2q.n-1)(2p.m+1) =
2p.m+q.n - 2q.n + 2p.m - 2p/m+q.n - 2q.n + 2p.m =
2(- 2q.n + 2p.m) =
2q.n+1(2p.m-q.n-1)

ofwel (2p.m-1)(2q.n+1) - (2q.n-1)(2p.m+1) = 2q.n+1(2ggd(m,n)-1)

#6

Nabuko Donosor

    Nabuko Donosor


  • >25 berichten
  • 94 berichten
  • Ervaren gebruiker

Geplaatst op 26 december 2005 - 14:51

Ik had dit bewijs
2^a-1 = 2^(a-1) + ... + 2 + 1
2^b-1 = 2^(b-1) + ... + 2 + 1
Pas nu het Euclidisch algoritme toe op die sommen. Zo zoeken we ggd(2^a-1,2^b-1). Stel a>b.
2^(a-1) + ... + 1 = 2^(a-b)[2^(b-1)+ ... +1] + 2^(a-b-1) + ... + 1
2^(b-1) + ... + 1 = 2^(2b-a)[2^(a-b-1) + ... + 1] + 2^(2b-a-1) + ... + 1
...
We zien wel dat 2^(a-b-1) + ... + 1 = 2^(a-b) - 1 en 2^(2b-a-1) + ... + 1=2^(2b-a)-1 enzoverder. De macht die bij 2 staat in het rechterlid is een algoritme om de x en y te zoeken in de Stelling van Bézout. Daaruit kunnen we het te bewijzen afleiden.

Het is nog wat vaag, maar ik denk dat het wel klopt.

#7

*_gast_PeterPan_*

  • Gast

Geplaatst op 30 april 2006 - 08:58

Aan te tonen: ggd(2a-1,2b-1) = 2ggd(a,b)-1.

Neem aan dat a > b is.
a = c.b + r met 0 [wortel] r < b.

Om deze regel aan mijn achterkleinzoon uit te leggen, leg ik rijtjes van a, b en r lucifers op tafel.
a = c.b + r betekent dat ik van de a lucifers er c groepjes van b lucifers af kan halen en er tot slot r overhoud.
Maar a lucifers lees ik binair als 2a-1.
Kortom
2a-1 = C.(2b-1) + 2r-1 voor een of andere C.
Hieruit blijkt dat je elke regel in het algoritme van Euclides voor de berekening van ggd(a,b) kunt vervangen door zijn binaire pendant.
Als ggd(a,b) = q, dan is dus
ggd(2a-1,2b-1) = 2q-1.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures