# HW 8 16. Determine whether the integers in each of these sets are pairwise relatively prime. a) 21, 34, 55 b) 14, 17, 85 c) 25, 41, 49, 64 The value of the Euler ϕ-function at the positive integer n...

HW 8
16. Determine whether the integers in each of these sets are pairwise relatively prime.
a) 21, 34, 55
) 14, 17, 85
c) 25, 41, 49, 64
The value of the Euler ϕ-function at the positive integer n is defined to be the number of positive integers less than or equal to n that are relatively prime to n. For instance, ϕ(6) = 2 because of the positive integers less or equal to 6, only 1 and 5 are relatively prime to 6. [Note: ϕ is the Greek letter phi.]
21. Find these values of the Euler ϕ-function.
a)ϕ(4)
)ϕ(10)
c)ϕ(13)
25. What are the greatest common divisors of these pairs of integers?
a) 37 · 53 · 73, 211 · 35 · 59
) 11 · 13 · 17, 29 · 37 · 55 · 73
c) 2331, 2317
d) 313 · 517, 212 · 721
e) 1111, 0
3. Encrypt the message DO NOT PASS GO by translating the letters into numbers, applying the given encryption function, and then translating the numbers back into letters.
a)f(p) = (p + 12) mod 26
)f(p) = (14p + 21) mod 26
c)f(p) = (−7p + 1) mod 26
5. Decrypt these messages encrypted using the shift cipher f(p) = (p + 7) mod 26.
a) AEBOX XYG
) LL WO PBSOXAA
c) BACS PYB PXA
Answered 2 days AfterApr 10, 2022

## Solution

Anandkumar answered on Apr 12 2022
Question 1:
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.
) 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:
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
) Ø(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: