gcd(a, b) <= a - b

Mange finner bevis vanskelig. Her er rom for spørsmål vedrørende bevis, og for å dele dine bevis med andre. Vi tenker først og fremst videregående nivå, men det er ingen begrensninger her.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
Emilga
Riemann
Riemann
Innlegg: 1552
Registrert: 20/12-2006 19:21
Sted: NTNU

Holder dette?

La den største felles faktoren til [tex]a,b\in \mathrm{N}[/tex] og [tex]a>b[/tex] denoteres med [tex](a,\,b)[/tex].

Bevis at: [tex](a,\,b) \leq a-b[/tex]

La [tex]k = (a,\,b)[/tex]. Da har vi at [tex]a = pk[/tex] og [tex]b = qk[/tex] for to [tex]p,q\in\mathrm{N}[/tex]. Siden [tex]a>b[/tex] må [tex]p>q[/tex].

[tex]k \leq pk - qk = k(p-q)[/tex]

[tex]1 \leq p-q[/tex]

[tex]q+1\leq p[/tex], som jo må stemme.
Emilga
Riemann
Riemann
Innlegg: 1552
Registrert: 20/12-2006 19:21
Sted: NTNU

Et mer elegant bevis:

La [tex]g = (a,\,b)[/tex]. Per definisjon vil [tex]g|a[/tex] og [tex]g|b[/tex], så [tex]a-b \equiv 0-0 \equiv 0 \pmod g[/tex].
Svar