WisFaq!

Congruentie oplossen

Beste wisfaq,

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

x⁵+x³+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 = 5³. Dus als x⁵+x³+3 = 0 (mod 125)
een oplossing heeft, dan moet x⁵+x³+3 = 0 (mod 5) ook een oplossing hebben (aangezien x⁵+x³+3 = 0 wanneer 125 x⁵+x³+3 deelt, en 5 deelt 125, dus in dit geval deelt 5 ook x⁵+x³+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 x⁵+x³+3 = 0 (mod 5) Þ x=1 (mod 5).

Als hierboven: als x⁵+x³+3 = 0 (mod 125) een oplossing heeft dan moet x⁵+x³+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 x⁵+x³+3 = 0 (mod 125) we moeten hebben x=1 (mod 5), hoeven we alleen te kijken of x⁵+x³+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 x⁵+x³+3 = 0 (mod 25) Þ x = 16 (mod 25)

Beschouw nu x⁵+x³+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 x⁵+x³+3 = 0 (mod 125) is x=41+125k waarbij k een geheel getal is.

Herman
5-5-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 x³(x²+1)=122; het vervelende is dat zo'n ontbinding niet uniek is en dat zorgt weer voor andere complicaties.

kphart
5-5-2009