Answer To: HW 8 16. Determine whether the integers in each of these sets are pairwise relatively prime. a) 21,...
Anandkumar answered on Apr 12 2022
Question 1:
Answer: a) 21, 34, 55
Two integers are said to be relatively prime if they don’t have any common factors other than 1.
Let’s take 21, 34, 55
21 can be written as 3*7
34 can be written as 2*17
55 can be written as 5*11
The are no common factors for 21, 34 and 55 other than 1.
b) lets find the gcd of the pairs
factors of 14: 1,2,7,14
factors of 17:1,17
factors of 85 : 1,5,17,85
gcd(14,17)=1
gcd(17,85)=17
which is not equal to 1
so we can say that 14,17,85 are not pairwise relatively prime
c) lets find the gcd of the pairs
25, 41, 49, 64
GCD(25,41) = 1
GCD(25,49) = 1
GCD(25,64) = 1
GCD(41,49) = 1
GCD(41,64) = 1
GCD(49,64) = 1
The above given pair of integers are relatively prime.
Question 2:
Answer: Euler’s function:
The numbers of the positive integers less than n and prime to it denoted by Ø(n)
Ø(n) = Number of numbers between 1 and (n-1) that are relatively prime to n.
a) Ø(4) = {1, 2, 3}
1 and 3 are relatively prime to 4
Ø(4) = 2
b) Ø(10) = {1, 2, 3, 4, 5, 6, 7, 8, 9}
Ø(10) = {1, 3, 5, 7, 9}
1, 3, 5, 7 and 9 are relatively prime to 10
Ø(10) = 4
c) Ø(13) = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
Ø(13) = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} are relatively prime to 13
Therefore, Ø(13) = 12
Question 3:
Answer: Greater common devisor:
Let a, b be integers
Suppose a = P1a1 , P2a2 , …….., Pnan
b = P1a1 , P2a2 , …….., Pnan
where each exponent is a non-negative...