# Thread: A number satsifying certain divisibility conditions

1. ## 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...

2. ## CRT

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

3. really brilliant thanks man