A number when divided by 527 gives a remainder 31. What remainder will...
Number = 527 * Q + 31
= 17 * 31 * Q + 17 + 14
= 17{31 * Q + 1} + 14
So, when divided by 17, the remainder will be 14
View all questions of this test
A number when divided by 527 gives a remainder 31. What remainder will...
Given:
Number when divided by 527 gives a remainder 31
To find:
Remainder obtained by dividing the same number by 17
Solution:
Let the number be x
According to the given condition, we can write
x = 527a + 31 -- (1) where a is any integer
We need to find the remainder when x is divided by 17
x ≡ ? (mod 17)
Substituting the value of x from equation (1)
527a + 31 ≡ ? (mod 17)
We know that 527 ≡ 2 (mod 17) [527 = 17*31 + 10]
Therefore, we can write
527a ≡ 2a (mod 17)
Substituting this in the above equation, we get
2a + 31 ≡ ? (mod 17)
Now, we need to find a value of a such that the above congruence is satisfied and we get the smallest positive integer value of a.
We can try to find such an integer by substituting the values of a one by one and checking the remainder until we get a value that satisfies the congruence. However, this method can be time-consuming and not feasible for large numbers.
Alternatively, we can use the Chinese Remainder Theorem (CRT) to solve this problem.
According to CRT, if we have a system of congruences of the form
x ≡ a (mod m)
x ≡ b (mod n)
where m and n are co-prime, then the solution of the system is given by
x ≡ mbnB + nmaM (mod mn)
where aM and bN are the solutions of the congruences x ≡ 1 (mod m) and x ≡ 0 (mod n) respectively, and MB and MN are the solutions of the congruences MBm ≡ 1 (mod n) and MNn ≡ 1 (mod m) respectively.
Applying CRT to the given congruence, we get
2a + 31 ≡ 0 (mod 17) and 2a + 31 ≡ 0 (mod 1)
Solving the first congruence, we get
2a ≡ -31 ≡ -14 (mod 17)
Multiplying both sides by 9 (the inverse of 2 mod 17), we get
a ≡ -63 ≡ 4 (mod 17)
Therefore, the smallest positive integer value of a that satisfies the congruence is a = 4.
Substituting this value in the congruence 2a + 31 ≡ 0 (mod 17), we get
2(4) + 31 ≡ 8 + 31 ≡ 39 ≡ 5 (mod 17)
Therefore, the remainder obtained by dividing the given number by 17 is 5.
Hence, the correct answer is option (A) 14.