wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Divisible by 12
        
(Message started by: NickH on Jan 7^th, 2003, 5:32am)

Title: Divisible by 12
Post by NickH on Jan 7^th, 2003, 5:32am

Let a and b be integers such that a + b + ab is divisible by 12. What is the most we can deduce about a and b?

Title: Re: Divisible by 12
Post by towr on Jan 7^th, 2003, 8:31am

I don't know what the most is..
But at least a, and b are integer (trivial deduction)
a-b is divisible by 12
a (and likewise b) is either 6*i, or 6*i -2 for some integer i

Title: Re: Divisible by 12
Post by Cyrus on Jan 7^th, 2003, 9:34am

I also don't know what the MOST is, but I've come up with a few constraints:

1) a & b must be integers and must be even
2) a + b must be a multiple of 4
3) a - b must be either 0 or a multiple of 12
4) ab must be a multiple of 4

This is another problem though, where I used my usual approach:
1) I came up with a few (5) possible solutions.
2) I then made some assumptions/constraints based on those solutions.
3) I tested my constraints by trying other numbers to see if I could find a pair of numbers that proved my constraints wrong.

The problem with my approach, is clear even to me. How can I be SURE this is the OPTIMAL/maximum amount of constraints? And unless I tested infinite numbers through my constraints how can I be sure that my constraints are even correct at all??

Title: Re: Divisible by 12
Post by Cyrus on Jan 7^th, 2003, 9:38am

on 01/07/03 at 08:31:33, towr wrote:

a-b is divisible by 12
a (and likewise b) is either 6*i, or 6*i -2 for some integer i

Oh, I just now read your post towr, and I like that 2nd point
"a must be either 6x or 6x-2", so that should be added to my list. See I missed one already.

Title: Re: Divisible by 12
Post by towr on Jan 7^th, 2003, 10:14am

it's easy enough to prove a and b are even, and thus a*b is a multiple of 4.. After that I don't know..

a+b+ab=12N for some integer a,b,N
(a+1)(b+1)-1=12N
(a+1)(b+1)=12N-1 , 12N-1 is always odd, so a+1 and b+1 are odd, so a and b have to be even..

Title: Re: Divisible by 12
Post by towr on Jan 7^th, 2003, 10:23am

here are some example solutions to work with:


-30  -30            -14  -14              0   12             18  -30
-30  -18            -14   -2              0   24             18  -18
-30   -6            -14   10              4  -20             18   -6
-30    6            -14   22              4   -8             18    6
-30   18            -12  -24              4    4             18   18
-30   30            -12  -12              4   16             18   30
-26  -26            -12    0              4   28             22  -26
-26  -14            -12   12              6  -30             22  -14
-26   -2            -12   24              6  -18             22   -2
-26   10             -8  -20              6   -6             22   10
-26   22             -8   -8              6    6             22   22
-24  -24             -8    4              6   18             24  -24
-24  -12             -8   16              6   30             24  -12
-24    0             -8   28             10  -26             24    0
-24   12             -6  -30             10  -14             24   12
-24   24             -6  -18             10   -2             24   24
-20  -20             -6   -6             10   10             28  -20
-20   -8             -6    6             10   22             28   -8
-20    4             -6   18             12  -24             28    4
-20   16             -6   30             12  -12             28   16
-20   28             -2  -26             12    0             28   28
-18  -30             -2  -14             12   12             30  -30
-18  -18             -2   -2             12   24             30  -18
-18   -6             -2   10             16  -20             30   -6
-18    6             -2   22             16   -8             30    6
-18   18              0  -24             16    4             30   18
-18   30              0  -12             16   16             30   30
-14  -26              0    0             16   28

Title: Re: Divisible by 12
Post by NickH on Jan 8^th, 2003, 5:29am

towr, I got your original result, namely that a and b are either both divisible by 6, or both leave a remainder of 4 when divided by 6.

As you indicated, write a + b + ab = (a + 1)(b + 1) - 1.
Then (a + 1)(b + 1) = 1 (modulo 12.)

Hence a + 1 and b + 1 are coprime with 12.
Considering the multiplication table, mod. 12, the following are the only possibilities for a + 1 and b + 1:

a + 1 = 1 => b + 1 = 1
a + 1 = 5 => b + 1 = 5
a + 1 = 7 => b + 1 = 7
a + 1 = 11 => b + 1 = 11

Therefore a = b = 0, 4, 6, or 10 (mod 12.)
Equivalently, a = b = 0 or 4 (mod. 6.)

Nick