Hoe op te lossen Linear Congruence

Een lineaire congruentie is een modulair wiskundige functie betreffende variabele ( x ) drie verschillende gehele getallen door de formule ax ≡ b ( mod m ) . Here , a en b gehele getallen zijn en m een ​​non - zero integer . Het oplossen van een lineaire congruentie vereist een begrip van een aantal lastige wiskundige concepten . Via een paar eenvoudige stappen , kunnen deze problemen worden beheerst . Instructies
1

Bereken de grootste gemene deler ( g ) tussen het gehele getal a en m . Als de integer b niet worden gedeeld door de grootste gemene deler , dan x in deze lineaire congruentie geen oplossing . Bijvoorbeeld , in het geval 6x ≡ 2 ( mod 3 ) , dan is de grootste gemene deler 3 echter 2 niet deelbaar is door 3 zonder rest , dus er geen oplossing voor dit probleem lineaire congruentie . Kopen van 2

Bereken het aantal oplossingen en het bereik van de mogelijke oplossing waarden . De grootste gemene deler bepaalt het aantal gehele oplossingen voor x van de reeks ( 0 , 1 , 2 , ... m -1 ) . Bijvoorbeeld , in het geval 3x ≡ 6 ( mod 9) de grootste gemene deler 3 dus bestaan ​​drie oplossingen voor dit probleem lineaire congruentie . Mogelijke oplossingen zijn ( 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ) .
3

Los g = r * a + s * m met behulp van de uitgebreide Euclidische algoritme , waarbij r en s extra integers . In het voorbeeld 3 = r * 3 + s * 9 kan opleveren r = -2 , s = 1
4

Zoek een oplossing neerkomt x tot ( r * b /g ) . Deze en alle oplossingen zijn congruent met g ( mod ( m /g ) ) . Voortzetting van het voorbeeld , x = ( -2 * 6/3 ) = -4 , die congruent is met 2 ( mod 3 ) .
5

Bereken de oplossingen voor x . In het voorbeeld zijn de oplossingen voor x ( 2 , 5 , 8 ) .