Hvordan løse lineære Kongruens

En lineær kongruens er en modulær matematisk funksjon som forbinder en variabel (x) til tre forskjellige heltall gjennom formel ax ≡ b (mod m). Her, a og b er hele tall og m er et ikke-null heltall. Løse en lineær kongruens krever en forståelse av noen vanskelige matematiske begreper. Gjennom noen få enkle trinn, kan disse problemene mestres.

Bruksanvisning

1 Beregn største felles divisor (g) mellom heltall a og m. Hvis heltall b ikke kan deles av denne største felles divisor, deretter x i denne lineære congruence har ingen løsning. For eksempel, i tilfellet 6x ≡ 2 (mod 3), så den største felles divisor er 3. Det er imidlertid to ikke er delelig med 3 uten en rest, eksisterer derfor ingen løsninger for denne lineære kongruens problem.

2 Beregne antall av løsninger, og det området av mulige løsningsverdier. Den største felles divisor bestemmer antallet heltallsløsninger for x fra rekken (0, 1, 2, ... m-1). For eksempel, i tilfellet 3x ≡ 6 (mod 9), er den største felles divisor 3. Derfor eksisterer tre løsningene for denne lineære kongruens problem. Mulige løsninger er (0, 1, 2, 3, 4, 5, 6, 7, 8).

3 Løs g = r

a + s m med utvidet Euklids algoritme, der r og s er flere heltall. I eksemplet, 3 = r + 3 r 9 kan gi r = -2, s = 1.

4 Finn en løsning ved å sette likhetstegn x til (r

b / g). Dette og alle løsninger er kongruente med g (mod (m / g)). Fortsetter eksempel, x = (-2 6/3) = -4, som er sammenfallende med 2 (mod 3).

5 Beregn løsningene for x. I eksemplet løsningene for x er (2, 5, 8).

Hint

• Løse en lineær kongruens forutsetter enten a og b er begge enten null eller ikke-null-verdier. Dersom en av heltall er en null, mens den andre er en annen verdi enn null, så er X ikke har noen løsning.