1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Larson 3.2.16c

  1. Jan 3, 2008 #1
    [SOLVED] larson 3.2.16c

    1. The problem statement, all variables and given/known data
    Let x be an integer one less than a multiple of 24. Prove that if a and b are positive integers such that ab=x, then a+b is a multiple of 24.


    2. Relevant equations



    3. The attempt at a solution
    ab=24n-1 implies that ab is congruent to 2 mod 3 and congruent to 7 mod 8

    ab=(a+1)(b+1) -ab-1 = (a+1)(b+1)-24n so ab is congruent to (a+1)(b+1) mod 3 and mod 8

    I checked this for n up in {1,...,9}. This is obviously true when 24n-1 is prime. The only n I found in that set for which it is not prime are n=4 and n=9 and it works in both cases.

    n=4 gives 95=5*19
    n=9 gives 215=5*43
     
  2. jcsd
  3. Jan 3, 2008 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    There are only 4 ways to factor a*b=23 mod 24. You could just find them all. Notice if a*b=23 mod 24 then both a and b are relatively prime to 24. That narrows the search down quite a bit.
     
    Last edited: Jan 3, 2008
  4. Jan 3, 2008 #3
    Umm... there are C(24,2)+24= 12*23+24= 300 possibilities for a and b and we only eliminated about 50 of them.

    EDIT: this is a ridiculous overestimate
     
    Last edited: Jan 3, 2008
  5. Jan 3, 2008 #4
    The numbers relatively prime to 24 are 1, 5, 7, 11, 13, 17, 19, and 23. Notice then that (WLOG), the possible pairs (a, b) satisfying the congruence are (1, 23), (5, 19), (7, 17), and (11, 13), each of which sum to 24.
     
  6. Jan 3, 2008 #5
    Did you find those possible pairs by multiplying mod 24 every possible pair in {1,5,7,11,13,17,19,23} ?
     
  7. Jan 3, 2008 #6
    I applied the cancellation rule: if gcd(c, m) = 1 and ca = cb (mod m), then a = b (mod m). So, for example, if 5a = 5b (mod 24), then a = b (mod 24). Hence there is only one pair (5, 19) involving a 5, and you don't have to try (5, 1), (5, 5), (5, 7), etc.
     
  8. Jan 3, 2008 #7
    AHA.
    So if you find (5,something) that works you know (5, something else) will not work. And you wisely selected 19 to try first because if the result is true, then (5,19) is the only one that can work.
     
  9. Jan 3, 2008 #8
    Right. :)
     
  10. Jan 4, 2008 #9

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    You know, thinking about this, there is a way to do this without finding all of the pairs. a*b=23 mod 24 is the same as a*b=(-1). So b=(-1/a) (mod 24, of course!). So a+b=0=a-1/a -> 0=a^2-1=(a+1)*(a-1). Since a is relatively prime to 24, it's not divisible by 2 or 3. If a is not divisible by 2 or 3, then (a+1)*(a-1) is divisible by 24.
     
  11. Jan 4, 2008 #10
    Does (1/a) mod 24 mean the inverse of a mod 24? That is, is (1/a) the unique number x such that x*a=1 mod 24? 1/a mod 24 would not be defined if a and 24 were not relatively prime, correct?

    Also, I think the arrow in your proof is pointing the wrong way. We are trying to prove that a+b=0 mod 24.
     
  12. Jan 4, 2008 #11

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Sure a is relatively prime to 24, 1/a is it's inverse mod 24. Change the arrow to a <-> if you like.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Larson 3.2.16c
  1. Larson 4.1.6 (Replies: 4)

  2. Larson 4.1.8 (Replies: 1)

  3. Larson 4.2.15 (Replies: 7)

  4. Larson 4.4.13 (Replies: 7)

  5. Larson 4.4.24 (Replies: 1)

Loading...