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.