BIGtheme.net http://bigtheme.net/ecommerce/opencart OpenCart Templates
Friday , July 28 2017
Home / Elementary Number Theory / Basic properties of congruence and their proved

# i) a ≡ b (mod n)

Proof: For any integer a, we have

0/n = 0

⟹ (a – a) / n = 0

⟹ a – a = 0.n

⟹ a ≡ a (mod n) (proved)

## ii) If a ≡ b (mod n) then b ≡ a(mod n)

Proof: Given that,

a ≡ b (mod n)

⟹ (a – b) / n ≡ k, say

⟹ (b – a) / n = –k

⟹ b – a = – nk

⟹ b ≡ a (mod n) (Proved)

### iii) If a ≡ b (mod n) and b ≡ c (mod n), then a ≡ c(mod n)

Proof: Given that,

a ≡ b (mod n)

⟹ (a – b) / n = k, say

⟹ a – b = nk —————- (1)

Again, b ≡ c (mod n)

⟹ (b – c) / n = t, say

⟹ b – c = nt ——————-(2)

Adding (1) and (2), we get

a – c = n(k + t)

∴ a ≡ c (mod n) (Proved)

### iv) If a ≡ b (mod n) and c ≡ d (mod n), then a ± c = b ± d (mod n)

Proof: Given that,

a ≡ b (mod n)

⟹ (a – b) / n = k , say

⟹ a – b = nk —————— (1)

Again, c ≡ d (mod n)

⟹ (c – d) / n = t, say

⟹ c – d = nt ——————(2)

Adding (1) and (2), we get

a – b + c – d = m ( k + t )

⟹ a + c ≡ b + d (mod n)

Subtracting (2) from (1), we get

a – b – c + d = m (k – t)

⟹ a – c ≡ b – d (mod n)

So, a ± c = b ± d (mod n) (Proved)

## v) If a ≡ b (mod n) then ac = bc (mod n)

Proof: Given that,

a ≡ b (mod n)

⟹ (a – b) / n = k, say

⟹ a – b = nk

⟹ c( a – b) = mkc [multiplying both side by c]

⟹ ac – bc = m (kc)

⟹ ac ≡ bc (mod n) (Proved)

### vi) If a ≡ b (mod n) and a ≡ c(mod n), then b ≡ c (mod n)

Proof: Given that,

a ≡ b (mod n)

⟹ (a – b) / n = k, say

⟹ a – b = nk —————— (1)

Again, a ≡ c(mod n)

⟹ (a – c) / n = t, say

⟹ a – c = nt ———————- (2)

Subtracting (1) from (2), we get

a – c – a + b = m (t – k)

⟹ b – c = m ( t – k )

⟹ b ≡ c (mod n) (Proved)

vii) If a ≡ b (mod n), then ak ≡ bk(mod m), for all k ≥ 1 but if ak ≡ bk (mod n) for k ≥ 2, then a ≡ b (mod n) may not be true.

Proof: Given that,

a ≡ b (mod n)

⟹ (a – b) / n = t, say

⟹ a – b = nt —————— (1)

Now, ak – bk = (a – b) (ak – 1+ …+ bk – 1 )

= mt (ak – 1+ …+ bk – 1 ) [by (1)]

∴ a ≡ b (mod n) (Proved)

## Application of Euclidian’s algorithm in Diophantine equation

Problem-1: Which of the following Diophantine equations cannot be solved –   a) 6x + ...