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,

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
Math Forum Home || Math Library || Quick Reference || Math Forum Search