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