1
$\begingroup$

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.

2 Answers 2

1

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.

  • 0
    Thanks, notably for the fact that there is at most one solution for each $S_x$.2012-06-05
2

$x(x-1)=kb^n$

$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]$.