Find the greatest number that will divide 43, 91 and 183 so as to leave the same remainder in each case.

Question

I KNOW THIS IS SOLUTION BUT I DON'T KNOW WHY?
We first find the difference of the numbers and then find the HCF of the got numbers.
183−91=92
183−43=140
91−43=48
Now find HCF of 92, 140 and 48, we get
92=2×2×23
140=2×2×5×7
48=2×2×2×2×3
HCF(92, 140, 48) = 4
Therefore, 4 is the required number.
Can you explain how we get correct answer using this method.

Bill Dubuque · Answer

Call the greatest number $n$ and the common remainder $x$, so our problem is
$$begin{align}  
x&equiv 43pmod{n}\
x&equiv 91pmod{n}\
x&equiv 183!!!pmod{n} end{align}qquad$$
By general CRT theory this system is solvable iff pairwise solvable, i.e. iff
$$begin{align} &nmid 91!-!43,, 183!-!91,, 184!-!43\
iff   &nmid 48,92,140\
iff   &nmid gcd(48,92,140) = 4end{align}  $$
where the final arrow is by the gcd Universal Property.

Find the greatest number that will divide 43, 91 and 183 so as to leave the same remainder in each case.

One Answer

Add your own answers!

Ask a Question