de gcd (greatest common divisor)

Badshaah

Hallo,

Ik heb hulp nodig bij een opdracht, die gaat als volgt:

Vind de gcd van (a^(2m)+1,a^(2n)+1) in termen van a en dan staat er als hint bij:

laat zien dat a^(2n)+1 | a^(2m)-1 (| betekent deelt) als m>n.

Ik heb er lang over nagedacht en ik heb geen idee wat ik moet doen, ook snap ik de hint niet.

Heel erg bedankt alvast.

Typhoner

zijn a, m en n gehele getallen?

Voor de hint: als a even dan ..., als a oneven dan ...

Drieske

Laten we eerst eens de hint bekijken. Bedoel je btw

\(a^{2m} + 1\)

of

\(a^{2^m} + 1\)

? Ik ga uit van het eerste, wegens jouw schrijfwijze, maar verwacht eigenlijk het tweede

. Er zijn veel manieren om dit te bewijzen. Maar hoe ik het zou doen: noem

\(T_i = a^{2i} + 1\)

en bekijk

\(T_m - 2 = (a^{2m} + 1) - 2\)

eens.

Safe

Kies bv eens n=1 en m=2,kan je ontbinden ...

Badshaah

ja, alle getallen zijn geheel.

als a even is dan zijn a^(2m)+1 en a^(2n)+1 oneven getallen. als a oneven dan zijn ze even getallen.

@Drieske: ik bedoel idd de eerste, maar ik snapte de link niet tussen de hint en de opgave

Drieske

Wel, als je graag eerst de link ziet: eens je weet dat

\(a^{2^m} - 1 = (a^{2^m} + 1) - 2\)

deelbaar is door

\(a^{2^n} + 1\)

, betekent dit dat er een C bestaat zodat

\((a^{2^m} + 1)-2 = C(a^{2^n} + 1)\)

of dus

\(a^{2^m}+1 = C(a^{2^n} + 1) + 2\)

. Dus elke gemene deler, moet ook een deler van 2 zijn. Akkoord? Zie je het nu?

Badshaah

@safe: als ik a^4+1 en a^2+1 wil ontbinden, moet ik i gebruiken ( (a^2-i)(a^2+i)=a^4+1 ) of bedoel je iets anders?

Badshaah

oke, nu zie ik de link tussen de hint en de opgave, dus ik moet eigenlijk de ggd vinden van (C(a^(2n)+1)+2,a^(2n)+1) en de ggd moet tegelijk 2 delen, klopt dit?

Drieske

Mja, een getal dat 2 moet delen, heeft toch niet meer zoveel opties? Dat is toch 1 of 2? Dus is de gcd die je zoekt...? En die C is overbodig, want...?

Badshaah

dus de gcd is 2 of 1, maar in de opgave staat dat je de gcd moet uitdrukken in termen van a, dus maken ze daar een fout?

Drieske

Neen, want of het 1 is of 2, hangt af van het even of oneven zijn van ...?

Badshaah

o ja natuurlijk! als a oneven is dan gcd=2 en als a even is dan gcd=1. dan nog een vraagje, waarom was die C overbodig?

Drieske

Probeer dat eens zelf te beredeneren... Bedenk hierbij dat het enkel om het even of oneven karakter gaat ondertussen. Wat ook mogelijk is, is om nu eerst de hint eens te proberen. Misschien krijg je daar nog wat meer info uit wat het je nog makkelijker gaat maken.

kee

Vraagje: Het moet dus zijn

\(a^{2^m}+1\)

en

\(a^{2^n}+1\)

? Anders zijn er veel tegenvoorbeelden voor de hint, bijvoorbeeld 2^2+1=5 is geen deler van 2^6-1=63.

Drieske

Ja, ik had ze blijkbaar in mijn bericht in het begin omgekeerd staan. Maar ik dacht dus ook dat die vorm bedoelt werd, en heb daarmee ook mijn eerdere antwoord gemaakt.. Over een tegenvoorbeeld had ik niet gedacht, maar bij deze

. Dat zijn ook getallen die bij getaltheorie vaak bestudeerd worden. Zeker voor a=2.

Edit: na wat proberen, geraak je er ook niet echt uit met de "foute" schrijfwijze om veel zinnigs te zeggen. Mijn aanpak uit post#3 lijkt ook alleen maar steek te houden op jouw schrijfwijze, kee.

Wetenschapsforum

Laatste berichten

Nieuwsberichten

de gcd (greatest common divisor)

de gcd (greatest common divisor)

Re: de gcd (greatest common divisor)

Re: de gcd (greatest common divisor)

Re: de gcd (greatest common divisor)

Re: de gcd (greatest common divisor)

Re: de gcd (greatest common divisor)

Re: de gcd (greatest common divisor)

Re: de gcd (greatest common divisor)

Re: de gcd (greatest common divisor)

Re: de gcd (greatest common divisor)

Re: de gcd (greatest common divisor)

Re: de gcd (greatest common divisor)

Re: de gcd (greatest common divisor)

Re: de gcd (greatest common divisor)

Re: de gcd (greatest common divisor)