- #26

- 363

- 8

Oops! Back to the drawing board. Thanks for the correction.Your first step fails: the hypothesis that b is not a power of a does not imply that b is divisible by a prime that doesn't divide a.

e.g. consider b = 12 and a = 6.

Petek

- Thread starter herraotic
- Start date

- #26

- 363

- 8

Oops! Back to the drawing board. Thanks for the correction.Your first step fails: the hypothesis that b is not a power of a does not imply that b is divisible by a prime that doesn't divide a.

e.g. consider b = 12 and a = 6.

Petek

- #27

- 363

- 8

Petek

- #28

- 841

- 0

I agree that Mathman and I were probably reading the problem incorrectly, because given thatI've just read Dodo's note and the previous replies now make more sense. But I think what he says is certainly correct. It is the case that

[itex](\exists k\in N)b=a^k\implies(\forall n\in N)a^n-1|b^n-1[/itex]

I think we're being asked to prove the converse. The question wouldn't make much sense read the other way.

The converse is likely to be a lot more awkward, which is why I wanted to get an idea of how much more awkward before I started thinking about it.

[itex](\forall n\in N)a^n-1|b^n-1[/itex] it is difficult to show that a|b much less that

[tex]b = a^k[/tex] While the converse is easily verified.

- #29

- 330

- 3

Following Petek's lead I located the site to which I assume he refers, viz: http://www.mathlinks.ro/Forum/topic-4556.html through Google and I append a copy of the transcription of Marius Cavachi's original proof taken from the site.

I've "Latexed" it and cleaned it up a bit. Hopefully I've not introduced errors, but I haven't been through the proof yet, so it's quite possible I have. If necessary I'll remove these as I notice them or if anyone pointss them out.

Unfortunately I've had to append the proof in two posts (following) because it seems to flake the system out if I use one.

- #30

- 330

- 3

Define a sequence [itex]{(Q_k)}[/itex] of polynomials with [itex]{deg(Q_k) \leq k}[/itex] by [itex]{Q_0 = -1}[/itex], and

[itex]{Q_{k+1}(x) = a^{k+1}(x-1)Q_k(bx)-b(a^{k+1}x-1)Q_k(x)}[/itex] for [itex]{k \geq 0}[/itex].

Observe that [itex]{Q_{k+1}(0) = (b - a^{k+1})Q_k(0)}[/itex]. Iterating this and employing [itex]{Q_0 = -1}[/itex] leads to

[itex]{Q_k(0) = -(b - a^k )(b - a^{k-1} )...(b - a)}[/itex].

Assume that [itex]{b\neq a^j}[/itex] for every non-negative integer [itex]{j}[/itex], so that [itex]{Q_k(0)\neq 0}[/itex].

We will obtain a contradiction by identifying a [itex]{k}[/itex] such that [itex]{Q_k}[/itex] is identically [itex]{0}[/itex].

Let [itex]{r_{0,n} = (b^{n - 1})/(a^{n - 1})}[/itex] for [itex]{n>0}[/itex].

By assumption [itex]{r_{0,n}}[/itex] is an integer.

For [itex]{k \geq 0}[/itex] define [itex]{r_{k+1,n}}[/itex] recursively by

[itex]{r_{k+1,n} = a^{k+1}r_{k,n+1} - br_{k,n}}[/itex]

Let [itex]{p_0 = 1}[/itex] and:

[itex]{{p_{k+1} = b(1 - a^{k+1} )p_k}}[/itex]

By induction on [itex]{k}[/itex] it follows for [itex]{n \geq 1}[/itex] and [itex]{k \geq 0}[/itex] that

[itex]{r_{k,n} = [b^np_k + Q_k(a^n) ]/[(a^{n+k} - 1)(a^{n+k-1} - 1)...(a^n - 1)]}[/itex]

Now fix [itex]{k}[/itex] so that [itex] a^k < b < a^{k+1} [/itex] . Since

[itex]{(a^n - 1)(a^{n+1} - 1)...(a^{n+k} - 1) = a^{n(k+1)} (1 - a^{-n} )(a - a^{-n} )...(a^k - a^{-n} ) \geq a^{n(k+1)} /2}[/itex]

we see that

[itex]{|r_{k,n}| \leq |b^np_k + Q_k(a^n)|/[a^{n(k+1)} /2] \leq 2( |p_k|(b/a^{k+1})^n + |Q_k(a^n)|/(a^n )^{k+1} )\;\;(*)}[/itex]

[itex]{Q_{k+1}(x) = a^{k+1}(x-1)Q_k(bx)-b(a^{k+1}x-1)Q_k(x)}[/itex] for [itex]{k \geq 0}[/itex].

Observe that [itex]{Q_{k+1}(0) = (b - a^{k+1})Q_k(0)}[/itex]. Iterating this and employing [itex]{Q_0 = -1}[/itex] leads to

[itex]{Q_k(0) = -(b - a^k )(b - a^{k-1} )...(b - a)}[/itex].

Assume that [itex]{b\neq a^j}[/itex] for every non-negative integer [itex]{j}[/itex], so that [itex]{Q_k(0)\neq 0}[/itex].

We will obtain a contradiction by identifying a [itex]{k}[/itex] such that [itex]{Q_k}[/itex] is identically [itex]{0}[/itex].

Let [itex]{r_{0,n} = (b^{n - 1})/(a^{n - 1})}[/itex] for [itex]{n>0}[/itex].

By assumption [itex]{r_{0,n}}[/itex] is an integer.

For [itex]{k \geq 0}[/itex] define [itex]{r_{k+1,n}}[/itex] recursively by

[itex]{r_{k+1,n} = a^{k+1}r_{k,n+1} - br_{k,n}}[/itex]

Let [itex]{p_0 = 1}[/itex] and:

[itex]{{p_{k+1} = b(1 - a^{k+1} )p_k}}[/itex]

By induction on [itex]{k}[/itex] it follows for [itex]{n \geq 1}[/itex] and [itex]{k \geq 0}[/itex] that

[itex]{r_{k,n} = [b^np_k + Q_k(a^n) ]/[(a^{n+k} - 1)(a^{n+k-1} - 1)...(a^n - 1)]}[/itex]

Now fix [itex]{k}[/itex] so that [itex] a^k < b < a^{k+1} [/itex] . Since

[itex]{(a^n - 1)(a^{n+1} - 1)...(a^{n+k} - 1) = a^{n(k+1)} (1 - a^{-n} )(a - a^{-n} )...(a^k - a^{-n} ) \geq a^{n(k+1)} /2}[/itex]

we see that

[itex]{|r_{k,n}| \leq |b^np_k + Q_k(a^n)|/[a^{n(k+1)} /2] \leq 2( |p_k|(b/a^{k+1})^n + |Q_k(a^n)|/(a^n )^{k+1} )\;\;(*)}[/itex]

Last edited:

- #31

- 330

- 3

when [itex]{n}[/itex] is sufficiently large. Thus [itex]{r_{k,n} = 0}[/itex] for large [itex]{n}[/itex], since it is an integer.

For all large [itex]{n}[/itex], this yields

[itex]{b^n p_k + Q_k(a^n) = 0}[/itex] and thus [itex]{p_k(b/a^k )^n + Q_k(a^n) /(a^n )^k = 0}[/itex].

This forces [itex]{p_k = 0}[/itex], since otherwise the left side is unbounded as [itex]{n\rightarrow +\infty}[/itex].

We now conclude that [itex]{Q_k(a^n) = 0}[/itex] for all [itex]{n}[/itex] and thus [itex]{Q_k}[/itex] is the zero polynomial

and we are done.

- #32

- 330

- 3

Define a sequence [itex]{(Q_k)}[/itex] of polynomials with [itex]{deg(Q_k) \leq k}[/itex] by [itex]{Q_0 = -1}[/itex], and [itex]{Q_{k+1}(x) = a^{k+1}(x-1)Q_k(ax)-b(a^{k+1}x-1)Q_k(x)}[/itex] for [itex]{k \geq 0}[/itex].

Observe that [itex]{Q_{k+1}(0) = (b - a^{k+1})Q_k(0)}[/itex]. Iterating this and employing [itex]{Q_0 = -1}[/itex] leads to [itex]{Q_k(0) = -(b - a^k )(b - a^{k-1} )...(b - a)}[/itex].

Assume that [itex]{b\neq a^j}[/itex] for every non-negative integer [itex]{j}[/itex], so that [itex]{Q_k(0)\neq 0}[/itex]. We will obtain a contradiction by identifying a [itex]{k}[/itex] such that [itex]{Q_k}[/itex] is identically [itex]{0}[/itex].

Let [itex]{r_{0,n} = (b^n - 1)/(a^n - 1)}[/itex] for [itex]{n>0}[/itex]. By assumption [itex]{r_{0,n}}[/itex] is an integer.

For [itex]{k\geq 0}[/itex] define [itex]{r_{k+1,n}}[/itex] recursively by [itex]{r_{k+1,n}=a^{k+1}r_{k,n+1}-br_{k,n}}[/itex].

Let [itex]{p_0=1}[/itex] and [itex]{{p_{k+1} = b(1 - a^{k+1} )p_k}}[/itex].

By induction on [itex]{k}[/itex] it follows for [itex]{n \geq 1}[/itex] and [itex]{k \geq 0}[/itex] that

[itex]{r_{k,n}=[b^np_k + Q_k(a^n) ]/[(a^{n+k} - 1)(a^{n+k-1} - 1)...(a^n - 1)]}[/itex]

Now fix [itex]{k}[/itex] so that [itex]a^k<b<a^{k+1}[/itex]. Since

[itex](a^n-1)(a^{n+1}-1)\dots(a^{n+k}-1)=a^{n(k+1)}(1-a^{-n})(a-a^{-n})\dots(a^k-a^{-n})\geq a^{n(k+1)}/2[/itex]

we see that

[itex]|r_{k,n}|\leq |b^np_k+Q_k(a^n)|/[a^{n(k+1)}/2]\leq 2(|p_k|(b/a^{k+1})^n+|Q_k(a^n)|/(a^n )^{k+1})\;\;(*)[/itex]

Since [itex]{b < a^{k+1}}[/itex] and [itex]{deg(Q_k) < k+1}[/itex], the rightmost expression in (*) is bounded above by [itex]{1}[/itex] when [itex]{n}[/itex] is sufficiently large. Thus [itex]{r_{k,n} = 0}[/itex] for large [itex]{n}[/itex], since it is an integer.

For all large [itex]{n}[/itex], this yields [itex]{b^n p_k + Q_k(a^n) = 0}[/itex] and thus [itex]{p_k(b/a^k )^n + Q_k(a^n) /(a^n )^k = 0}[/itex].

This forces [itex]{p_k = 0}[/itex], since otherwise the left side is unbounded as [itex]{n\rightarrow +\infty}[/itex]. We now conclude that [itex]{Q_k(a^n) = 0}[/itex] for all [itex]{n}[/itex] and thus [itex]{Q_k}[/itex] is the zero polynomial and we are done.