Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given $b$ and $n$, I need to efficiently enumerate all integers $x$ (and $k$) such that:

$$x^2-x=kb^{n}$$ $$x∈⟦b^{n-1},b^n-1⟧$$

I simply don't know how to proceed. I tried the naive quadratic formula but then I have to enumerate all $k$ such that $∃δ~(δ-1)(δ+1) = 4kb^n$ which is still hard for me.

The number $b$ can be prime or composite. I am interested in both cases.

To be honest, $b=14$ is enough.

share|improve this question
add comment

2 Answers

up vote 1 down vote accepted

I assume $b>1$ otherwise there's no interval for $x$.

Let $b=\prod p_i^{a_i}$ be the prime factorization of $b$ and factor the left side to get $$ x(x-1) = k\prod p_i^{na_i} $$ If $p_i \mid x$ then $p_i \nmid x-1$ so we must have $p_i^{na_i}\mid x$. Likewise, if $p_j \mid x-1$ then $p_j^{na_j} \mid x-1$.

So some subset $S_x$ of $\{p_i\}$ are divisors of $x$ and the rest must be divisors of $x-1$, each appearing to the highest power that's in $b^n$. Thus we must satisfy $$ x \equiv 0 \pmod{\prod_{p_i\in S_x} p_i^{na_i}} $$ and $$ x \equiv 1 \pmod{\prod_{p_i\not\in S_x} p_i^{na_i}} $$ Using the Chinese remainder theorem there is exactly one $0\le x < b^n$ that satisfies these both. We just need to find it and check if it's in the interval $b^{n-1}\le x < b^n$ to see if it qualifies.

Considering all possible subsets $S_x$ we can enumerate all solutions. If there are $M$ distinct primes that divide $b$ then there are $2^M$ possible $S_x$ so $2^M$ potential solutions. However, if $S_x$ contains all of the primes then $x=0$ is our candidate, which is never in the desired interval, and if $S_x=\emptyset$ then $x=1$ is our candidate which is a solution iff $n=1$.

In particular, if $b$ is prime, then there are only two possible $S_x$, either $\emptyset$ or $\{b\}$, which give $(x,k)=(1,0)$ if $n=1$ and no solution if $n>1$.

If $b=pq$ for primes $p,q$ (includes the case $b=14$) then there are 4 subsets, two of which are $\emptyset$ and $\{p,q\}$, which again only give $(x,k)=(1,0)$ if $n=1$. So there are at most two non-trivial solutions.

share|improve this answer
Thanks, notably for the fact that there is at most one solution for each $S_x$. –  jmad Jun 5 '12 at 12:57
add comment


$x$ and $x-1$ are relatively prime therefore if $b$ is prime then $b^n|x$ or $b^n|x-1$, therefore there are no solutions in the range $[b^{n-1},b^n-1]$. If $b=14$ then $2^n|x$ and $7^n|x-1$, (exclusive) or $2^n|x-1$ and $7^n|x$, (exclusive) or $14^n|x$ (exclusive) or $14^n|x-1$.

A brute force approach is to find all $b$ such that $7^nb=1 \mod 2^n$ and $c$ such that $7^nc=-1 \mod 2^n$ and let $x=7^n(b+d.2^n)$ or $x=7^n(c+d.2^n)+1$ for any $d\geq0$ for which $x\in [b^{n-1},b^n-1]$.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.