A Divisibility Proof; Also, a Function with Integer Values to FindDate: 12/31/2011 at 08:48:11 From: amirmath1995 Subject: number theory Let n be a positive integer not divisible by 2 or 3. Prove that for all integers k, $ k^{2} + k + 1 $ divides $ (k + 1)^{n} - k^{n} - 1 $ Sorry for all the LaTeX. Date: 12/31/2011 at 13:49:11 From: Doctor Vogler Subject: Re: number theory Hi, Thanks for writing to Dr. Math. I don't mind LaTeX. Are you familiar with modular arithmetic? Mod, Modulus, Modular Arithmetic http://mathforum.org/library/drmath/view/62930.html You are trying to prove that (k + 1)^n - k^n - 1 = 0 (mod k^2 + k + 1). Well, you know that ... k^2 = -(k + 1) (mod k^2 + k + 1) ... and ... (k + 1)^2 = k (mod k^2 + k + 1). So you should use those two facts. Furthermore, you have k^3 = 1 (mod k^2 + k + 1) and (k + 1)^3 = -1 (mod k^2 + k + 1). Now, n is not divisible by 2 or 3, which means that n = 1 mod 6 or n = 5 mod 6. If n = 1 mod 6, then that means that (k + 1)^n = k + 1 (mod k^2 + k + 1) k^n = k (mod k^2 + k + 1), Whereas if n = 5 mod 6, then that means that (k + 1)^n = -k (mod k^2 + k + 1) k^n = -(k + 1) (mod k^2 + k + 1) Either way, you have your result. Does that make sense? If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/ Date: 12/31/2011 at 08:54:34 From: amirmath1995 Subject: number theory Let a, b be two positive integers, such that $ ab eq 1 $ Find all the integer values that $ f(a, b) $ can take where \[ f(a, b) =\frac{ a^{2} + ab + b^{2} }{ab - 1}. \] Date: 12/31/2011 at 15:07:02 From: Doctor Vogler Subject: Re: number theory Hi, This is one of those problems where you have a method of transforming one solution into another. I will call a "solution" any triple of positive integers (a, b, c) = (a, b, f(a, b)). These triples (a, b, c) have to satisfy the equation c = (a^2 + ab + b^2)/(ab - 1) or a^2 + ab + b^2 = c(ab - 1). Now, the trick here is thinking of this as a quadratic polynomial in a: a^2 + (b - bc)a + (b^2 + c) = 0. Then this polynomial has two solutions (in a, for a given choice of b and c), the product of which is b^2 + c and the sum of which is -(b - bc). For a particular choice of b and c, those two solutions might not be integers, or even rational. But if you have one solution in positive integers, (a, b, c), then another solution will be (bc - b - a, b, c). You can check this directly by substituting bc - b - a for a into the equation a^2 + ab + b^2 = c(ab - 1) Then check that this simplifies to the same equation. So what does this tell us? Well, since the function f(a, b) is symmetric in a and b (that is, f(a, b) = f(b, a)), then we can get from one solution (a, b, c) to either (b, a, c) or (bc - b - a, b, c). For example, we can start with (2, 2, 4) and get to ... (2, 4, 4), (4, 10, 4), (10, 26, 4), (26, 68, 4), (68, 178, 4), (178, 466, 4), (466, 1220, 4), (1220, 3194, 4), (3194, 8362, 4), (8362, 21892, 4), (21892, 57314, 4), ... and so on. In this way, we can keep getting more and bigger solutions. But the value of c = f(a, b) doesn't change, and since you want to know which c values you can get, these can all be considered as a single solution. Notice that we can get that c value with extremely large a and b values, which is annoying because it means that we can't rule out very large a and b values when trying to decide which c values are possible. But there is something else we can do that's just as good: Suppose there is some solution (a, b, c). Maybe a and b are very large, but if so, then we can do the same method of getting from one solution to another, but in the other direction, until we get to the smallest solution in that chain (for that c value). So we suppose that we have a solution in positive integers (a, b, c). If ... a < b, ... then we switch a and b, so that a >= b. And if a >= b and bc - b - a < a, ... then we change a into bc - b - a and repeat. Since the positive integer a + 2b is getting strictly smaller at every step, this can't go on indefinitely, which means that eventually the process will stop at a solution which has both a >= b, and bc - b - a >= a. So we have proven that if there is a positive integer solution (a, b, c) to the equation ... a^2 + ab + b^2 = c(ab - 1), ... then there is another positive integer solution with possibly different a and b but which has the same c and also satisfies the inequalities a >= b, and bc - b - a >= a. We might call such a solution a "minimal solution." So if we want to decide what c values are possible, then we only have to find all of the (minimal) solutions in positive integers to c = (a^2 + ab + b^2)/(ab - 1), a >= b, c >= (2a + b)/b. Taking the first and last two inequalities, we get (a^2 + ab + b^2)/(ab - 1) >= 2a/b + 1 Since b and ab - 1 are both positive, we can multiply by their product and not change the direction of the inequality: (a^2 + ab + b^2)b >= (2a + b)(ab - 1). Then we simplify to b^2 + 2a + b >= ba^2. But we know that a >= b, so that means that the right side will usually be larger (not smaller than the left). For example, if a >= 3 and b >= 2, then ba^2 >= 3ab = ab + ab + ab > b^2 + 2a + b. So any minimal solutions must have either b < 2 or a < 3. Well if b < 2, then since b is a positive integer, the only possibility is b = 1. And if b is not 1 but a < 3, then a >= b implies that ... 1 < b <= a < 3, ... so b = a = 2. Well, if a = b = 2, then c = 4. And if b = 1, then c = (a^2 + a + 1)/(a - 1) = a + 2 + 3/(a - 1) This means that a - 1 must be a factor of 3, so either a - 1 = 1, or a - 1 = 3 The first case gives b = 1 and a = 2, so c = 7. The second gives b = 1 and a = 4, and c = 7 still. (Actually, the second is not even a minimal solution.) So the only possible values for c are 4 and 7. And you can get all solutions in positive integers by starting with either (2, 2, 4) or (1, 2, 7) and then repeatedly applying the transformations (a, b, c) -> (b, a, c), or (a, b, c) -> (bc - b - a, b, c). If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, 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/