Thread: A number satsifying certain divisibility conditions

1.If a number is divided by 9, the remainder is 1 and if the same number is divided by 11 the remainder is 8.
Col A: The number
Col B: 19

if the number is 19 both r equal my question is is there any other number other than 19 satisfying this condition...

Multiple answers for this problem can be found out using Chinese Remainder Theorem

The problem can be rephrased to find x which is a [multiple of 9] +1 and a [multiple of 11] + 8 simultaneously.
That is, x =+ 1 mod 9
x =+ 8 mod 11 where =+ is congruence modulo operation.

This can be solved by using the Chinese remainder theorem.

If you haven't come across this theorem yet, follow this link Chinese remainder theorem - Wikipedia, the free encyclopedia

The first point which is in favour of using the CRT is that 9 and 11 are relatively prime. That is there exists two integers a and b such that 9a + 11b = 1.

We can use the Extended Euclidean algorithm to find the two integers a and b as a = 5 and b= -4.

Now by CRT, we find the solution by the following computation.

9*a*8 + 11*b*1 = x mod (9*11)

Remember we are multiplying 9 and the remainder when 'x' is divided by 11.
Similarly we multiply 11 and the remainder when 'x' is divided by 9.

Substituting a = 5 and b=-4 gives us
9*5*8 + 11*(-4)*1 = 360 -44 = 316

316 itself is a solution for this problem as 316 = 28*11 + 8
= 35*9 + 1

But 316 can be written as 99*3 + 19 which implies the general solution for the problem would be 19 mod 99.

19{plus or minus} any multiple of 99 will be a solution for this equation.

19 + 99*1 = 99+19 = 118 = [11*10 + 8] = [13*9 + 1]
19 + 99*2 = 198+19 = 217 = [24*9 + 1] = [19*11 + 8]

19 - 99*1 = 19 - 99 = -80 = 9*-9 + 1 = 11*-8 + 8
19 - 99*2 = 19 - 198 = -179 = 9*-20 + 1 = 11* -17 +8

We've got 6 answers so far. 19, 316, 118, 217,-80,-179.

You can improvise with more multiples of 99.

Hope it helped,
MAX

really brilliant thanks man