25127

Przykład

1.    Rozwiązać równanie 13x + 7y =1

x₀ = -l, yo=2 x = -1 +7t, y = 2- 13t

2.    Rozwiązać równanie 1000x+73y=l

x_o = -10, y₀= 137 x= -10+73t, y=137-1000t

Kongruencje liniowe

Kongruencje liniowe

ax = b (mod m)

ma rozwiązanie wtedy i tylko wtedy gdy równanie diafontyczne: ax + my =b

ma rozwiązanie w liczbach całkowitych.

Twierdzenie

Kongruencje liniowe ax = b (mod m), gdzie a,b,m e Z, ma rozwiązanie w liczbach całkowitych wtedy i tylko wtedy gdy d Ib, gdzie d = NWD(a,m).

1) Jeśli NWD(a,m)=l, to istnieją liczby s,t takie, że

as+mt=l => as s 1 (mod m)

Liczbę s nazywamy odwrotnej do liczby a. Wtedy

asb = b (mod m), skąd

x = sb + mt - rozwiązanie kongruencji.

3) Jeśli NWD(a,m) =d oraz dlb, to a=aid, b=bjd, m=ni|d, i mamy