Thus, a+b is a multiple of 24.

[ehrenfest]

[SOLVED] larson 3.2.16c

Homework Statement

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.

Homework Equations

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

 

[Dick]

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.

 

[ehrenfest]

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.

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

 

[durt]

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.

 

[ehrenfest]

Did you find those possible pairs by multiplying mod 24 every possible pair in {1,5,7,11,13,17,19,23} ?

 

[durt]

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.

 

[ehrenfest]

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.

 

[durt]

Right. :)

 

[Dick]

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.

 

[ehrenfest]

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.

 

[Dick]

Sure a is relatively prime to 24, 1/a is it's inverse mod 24. Change the arrow to a <-> if you like.