Hulp nodig bij ggd en modulo

[Yoran1991]

Hallo allemaal,

ik heb hulp nodig met een opgave die ik moet maken voor groepentheorie. Ik heb de opgave vrijwel helemaal af, maar er mist slechts 1 bewijs. Ik moet het volgende bewijzen:

Als ggd(a,24) = 1, dan a^2 = 1 mod 24 .

Wat ik tot nu toe heb is dit (ik weet ook niet of het in de goede richting is):

1. a en 24 zijn relatief priem, dus ggd(a,24) =1. Dit is equivalent met:

\(\exists t,s \in \mathbb{Z}\,\,\,\,\,\,at+24s=1\)

2. Dus

\(at-1=24r\)

met r=-s.

3. Dus at = 1 mod 24

Verder kom ik niet echt... is er iemand die een hint kan geven?

[Safe]

Je weet toch welke getallen a relatief priem met 24 zijn?

Bepaal dan a².

[Yoran1991]

Nou, het probleem is dus dat a een willekeurig getal is relatief priem met 24..

ik zie wel dat 5^2 = 1 mod 24, 7^2 = 1 mod 24 etc... maar ik wil graag het bewijs leveren voor willekeurige a relatief priem met 24

[Safe]

Nou, het probleem is dus dat a een willekeurig getal is relatief priem met 24..

ik zie wel dat 5^2 = 1 mod 24, 7^2 = 1 mod 24 etc... maar ik wil graag het bewijs leveren voor willekeurige a relatief priem met 24

Dat begrijp ik en dat komt nog, maar probeer het eerst met bv 5, want ...

[Yoran1991]

Ik begrijp niet precies wat je bedoelt

Bedoel je dat ik a=5 moet stellen in mijn 'bewijs'?

Of bedoel je dat ik moet checken dat 5^2 = 1 mod 24?

[Safe]

Precies! En de andere mogelijkheden ...

[Yoran1991]

Ik weet dat de getallen 5,7,11,13,17,19,23 relatief priem met 24 zijn, en dat ze allemaal 1 mod 24 zijn als ik ze kwadrateer. Mijn punt is juist dat ik dit voor een willekeurig getal wil laten zien en het niet voor elk getal expliciet uit wil rekenen.

[Drieske]

Ik veronderstel dat je weet:

\(a = b \mod m \Leftrightarrow m | (b - a).\)

Kun je daar niets mee doen hier?

[Yoran1991]

Ik veronderstel dat je weet:

\(a = b \mod m \Leftrightarrow m | (b - a).\)

Kun je daar niets mee doen hier?

Ik heb die equivalentie bij stap 2. naar 3. gebruikt in mijn 'bewijs'. Ik weet niet wat ik er verder mee zou kunnen doen. Ik probeer nu met een getal aan beiden zijden te vermenigvuldigen, maar dat lijkt ook niet echt ergens op uit te komen

[Drieske]

Maar je moet het niet op 'jouw' a gebruiken. Je weet dus dat a relatief priem is met 24. Is a² dat dan ook?

[Yoran1991]

Maar je moet het niet op 'jouw' a gebruiken. Je weet dus dat a relatief priem is met 24. Is a² dat dan ook?

Hmm, ik denk het wel, maar ik moet het nog wel even bewijzen

Edit:

Als ik at+24s = 1 aan beiden zijden kwadrateer, krijg ik

\(a^2p+24r=1\)

voor p en r in Z.

Dus die zijn inderdaad relatief priem

[Drieske]

De makkelijkste manier om dit in te zien is priemfactorontbinding van je getal a (noem die factoren bijv p₁, ..., p_k). Dan kun je alvast opmerken dat, omdat 24 = 2.3.4, al deze factoren groter moeten zijn dan 5 (of gelijk aan). Helpt dit?

[Yoran1991]

De makkelijkste manier om dit in te zien is priemfactorontbinding van je getal a (noem die factoren bijv p₁, ..., p_k). Dan kun je alvast opmerken dat, omdat 24 = 2.3.4, al deze factoren groter moeten zijn dan 5 (of gelijk aan). Helpt dit?

Ik heb nu at+24s = 1 aan beiden zijden gekwadrateerd, dan krijg ik dat

\(a^2t^2 + 2\cdot24\cdot a\,t\,s+24^2s^2=1\)

Al die producten van getallen t^2, 2ats en 24s^2 zitten weer in Z dus zijn a en 24 relatief priem. Daaruit kan ik weer aantonen dat a^2 = 1 mod 24 (op dezelfde manier zoals ik helemaal bovenaan heb gedaan)

Klopt het dan?

[Drieske]

Kun je het eens preciezer uitschrijven? Je weet dat a² relatief priem is met 24. Om evidente redenen zoals hierboven geschetst. We willen nu dus bewijzen dat

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

. Dit was equivalent met

\(24 | (1 - a^2).\)

Uit het relatief priem zijn, weet je dat ggd(a², 24) = 1.

[Yoran1991]

Kun je het eens preciezer uitschrijven? Je weet dat a² relatief priem is met 24. Om evidente redenen zoals hierboven geschetst. We willen nu dus bewijzen dat

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

. Dit was equivalent met

\(24 | (1 - a^2).\)

Uit het relatief priem zijn, weet je dat ggd(a², 24) = 1.

Okee, ik zal het volledig uitschrijven.

We willen bewijzen dat :

\(gcd(a,24)=1 \Rightarrow a^2 = 1 mod24\)

We nemen dus aan dat gcd(a,24)=1. We weten dan dat

\(\exists t,s \in \mathbb{Z}\)

zodat

\(at+24s=1\)

Deze vergelijking kwadrateren we nu aan beide zijden:

\(a^2t^2+2\cdot24\cdot ats + 24^2s^2=1\)

. De producten

\(t^2, 2ats\)

en

\(24s^2\)

zijn allen elementen in

\(\mathbb{Z}\)

.

Dus we kunnen schrijven

\(\exists p,q \in \mathbb{Z}\,\, a^2p+24q=1\)

. Dus a en 24 zijn relatief priem. Verder geldt:

\(a^2p-1=24\cdot (-q)\)

. Dit is equivalent aan

\(a^2=1 mod24\)

QED