Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Which Elements are Divisible by 11?


Date: 07/12/99 at 11:43:12
From: James Knotts
Subject: Sequence question

1. Determine all solutions w = x+y+z, (1/w) = (1/x)+(1/y)+(1/z).

2. A sequence is generated as follows: the first number is 0 and  
   the second number is 1. Subsequent numbers are generated by 
   concatenating the prior two numbers (thus the first five numbers 
   are 0,1,10,101,10110). Which elements of the sequence are divisible 
   by 11?

Thank you,
James Knotts


Date: 07/12/99 at 17:47:56
From: Doctor Anthony
Subject: Re: Sequence question

>1. Determine all solutions w = x+y+z, (1/w) = (1/x)+(1/y)+(1/z).
         
       1        yz + zx + xy
    ------- =  -------------- 
     x+y+z          xyz

    xyz = (x+y+z)(yz+zx+xy)  ........(1)

If you consider the cubic equation

   t^3 - t^2 + t - 1 = 0  ..........(2)

If x, y, z are the roots of this cubic then x+y+z = 1
                                         xy+yz+zx = 1
                                              xyz = 1  

and these will satisfy equation (1) above.

It follows that x, y, z are to roots of the equation (2). So we must 
solve equation (2)

 The lefthand side factorizes to t^2(t-1) + (t-1) = 0
 
                                    (t-1)(t^2 +1) = 0

So the three roots are t = 1,  t = +-i

So we let  x = 1,  y = +i,   z = -i

In this case w = 1

Another set of solutions could be obtained by solving

   t^3 + t^2 + t + 1 = 0       x+y+z = -1
                            xy+yz+zx = 1
                                 xyz = -1   

Now the roots are  -1,  -i,   +i

In this case w = -1

- Doctor Anthony, The Math Forum
http://mathforum.org/dr.math/   


Date: 07/13/99 at 09:11:38
From: Doctor Rob
Subject: Re: Sequence question?

Thanks for writing to Ask Dr. Math!

1. If you are looking for integer values of w, x, y, and z, then 
this is how to proceed.

First of all, there are no solutions with x,y,z > 0, because then you
would have

   1/x < 1/x + 1/y + 1/z = 1/(x+y+z) < 1/x,

a contradiction.

There are no solutions with x,y,z < 0, because if there were, then
(-x), (-y), (-z), (-w) would give you a solution with all positive 
numbers.

Thus at least one of the three is positive, and one negative. By the
same argument as in the last paragraph, and by the symmetry of the
equation, we can assume that x, y > 0, and z < 0.

Let k = GCD(x,y,z), and let a, b, and c be positive integers such that

   x = k*a,
   y = k*b,
   z = -k*c.

Then GCD(a,b,c) = 1.  Now define

   d = GCD(b,c),
   e = GCD(a,c),
   f = GCD(a,b).

Now you can show that GCD(d,e) = GCD(d,f) = GCD(e,f) = 1.  Thus

   x = k*e*f*X,
   y = k*d*f*Y,
   z = -k*d*e*Z,

for some positive integers X, Y, and Z.  It's easy to see that
GCD(X,Y) = GCD(X,Z) = GCD(Y,Z) = 1, and its also true that
GCD(d,X) = GCD(e,Y) = GCD(f,Z) = 1.  Now substituting these into the 
equation

   1/(x+y+z) = 1/x + 1/y + 1/z,

clearing fractions, and cancelling like factors from both sides, you
should get

   d*e*f*X*Y*Z = (e*f*X+d*f*Y-d*e*Z)*(d*Y*Z+e*X*Z-f*X*Y).

Now d, e, and f are pairwise relatively prime, and divide the left
side, so they divide the right side, but they are relatively prime
to the first factor, so

   d*e*f | d*Y*Z+e*X*Z-f*X*Y.

Similarly X, Y, and Z are pairwise relatively prime, and divide the
left side, so they divide the right side, but they are relatively
prime to the second factor, so

   X*Y*Z | e*f*X+d*f*Y-d*e*Z.

This means that

   d*e*f = u*(d*Y*Z+e*X*Z-f*X*Y),
   X*Y*Z = u*(e*f*X+d*f*Y-d*e*Z),

where u = 1 or -1.

Assume first that u = 1.  Add the first equation to the second, and
bring all terms to the left side of the equation:

   X*Y*Z - (d*Y*Z+e*X*Z-f*X*Y) - (e*f*X+d*f*Y-d*e*Z) + d*e*f = 0,
   (X-d)*(Y-e)*(Z+f) = 0.

This implies that either X = d or Y = e, because 0 < Z = -f < 0 is
impossible. This implies that either X = d = 1 or Y = e = 1.  In 
either case, you can conclude that Z = f = 1, and the two sets of
solutions are given by z = -x or z = -y:

   1/(x+y-x) = 1/x + 1/y + 1/(-x), or
   1/(x+y-y) = 1/x + 1/y + 1/(-y).

You supply the reasons and the rest of the details.

2. The following argument works in any base:

Let the numbers be called X(n), and let the Fibonacci numbers be 
called F(n), so we have the following table:

   n    X(n)             F(n)
   1    0                1
   2    1                1
   3    10               2
   4    101              3
   5    10110            5
   6    10110101         8
   7    1011010110110    13

Notice that X(n) contains F(n) digits. (You can prove this by 
induction.) Then X(n) satisfy the following recursion:

   X(n+1) = X(n)*10^F(n-1) + X(n-1).

Now 10^F(n-1) (mod 11) has the pattern 0,1,1,0,1,1,0,1,1,..., 
for n = 1,2,3,4,5,6,7,8,9,..., of period 3. That means that X(n) 
satisfy the three equations

   X(3*k) = -X(3*k-1) + X(3*k-2) (mod 11),
   X(3*k+1) = -X(3*k) + X(3*k-1) (mod 11),
   X(3*k+2) = X(3*k+1) + X(3*k) (mod 11).

Putting these together, 

   X(3*k+3) = -X(3*k) = X(3*k-3) (mod 11),
   X(3*k+2) = X(3*k-1) = X(3*k-4) (mod 11),
   X(3*k+1) = X(3*k-5) (mod 11).

This means that X(n+6) = X(n) (mod 11) for all n. Thus we only need to 
compute the remainders for X(1) through X(6) to see what happens 
there.

It turns out that there are two cases, base 2 or larger bases. If the 
base is 2, then X(3*k+1) is divisible by 11 for all k >= 0, and only 
those. If the base is larger than 2, that X(6*k+1) is divisible by 11 
for all k >= 0, and only those.

You fill in the reasons and the details.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/   
    
Associated Topics:
High School Sequences, Series

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/