# Some help with a number theory problem

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.
Oops! Back to the drawing board. Thanks for the correction.

Petek

Well, I gave up and searched online for information about this problem. If you Google for the exact text of the first post in this thread, the first result is this thread and the second result points to another forum in which the exact same question was posed back in 2004. It turns out that the solution to this problem is surprisingly difficult. The problem was posed in the AMM, with a solution provided by the proposer. The thread in the other forum has lots of discussion. I'll post a link upon request.

Petek

I'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

$(\exists k\in N)b=a^k\implies(\forall n\in N)a^n-1|b^n-1$

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.
I agree that Mathman and I were probably reading the problem incorrectly, because given that

$(\forall n\in N)a^n-1|b^n-1$ it is difficult to show that a|b much less that
$$b = a^k$$ While the converse is easily verified.

As I suspected this problem turned out to be rather more than a relaxing Sunday afternoon puzzle.

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.

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

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

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

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

By assumption ${r_{0,n}}$ is an integer.

For ${k \geq 0}$ define ${r_{k+1,n}}$ recursively by

${r_{k+1,n} = a^{k+1}r_{k,n+1} - br_{k,n}}$

Let ${p_0 = 1}$ and:

${{p_{k+1} = b(1 - a^{k+1} )p_k}}$

By induction on ${k}$ it follows for ${n \geq 1}$ and ${k \geq 0}$ that

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

Now fix ${k}$ so that $a^k < b < a^{k+1}$ . Since

${(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}$
we see that

${|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} )\;\;(*)}$

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

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

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

I have noticed a couple of misprints in the previous two posts. Unfortunately I can no longer edit them. No one has pointed out the misprints so hopefully they haven't caused too much confusion, but I have corrected them and combined the posts below.

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

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

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

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

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

Let ${p_0=1}$ and ${{p_{k+1} = b(1 - a^{k+1} )p_k}}$.

By induction on ${k}$ it follows for ${n \geq 1}$ and ${k \geq 0}$ that

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

Now fix ${k}$ so that $a^k<b<a^{k+1}$. Since

$(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$

we see that

$|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})\;\;(*)$

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

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

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