[Techniques in Symbolic Computation] Equivalence classes / Diophantine equation / Bezout's Identity

< Equivalence classes >

Problem )

Verify that the relation, two ordered pairs(a,b) and (c,d) are equivalent if ad= bc, is an equivalence relation on the set S of all ordered pairs (a, b) of integers with b̸=0.

-->  

(1) reflexive : For all (a, b) ∈ X, ab = ba. This is clearly true. Hence R is reflexive. 

(2) symmetric : For all (a,b),(c,d) ∈ X, suppose (a,b)R(c,d). Then ad = bc if and only if cb = da if and only if (c,d)R(a,b). 

                           Therefore, R is symmetric. 

(3) transitive : Now, see what you can do with the following : Take arbitrary (a,b), (c,d),(e,f) and assume (a,b)R(c,d), and (c,d)R(e,f).  So  ad = bc, and cf = de 

Now, we use a little algebra to show that this implies af = be, and hence (a,b)R(e,f).

ad = bc <=> adf = bcf = b(cf). Also, we have cf = de. So adf = b(de) <=> af =be, as desired. 

The relation has all three properties, and hence, is by definition, an equivalence relation. 

 

 

 

 

 

< Number-theoretic problems > 

a ≡ b (mod n )  <=> n | b-a

                              <=> a and b have saved remainder when divided by n. 

 

a ≡ (last 2 digits)(mod 100) 

 

Problem  )

 

What is the probability that the last two digits of 7^n are 43?   = > 1/4 

 

-- >  n = 0 ----> 7^0 = 1

         n = 1 ----> 7^1 = 7

         n = 2 ----> 7^2 = 49

         n = 3 ----> 7^3 = 43 ( 343 - last two digits)

         n = 4 ----> 7^4 = 1     (301 - alst two digits) 

         n = 5 ----> 7^5 = 7     (301 - alst two digits) 

           ...

 

 

 

< Diophantine equation > 

def) ax + by = gcd(a,b) 

Suppose a and b are integers. Mathematically, a,b  ∈ Z.

Then the diophantine equation ax + by = gcd(a,b) has a solution. 

 

Problem )

Find the solution to the diophantine equation 47x + 30 y = 1. 

-->  The strategy is to use the Euclidean Algorithm. Remember, if you divide a by b, you get a quotient q and a remainder r. They satisfy a = b q  + r.

 

47 = 30(1) + 17

30 = 17(1)  + 13

17 = 13(1) + 4

13 = 4(3) + 1

 

---> Solve for the remainders : 47 = 30(1) + 17 => 17 = 47 (1) + 30(-1)

                                                      30 = 17 (1) + 13 => 13 = 30(1) + 17(-1)

                                                       17 = 13 (1) + 4   => 4 = 17(1) + 13(-1)

                                                       13 = 4 (3) + 1    => 1 = 13(1) + 4 (-3)

                                                 ----------------------------------------------

                                                                        1  = 13 (1) + 4(-3)   Substitute for 4

                                                                            = 13 (1) + [ 17(1) + 13(-1) ](-3)   

                                                                            = 13 (1) + 17(-3) + 13(1) 

                                                                            = 13 (4) + 17(-3) 

                                                                            = 13 (4) + 17(-3) Substitute for 13

                                                                            = [30(1) + 17(-1)] (4) + 17(-3) 

                                                                            = 30 (4) + 17(-7) Substitute for 17

                                                                            = 30 (4) + [ 47 (1) + 30(-1) ](-7)

                                                                            = 30 (11) + 47(-7)  Done!! 

 

 

=> So the equation 47 x + 30 y = 1 has a solution : x = -7, y = 11

 

 

 

 

<  Bezout's Identity > 

def) If GCD(a,b) = d  where a and b are positive integers

then xa + yb = d where x and y are integers 

 

Problem )

 

Find x and y such that 140x + 252y = GCD(140,252)

 

--> 252 = 1 (140) + 112

       140 = 1 ( 112 ) + 28         == > GCD  is 28   ==> 140x + 252y = 28 

       112 = 4 ( 28 ) + 0

 

 => 28 = 140 - 1 (112) 

       28 = 140 - 1 [252 - 1 (140) ]      

       28 = (2) 140 - (1)252     = > x = 2, y = -1 

 

=> So the equation 40x + 252y = GCD(140,252) has a solution :  x = 2, y = -1