Perkongruenan Linear

Teorema 5.10

Jika (a, m) + b maka perkongruenan linear ax ≡ b (mod m) tidak memiliki solusi

Buktikan :

 misal : ax ≡ b (mod m) anggaplah mempunyai solusi r

       maka, ar ≡ b (mod m)

 bentuk ax ≡ b (mod m) diubah dalam bentuk pembagian menjadi ar-b=km yang artinya ar-b habis dibagi m untuk k bilangan bulat

bentuk ax ≡ b (mod m) kita asumsikan ada solusi berarti,

(a,m) │a , (a,m) km kembali lagi ke bentuk ax ≡ b (mod m) 

1. fpb a dan m habis membagi a,ada di bentuk sebelah kiri

2. fpb a dan m habis membagi km,ada dibentuk sebelah kanan

jika a dan m habis membagi a dan km,berarti fpb a dan m juga habis membagi b,

sehingga kesimpulannya (a,m) │b 

jadi, jika  ax ≡ b (mod m) ada solusi maka (a,m) │b 

                      kita gunakan kontraposisi

        jika (a, m) + b maka ax ≡ b (mod m) tidak memiliki solusi

Terbukti bahwa (a, m) + b tidak memiliki solusi