Results 1 to 3 of 3

Math Help - A number satsifying certain divisibility conditions

  1. #1
    Junior Member
    Joined
    Jul 2009
    Posts
    57

    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...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Jul 2009
    Posts
    111
    Thanks
    1

    Thumbs up 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
    Last edited by MAX09; August 10th 2009 at 04:57 AM. Reason: Corrections in solution
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jul 2009
    Posts
    57
    really brilliant thanks man
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: January 30th 2011, 07:32 PM
  2. Replies: 1
    Last Post: July 23rd 2010, 05:53 AM
  3. Number Theory: Divisibility
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 25th 2007, 07:56 PM
  4. Number theory, divisibility by 22
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: September 12th 2006, 05:30 PM

Search Tags


/mathhelpforum @mathhelpforum