Associated Topics || Dr. Math Home || Search Dr. Math

### A Divisibility Proof; Also, a Function with Integer Values to Find

Date: 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.

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).

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/

Associated Topics:
High School Number Theory

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