Hulp nodig bij ggd en modulo

[Drieske]

Het relatief priem zijn a² en 24 bewijs je moeilijker dan nodig hoor. Heb je mijn argument hierboven gezien?

En je laatste zin "dit is equivalent met"... Waarom?

[Yoran1991]

Het relatief priem zijn a² en 24 bewijs je moeilijker dan nodig hoor. Heb je mijn argument hierboven gezien?

En je laatste zin "dit is equivalent met"... Waarom?

Oh wacht, die equivalentie geldt niet, er moet nog een p bij:

\(a^2p=1 mod 24\)

. Dan heb ik het dus nog niet bewezen...

En ik heb het argument nu gezien, maar ik volg het niet helemaal...

[Drieske]

En ik heb het argument nu gezien, maar ik volg het niet helemaal...

Wel, je hebt dus de ontbinding in priemfactoren. Ben je hiermee bekend?

[Yoran1991]

Wel, je hebt dus de ontbinding in priemfactoren. Ben je hiermee bekend?

Opzich wel ja

[Drieske]

Okee . Je hebt dus

\(a = p_1^{a_1} \cdots p_n^{a_n}\)

met de p's priemgetallen en de a's natuurlijke getallen. Dan heb je ook dat

\(a^2 = p_1^{2a_1} \cdots p_n^{2a_n}.\)

Dus de priemfactoren veranderen niet. Zie je nu waarom a² relatief priem moet zijn als a dat is?

[Yoran1991]

Okee . Je hebt dus

\(a = p_1^{a_1} \cdots p_n^{a_n}\)

met de p's priemgetallen en de a's natuurlijke getallen. Dan heb je ook dat

\(a^2 = p_1^{2a_1} \cdots p_n^{2a_n}.\)

Dus de priemfactoren veranderen niet. Zie je nu waarom a² relatief priem moet zijn als a dat is?

Ja, dat zie ik

Dus dat weet je dat ggd(a^2,24) = 1... maar hoe bewijs je dan daaruit dat a^2 = 1 mod 24?

[Drieske]

Ben je het ermee eens dat je moet bewijzen dat (a²-1) deelbaar is door 24?

[Yoran1991]

Ben je het ermee eens dat je moet bewijzen dat (a²-1) deelbaar is door 24?

Ja, dat is equivalent aan dat a^2 = 1 mod 24...

[Drieske]

Schrijf nu eens (a²-1) = (a-1)(a+1). Kun je hier iets mee?

[Yoran1991]

Schrijf nu eens (a²-1) = (a-1)(a+1). Kun je hier iets mee?

niet echt.. alleen dat als ik nu wil bewijzen dat 24|(a^2-1) , dan moet 24|(a-1) of 24|(a+1)

[Drieske]

Ik probeer het allemaal even zo inzichtelijk mogelijk te benaderen. Als je weet dat a noch door 2 noch door 3 noch door 4 deelbaar is. Wat kun je dan zeggen over (a-1) én (a+1)?

Ik zal je hierin alvast even op weg helpen. Daar a niet door 2 deelbaar is, is a oneven. Dus a-1 en a+1 zijn even. Dus deelbaar door 2. Bijgevolg is (a-1)(a+1) deelbaar door 4. Kun jij doorgaan?

[Yoran1991]

Ik probeer het allemaal even zo inzichtelijk mogelijk te benaderen. Als je weet dat a noch door 2 noch door 3 noch door 4 deelbaar is. Wat kun je dan zeggen over (a-1) én (a+1)?

Ik zal je hierin alvast even op weg helpen. Daar a niet door 2 deelbaar is, is a oneven. Dus a-1 en a+1 zijn even. Dus deelbaar door 2. Bijgevolg is (a-1)(a+1) deelbaar door 4. Kun jij doorgaan?

Aha, dus we stellen nu dat a niet deelbaar is door 3. Dan:

a = 3q+1 of a = 3q+2 voor een q in Z. En dus (a-1) = 3q of 3q+1

en (a+1) = 3q+1 of 3r met r ook weer in Z. Als je die vermenigvuldigd (dus beiden gevallen uitwerkt), krijg je dat a^2 - 1 deelbaar is door 3.

dus a^2 -1 is deelbaar door zowel 2,3 als 4. Kan je dan zeggen dat hij ook deelbaar is door 24?

[Drieske]

Als je dat hebt, kun je dat uiteraard. Immers is 24=2*3*4. Maar momenteel hebben we nog maar 3 en 4 hè...

[Yoran1991]

Als je dat hebt, kun je dat uiteraard. Immers is 24=2*3*4. Maar momenteel hebben we nog maar 3 en 4 hè...

Maar als a^2 - 1 deelbaar is door 4, is het toch ook deelbaar door 2

[Drieske]

Ja. Maar het moet deelbaar zijn door 2 én 4 tegelijk hè... En dat heb je nog niet.