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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/