Question No 03 | Exercise 4.2 | The Theory of Congruences | Elementary Number Theory
Question No 03 | Exercise 4.2 | Chapter No 4 | The Theory of Congruences | Elementary Number Theory
Question No 03 | Exercise 4.2 | The Theory of Congruences Elementary Number Theory
Basic Properties of Congruence | Chapter No 4 | The Theory of Congruences | Elementary Number Theory
Book Name : Elementary Number Theory
By : David M. Burton
Chapter Number : 04
Chapter Name : The Theory of Congruences
Lecture Number : 07
By (Name) : Awais Rasool
Exercise Number : 4.2
Problems Number: 4.2
Question Number : 03
Part Number : 00
Example Number : 00
Theorem Number: 4.2
Awais Rasool Shah
Topics Name :
4.1 Carl Friedrich Gauss
4.2 Basic Properties of Congruence.
4.3 Binary and Decimal Representations of integers
4.4 Linear Congruences and the Chinese Remainder Theorem.
..........................................................| |........................................................
📲 Facebook Profile Link:
https://www.facebook.com/awaisrasoolshah786/
📲 Instagram Profile Link:
https://www.instagram.com/awaisrasoolshah
📲 Linkedin Profile Link:
https://www.linkedin.com/in/
📲 WhatsApp contact:
+923160600073
..........................................................| Thanks |........................................................
Basic Properties of Congruence:
Definition:
Let 𝑛 be a fixed positive integer. Two integers 𝑎 and 𝑏 are said to be congruent modulo 𝑛, symbolized by
𝑎≡𝑏 (𝑚𝑜𝑑 𝑛)
If 𝑛 divides the difference 𝑎−𝑏; that is, provided that 𝑎−𝑏=𝑘𝑛 for some integer 𝑘.
Let 𝑛 is greater then 1 be fixed and 𝑎,𝑏,𝑐,𝑑 be arbitrary integers. Then the following properties hold:
𝑎≡𝑎 (𝑚𝑜𝑑 𝑛).
If 𝑎≡𝑏 (𝑚𝑜𝑑 𝑛), then 𝑏≡𝑎 (𝑚𝑜𝑑 𝑛).
If 𝑎≡𝑏 (𝑚𝑜𝑑 𝑛) and 𝑏≡𝑐 (𝑚𝑜𝑑 𝑛) then 𝑎≡𝑐 (𝑚𝑜𝑑 𝑛).
If 𝑎≡𝑏 (𝑚𝑜𝑑 𝑛) and 𝑐≡𝑑 (𝑚𝑜𝑑 𝑛) , then 𝑎+𝑐≡𝑏+𝑑 (𝑚𝑜𝑑 𝑛) and 𝑎𝑐≡𝑏𝑑 (𝑚𝑜𝑑 𝑛)
If 𝑎≡𝑏 (𝑚𝑜𝑑 𝑛) , then 𝑎+𝑐≡𝑏+𝑐 (𝑚𝑜𝑑 𝑛) and 𝑎𝑐≡𝑏𝑐 (𝑚𝑜𝑑 𝑛)
If 𝑎≡𝑏 (𝑚𝑜𝑑 𝑛), then 𝑎^𝑘≡𝑏^𝑘 (𝑚𝑜𝑑 𝑛) for any positive integer 𝑘.
Question No: 03
If 𝑎≡𝑏 (𝑚𝑜𝑑 𝑛), prove that gcd(𝑎,𝑛) = gcd(𝑏,𝑛).
If 𝑎≡𝑏 (𝑚𝑜𝑑 𝑛), prove that gcd(𝑎,𝑛) = gcd(𝑏,𝑛).
Sol:
If 𝑎≡𝑏 (𝑚𝑜𝑑 𝑛)
𝑎−𝑏≡𝑏−𝑏 (𝑚𝑜𝑑 𝑛)
𝑎−𝑏≡0 (𝑚𝑜𝑑 𝑛)
we can written as:
𝑛|𝑎−𝑏
𝑎−𝑏=𝑘𝑛 for some “𝑘∈𝑍”.
𝑎=𝑏+𝑘𝑛 (i)
Now Let 𝑑=gcd(𝑎, 𝑛) and 𝑔=gcd(𝑏, 𝑛).
If 𝒅=𝒈𝒄𝒅(𝒂, 𝒏)
𝑑|𝑎 and 𝑑|𝑛
we can written in the form:
𝑎=𝑑𝑠 and 𝑛=𝑑𝑟 (ii)
For some 𝑠 and 𝑟 belong to integer (Z) .
𝑎=𝑑𝑠 and 𝑛=𝑑𝑟 (ii)
For some 𝑠 and 𝑟 belong to integer (Z) .
put the values 𝑎=𝑑𝑠 and 𝑛=𝑑𝑟 in equation (i). 𝑎=𝑏+𝑘𝑛
𝑑𝑠=𝑏+𝑘𝑑𝑟
𝑏=𝑑𝑠−𝑘𝑑𝑟
𝑏=𝑑(𝑠−𝑘𝑟)
𝑑|𝑏 (iii)
So,
𝑑|𝑏 and 𝑑|𝑛
Then 𝑑|gcd(𝑏,𝑛)
If 𝑔=gcd(𝑏, 𝑛).
→ 𝑑|𝑔 (iv)
If 𝒈=𝒈𝒄𝒅(𝒃, 𝒏)
𝑔|𝑏 and 𝑔|𝑛
we can written in the form:
𝑏=𝑔𝑡 and 𝑛=𝑔𝑢 (v)
𝑏=𝑔𝑡 and 𝑛=𝑔𝑢 (v)
For some 𝑡 and 𝑢 belong to integer (Z) .
put the values 𝑏=𝑔𝑡 and 𝑛=𝑔𝑢 in equation (i). 𝑎=𝑏+𝑘𝑛
𝑎=𝑔𝑡+𝑘𝑔𝑢
𝑎=𝑔(𝑡+𝑘𝑢)
𝑔|𝑎 (vi)
So,
𝑔|𝑎 and 𝑔|𝑛
Then 𝑔|gcd(𝑎,𝑛)
If 𝑑=gcd(𝑎, 𝑛).
→ 𝑔|𝑑 (vii)
From (iv) and (vii)
→ 𝑑|𝑔 (iv)
→ 𝑔|𝑑 (iv)
If and only if 𝑔=𝑑. If 𝑑=gcd(𝑎, 𝑛) and 𝑔=gcd(𝑏, 𝑛).
Then gcd(𝑎,𝑛) = gcd(𝑏,𝑛).