Subnetting
August 29, 2024Sockets
August 29, 2024Computer-Networks
|
Question 305
|
You are told that n = 110179 is the product of two primes p and q. The number of
positive integers . less than n that are relatively prime to n (i.e. those m such that
gcd(m, n) = 1) is 109480. What is the value of p + q.
positive integers . less than n that are relatively prime to n (i.e. those m such that
gcd(m, n) = 1) is 109480. What is the value of p + q.
|
700
|
|
|
750
|
|
|
600
|
|
|
650
|
Question 305 Explanation:
We use the concept of Euler to find function. It is used to give the no. of numbers which are less than and relatively prime to n and is represented as, Q(n).
So, ATQ,
n = p = q = 110179 —(1)
and Q(n) = (p-1)(q-1) = 109480 —(2)
Now let’s solve (2),
pq – p – q + 1 = 109480
Let put value of pq from (1),
110179 – p – q + 1 = 109480
110180 – 109480 = p + q
Therefore p+q = 700
So, ATQ,
n = p = q = 110179 —(1)
and Q(n) = (p-1)(q-1) = 109480 —(2)
Now let’s solve (2),
pq – p – q + 1 = 109480
Let put value of pq from (1),
110179 – p – q + 1 = 109480
110180 – 109480 = p + q
Therefore p+q = 700
Correct Answer: A
Question 305 Explanation:
We use the concept of Euler to find function. It is used to give the no. of numbers which are less than and relatively prime to n and is represented as, Q(n).
So, ATQ,
n = p = q = 110179 —(1)
and Q(n) = (p-1)(q-1) = 109480 —(2)
Now let’s solve (2),
pq – p – q + 1 = 109480
Let put value of pq from (1),
110179 – p – q + 1 = 109480
110180 – 109480 = p + q
Therefore p+q = 700
So, ATQ,
n = p = q = 110179 —(1)
and Q(n) = (p-1)(q-1) = 109480 —(2)
Now let’s solve (2),
pq – p – q + 1 = 109480
Let put value of pq from (1),
110179 – p – q + 1 = 109480
110180 – 109480 = p + q
Therefore p+q = 700