Bissoy.com
Doctors Medicines MCQs Q&A

If a and b are any positive integers and a ≡ b(mod n) then 

If a and b are any positive integers and a ≡ b(mod n) then  Correct Answer gcd(a, n) = gcd(b, n)

Concept:

Let n be a fixed positive integer, then two integers a and b are congruent modulo n, denoted by a ≡ b(mod n) if n divides (a - b).

Calculations:

Let d = gcd(a, n) and e = gcd(b, n)

Now 

a ≡ b(mod n) 

⇒ n|(a -b)

⇒ (a - b) = kn for some k ∈ Z

Next,

d = gcd(a, n)

⇒ d|a and d|n

⇒ d|b

Now,

d|b and d|n

⇒ d|e     ( ∵ e = gcd(b, n) )

Now,

e = gcd(b, n)

⇒ e|d     (∵ e|b and e|n )

Hence, d = e, i.e gcd(a, n) = gcd(b, n)

Hence, the correct answer is option 1)

Related Questions

A, B, C, D and E are five different integers. When written in the ascending order of values, the difference between any two adjacent integers is 4. D is the greatest and A is the least. B is greater than E but less than C. The sum of the integers is equal to E. What is the positive difference between the lowest and the highest integers?
The average of 4 positive integers is 59. The highest integer is 83 and the lowest integer is 29. The difference between the remaining two integers is 28. Which of the following integers is higher of the remaining two integers ?
Let Z be the set of real integers and R the set of real numbers. The sampling process may be viewed as partitioning the x-y plane into a grid, with the central coordinates of each grid being from the Cartesian product Z2, that is a set of all ordered pairs (zi, zj), with zi and zj being integers from Z. Then, f(x, y) is a digital image if (x, y) are integers from Z2 and f is a function that assigns a gray-level value (that is, a real number from the set R) to each distinct coordinate pair (x, y). What happens to the digital image if the gray levels also are integers?
Four positive integers are given. If the average of any two of them is added to the remaining two integers, the numbers 46, 49, 48, 45, 44 and 47 are obtained. What is the average of the given four integers?
Consider the first order predicate formula ϕ: ∀x [(∀z z|x ⇒ ((z = x) ∨ (z = 1))) ⇒ ∃w (w > x) ∧ (∀z z|w ⇒ ((w = z) ∨ (z = 1)))] Here ‘a|b’ denotes that ‘a divides b’, where a and b are integers. Consider the following sets: S1. {1,2,3, ... , 100} S2. Set of all positive integers S3. Set of all integers Which of the above sets satisfy φ?
The average of 5 positive integers is 60. If the average of 3 of these integers is 67, what is the greatest possible value that one of the other two integers can have?
Two sets of 4 consecutive positive integers have exactly one integer in common. The sum of the integers in the set with greater numbers is how much greater than the sum of the integers in the other set?
Suppose that P(n) is a propositional function. Determine for which positive integers n the statement P(n) must be true if: P(1) and P(2) is true; for all positive integers n, if P(n) and P(n+1) is true then P(n+2) is true.
A rectangular wheat field has an area of 1682 sq. metres whereas its perimeter is 29a × 3b × 2c metres. If the length and breadth are positive integers, then find the perimeter. (It is known that a, b, c are positive integers.)
Suppose that P(n) is a propositional function. Determine for which positive integers n the statement P(n) must be true if: P(1) is true; for all positive integers n, if P(n) is true then P(n+2) is true.