Pagina 1 van 1
Relatief priem
Geplaatst: 02 mei 2011, 00:36
door vwpolo02
Zij m en n natuurlijke getallen die relatief priem zijn, en a en b gehele getallen:
Bewijs dat:
1°als:
a=b (mod m) en a=b (mod n)
dan:
a=b (mod m.n)
2°Geldt dit ook als ggd(m,n) > 1?
1°vb: m=3, n=4
ggd(m,n) = 1 (dus relatief priem)
50 = 2 (mod 3) en 50 = 2 (mod 4)
=>50 = 2 (mod 3.4), dus geldig
2°vb: m=4, n=8
ggd(m,n) > 1 (dus niet relatief priem)
50 = 2 (mod 4) en 50 = 2 (mod 8 )
=>50 = 18 (mod 4.8 ) , dus niet geldig
m | (a-b)
n | (a-b)
=> m*n | (a-b)(a-b)
Hoe kan ik nu aantonen dat m*n|(a-b) en enkel wanneer m en n relatief priem zijn?
Re: Relatief priem
Geplaatst: 02 mei 2011, 12:23
door vwpolo02
Niemand die mij enige hint kan geven?
Re: Relatief priem
Geplaatst: 02 mei 2011, 13:11
door Sjoerd Job
Wat je eigenlijk zou moeten bewijzen is: Als
en
en
dan
. (en dan dit toepassen op
.). Ik ken uit mijn hoofd niet een bewijs hiervoor, maar weet wel dat het waar is. Welke voorkennis heb je?
Re: Relatief priem
Geplaatst: 02 mei 2011, 15:01
door vwpolo02
Is vraag voor een cursus discrete wiskunde. Ik zal mij hier al mee proberen te behelpen...
Re: Relatief priem
Geplaatst: 02 mei 2011, 16:59
door Sjoerd Job
Gebruik bijvoorbeeld
en
, dus
. Zie dit te gebruiken om bij
te komen.
Re: Relatief priem
Geplaatst: 02 mei 2011, 22:07
door vwpolo02
Geraak er maar niet aan uit... Het feit dat elk getal een unieke priemontbinding heeft lijkt me hier wel van belang...
Re: Relatief priem
Geplaatst: 02 mei 2011, 22:49
door Huibert
Kun je niet gebruiken dat als ggd(m,n)=1, de priemontbinding van m en n geen gelijke priemgetallen bevat. Omdat m|x en n|x zijn de priemontbindingen van m en n wel beide een gedeelte van de priemontbinding van x en dus die van mn ook en dus is mn|x.
Het is wat krom opgeschreven, maar ik heb het idee dat het wel klopt.
Re: Relatief priem
Geplaatst: 02 mei 2011, 23:45
door vwpolo02
Maar hoe toon je aan dat het niet zo is wanneer ze niet relatief priem zijn zoals in het 2e voorbeeld? Als je 2 getallen vermenigvuldigt die relatief priem zijn heb je hun kgv. In dit geval is dat dus a (+ b als rest)
Re: Relatief priem
Geplaatst: 03 mei 2011, 05:10
door Sjoerd Job
vwpolo02 schreef:Maar hoe toon je aan dat het niet zo is wanneer ze niet relatief priem zijn zoals in het 2e voorbeeld? Als je 2 getallen vermenigvuldigt die relatief priem zijn heb je hun kgv. In dit geval is dat dus a (+ b als rest)
Als ze niet relatief priem zijn, kan het nog wel waar zijn. Bijvoorbeeld:
,
.
Dat het niet
altijd waar hoeft te zijn kan met een tegenvoorbeeld. (die heb je al gegeven).
Wat je kan gebruiken is dat omdat
, en
, dat
. Hier staat dus ook dat
. Je weet dat
, dus
(vul in).