Hulp nodig bij ggd en modulo

Moderators: dirkwb, Xilvo

Forumregels
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
Reageer

Bericht 01-10-'11, 18:03

Yoran1991

Berichten: 28

Hulp nodig bij ggd en modulo

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?
Omhoog

Bericht 01-10-'11, 19:29

Safe

Gebruikersavatar
Pluimdrager
Berichten: 10.058

Re: Hulp nodig bij ggd en modulo

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

Bepaal dan a².
Omhoog

Bericht 01-10-'11, 19:38

Yoran1991

Berichten: 28

Re: Hulp nodig bij ggd en modulo

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
Omhoog

Bericht 01-10-'11, 20:11

Safe

Gebruikersavatar
Pluimdrager
Berichten: 10.058

Re: Hulp nodig bij ggd en modulo

Yoran1991 schreef: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 ...
Omhoog

Bericht 01-10-'11, 22:46

Yoran1991

Berichten: 28

Re: Hulp nodig bij ggd en modulo

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?
Omhoog

Bericht 02-10-'11, 09:10

Safe

Gebruikersavatar
Pluimdrager
Berichten: 10.058

Re: Hulp nodig bij ggd en modulo

Precies! En de andere mogelijkheden ...
Omhoog

Bericht 02-10-'11, 11:16

Yoran1991

Berichten: 28

Re: Hulp nodig bij ggd en modulo

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.
Omhoog

Bericht 02-10-'11, 11:37

Drieske

Gebruikersavatar
Berichten: 10.179

Re: Hulp nodig bij ggd en modulo

Ik veronderstel dat je weet:
\(a = b \mod m \Leftrightarrow m | (b - a).\)
Kun je daar niets mee doen hier?
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.
Omhoog

Bericht 02-10-'11, 12:09

Yoran1991

Berichten: 28

Re: Hulp nodig bij ggd en modulo

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 ;)
Omhoog

Bericht 02-10-'11, 12:12

Drieske

Gebruikersavatar
Berichten: 10.179

Re: Hulp nodig bij ggd en modulo

Maar je moet het niet op 'jouw' a gebruiken. Je weet dus dat a relatief priem is met 24. Is a² dat dan ook?
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.
Omhoog

Bericht 02-10-'11, 12:27

Yoran1991

Berichten: 28

Re: Hulp nodig bij ggd en modulo

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
Omhoog

Bericht 02-10-'11, 12:31

Drieske

Gebruikersavatar
Berichten: 10.179

Re: Hulp nodig bij ggd en modulo

De makkelijkste manier om dit in te zien is priemfactorontbinding van je getal a (noem die factoren bijv p1, ..., pk). Dan kun je alvast opmerken dat, omdat 24 = 2.3.4, al deze factoren groter moeten zijn dan 5 (of gelijk aan). Helpt dit?
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.
Omhoog

Bericht 02-10-'11, 12:38

Yoran1991

Berichten: 28

Re: Hulp nodig bij ggd en modulo

De makkelijkste manier om dit in te zien is priemfactorontbinding van je getal a (noem die factoren bijv p1, ..., pk). 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?
Omhoog

Bericht 02-10-'11, 12:44

Drieske

Gebruikersavatar
Berichten: 10.179

Re: Hulp nodig bij ggd en modulo

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.
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.
Omhoog

Bericht 02-10-'11, 12:58

Yoran1991

Berichten: 28

Re: Hulp nodig bij ggd en modulo

Drieske schreef: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
Omhoog
Reageer

Terug naar “Wiskunde”