Algebra

Analyse

Bewijzen

De grafische rekenmachine

Discrete wiskunde

Fundamenten

Meetkunde

Oppervlakte en inhoud

Rekenen

Schoolwiskunde

Statistiek en kansrekenen

Telproblemen

Toegepaste wiskunde

Van alles en nog wat


\require{AMSmath}

Congruentie oplossen

Beste wisfaq,

Ik zit met het volgende probleem: ik moet de oplossingen vinden voor

x5+x3+3 = 0 (mod 125)

Ik weet wel een methode (ik beschrijf hieronder wat ik heb gedaan), maar vroeg me af of er een elegantere methode bestaat. De hieronder beschreven methode is namelijk (voor kleine moduli) maar iets sneller dan alle oplossing proberen.

Mijn oplossing: merk op dat 125 = 53. Dus als x5+x3+3 = 0 (mod 125)
een oplossing heeft, dan moet x5+x3+3 = 0 (mod 5) ook een oplossing hebben (aangezien x5+x3+3 = 0 wanneer 125 x5+x3+3 deelt, en 5 deelt 125, dus in dit geval deelt 5 ook x5+x3+3).

De "residue classes" modulo 5 zijn 0,1,2,3 en 4. Als we nu een representative voor elk van deze residue classes substitueren in de congruentie dan zien we dat wanneer x5+x3+3 = 0 (mod 5) Þ x=1 (mod 5).

Als hierboven: als x5+x3+3 = 0 (mod 125) een oplossing heeft dan moet x5+x3+3 = 0 (mod 25) ook een oplossing hebben. De residue classes modulo 25 zijn 0,1,2,3, ..., 23,24. Aangezien we net hebben aangetoond dat voor elke oplossing x5+x3+3 = 0 (mod 125) we moeten hebben x=1 (mod 5), hoeven we alleen te kijken of x5+x3+3 = 0 (mod 25) voor x E 1,6,11,16 en 21 (de E hier staar voor element, en de getallen zijn residue classses). Een representative substitueren laat zien dat x5+x3+3 = 0 (mod 25) Þ x = 16 (mod 25)

Beschouw nu x5+x3+3 = 0 (mod 125). De residue classes zijn 0,1,2,3, ..., 123,124. We weten al dat x = 1 (mod 5) en x = 16 (mod 25). Dus we testen x E 16, 41, 66, 91 en 116. Dit laat zien dat de enige oplossing voor x5+x3+3 = 0 (mod 125) is x=41+125k waarbij k een geheel getal is.

Herman
Student universiteit - dinsdag 5 mei 2009

Antwoord

Er is niets mis met je oplossing en het is iets wat ik zelf ook geprobeerd zou hebben. Een alternatief zou kunnen zijn dat je -3=122 ontbindt in factoren en met behulp daarvan x probeert te vinden met x3(x2+1)=122; het vervelende is dat zo'n ontbinding niet uniek is en dat zorgt weer voor andere complicaties.

kphart
dinsdag 5 mei 2009

©2001-2024 WisFaq