(a) Use Euclidean algorithm to find the gcd of 105 and 231.
(b) Use mathematical induction to show that
1 · 1! + 2 · 2! + · · · + n · n! = (n + 1)! − 1
(c) Show that the relation ∼ defined on R as a ∼ b if b−a ∈ Q, is an equivalence relation.
Also, find the equivalence class of 1.
(a) GCD(105,231)
Set up a division problem where a is larger than b.
a ÷ b = c with remainder R. Do the division. Then replace a with b, replace b with R and repeat the division. Continue the process until R = 0.
231 ÷ 105 = 2 R 21 (231 = 2 × 105 + 21)
105 ÷ 21 = 5 R 0 (105 = 5 × 21 + 0)
When remainder R = 0, the GCF is the divisor, b, in the last equation. GCD = 21 [Answer]
(b) Use mathematical induction to show that
1 · 1! + 2 · 2! + · · · + n · n! = (n + 1)! − 1
S1=1.1!=1
=(1+1)!-1=2!-1=2-1=1
Sk= 1.1! + 2 · 2! + · · · + k · k! = (k + 1)! − 1
Sk+1= 1.1! + 2 · 2! + · · · + k+1 · (k+1)! = (k+1 + 1)! − 1=(k+2)!-1
Therefore,
Sk+ Ak+1 =Sk+1, where Ak+1 = k+1 · (k+1)!
(k+1)!-1 +k+1 · (k+1)! = (k+1)![1+(k+1)]−1 = (k+1)![k+2]−1=(k+2)!−1 [Answer]
(c) Show that the relation ∼ defined on R as a ∼ b if b−a ∈ Q, is an equivalence relation.
Also, find the equivalence class of 1.
Let us show that a relation '' on by ' if ∈ Q is an equivalence relation, that is reflexive, symmetric, and transitive.
For each , , and thus each , and the relation is reflexive.
If , then . It follows that , and thus Consequently, the relation is symmetric.
Let and . Then . It follows that , and thus . Therefore, the relation is transitive.
By definition, the equivalence class of an element is .
Let us give the equivalence classes of 1
[Answer]
Comments