let $ k=b^2$: $ b^2|b-a^n_k \Rightarrow a^n_k=b(bx+1)$ but $ gcd(b , bx+1)=1$ therefore $ b=A^n$ for some integer $ A$.

orl wrote: Let $ b,n > 1$ be integers. Suppose that for each $ k > 1$ there exists an integer $ a_k$ such that $ b - a^n_k$ is divisible by $ k.$ Prove that $ b = A^n$ for some integer $ A.$ Author: unknown author, Canada

It may be interesting to know that if $ 8 \nmid n$, then it suffices to consider primes $ k$ only. More generally (more or less the Grunwald-Wang-theorem): Let $ n,b$ be a integers, $ n > 0$. If for all primes $ p$ there is an $ a_p$ such that $ p|b - a_p^n$, then the following holds: a) If $ 8 \nmid n$, then $ b = a^n$ for some integer $ a$. b) If $ 8|n$ then $ b = a^{\frac n2}$ for some integer $ a$. This was posted and partially solved before. For those knowing algebraic number theory, this can be generalised even more (those don't knowing algebraic number theory, please stop here ): Let $ K$ be a number field, $ b \in K$, $ n = m \cdot 2^s > 0$ an integer ($ m$ odd). If $ b$ is a $ n$-th power in all but finitely many completions $ K_v$ (where $ v$ runs through the primes of $ K$), then: a) If $ K[\zeta_{2^s}]|K$ is cyclic, then $ b = a^n$ for some $ a \in K$. b) Otherwise, $ b = a^{\frac n2}$ for some $ a \in K$. Proving this is some work in (pre)global class field theory (the main step being to show that if $ L|K$ has all but finitely many primes totally split, then $ K = L$).

Note that a) indeed requires $ 8\nmid n$: Let $ b = 16$, $ n = 8$. We have $ x^8 - 16 = (x^2 - 2)(x^2 + 2)(x^2 - 2x + 2)(x^2 + 2x + 2)$. Of course one of the numbers $ - 1, - 2,2$ is a quadratic residue $ \mod p$. It means that for every prime $ p$ one of the equations $ (x + 1)^2 + 1 = 0$, $ x^2 + 2 = 0$, $ x^2 - 2 = 0$ has a solution $ \mod p$ and so does $ x^8 - 16 = 0$. And $ 16\neq A^8$. [Moderator edit: See also http://www.mathlinks.ro/viewtopic.php?t=4874 for this counterexample.]

I also didn't see it at first, but $ p$ is not necessarily prime. Using this, it gets really easy (using valuations). But you will have a lot of fun to show that if we require that $ 8 \nmid n$, then we need only to look at primes $ p$.

Solution Assume that there is no $A$ such that $b=A^n$. Then there must exist a prime number $p$ such that, if $p^a \| b$, then $n \not | a$. Assume now that $mn < a < (m+1)n$ for some $m \in \mathbb{N}$. Taking $k=p^{(m+1)n}$ yields that \[b \equiv a_{k}^n \pmod{p^{(m+1)n}}\] Which implies that $p^{a} |a_{k}^n$ and, since $a_{k}^n$ is a perfect $n$th power, that $p^{(m+1)n} | a_{k}^n$. Hence $b \equiv 0 \pmod{p^{(m+1)n}}$ and $n|a$ which is a contradiction. $\blacksquare$

Does anyone have a solition with looking at a prime divisor of $n$?

ali666 wrote: let $ k=b^2$: $ b^2|b-a^n_k \Rightarrow a^n_k=b(bx+1)$ but $ gcd(b , bx+1)=1$ therefore $ b=A^n$ for some integer $ A$. Can you explain more detailed?

A different Solution write $b$ as $b=B^n \times j$ where $gcd(B,j)=1$ now if $j=1$ then we are done. Suppose $j$ is not equal to $1$ then consider a prime which divides $j$ and consider $k=p^n$ now since $p|j$ then $p|a_k$ this implies $p^n|{a_k}^n$ implies $p^n|j$ but then it follows that $p^{n}|B$ by definition of B. So this a contradiction and hence we are infact done.

hehe my solution if exist p: Vp(b)=r.n+s ( 0<s<n) then choose k=p^(r(n+1)) then Vp(ak) > r then Vp(ak) >= r+1 then Vp(b-ak^n) = rn+s < r(n+1)

in this problem b and n are not fixed right? they can vary, just like k?

Let $b=p^{an+c}l$ where p is prime and $(p,l)=1$ and $1\leq c\leq n-1$. Let $k=p^{an+n}$, $k|b-a_k^n,=>v_p(k)\leq v_p(b-a_k^n)<=>an+n\leq v_p(b-a_k^n)=min\left\{v_p(b),v_p(a_k^n)\right\}\leq an+c$ . Which is plainly a contradiction, thus $b=m^n$

vjdjmathaddict wrote: A different Solution write $b$ as $b=B^n \times j$ where $gcd(B,j)=1$ now if $j=1$ then we are done. Suppose $j$ is not equal to $1$ then consider a prime which divides $j$ and consider $k=p^n$ now since $p|j$ then $p|a_k$ this implies $p^n|{a_k}^n$ implies $p^n|j$ but then it follows that $p^{n}|B$ by definition of B. So this a contradiction and hence we are infact done. Wrong: If you take B to be the max n-th power that divides b, then not necessarily GCD(B,j)=1, but if you take by construction that GCD(B,j) , B and j are clearly unique, but not necessarily all n-th power that divides b go to B. Take for instanceb=(2^n)*(3^(n+1)), then B=2^n and j=3^(n+1) are the only air (B,j), but 3^n divides j, and therefore no contradiction

Nice problem. Hope, my solution is not the same as anyone else's $\rightarrow$. Suppose there exists a prime $\text{p}$ such that $b = p^{\alpha n + e_0}x , 1 \le e_0 < n$. Where, $\text{gcd} ( x,p)=1$ and $\text{v}_p(b)$ is not congruent to $0 \pmod{n}$. Now, let $k= p^{n (\alpha +1)}$. Now, $\text{v}_p(b-a_k^n)$ must be greater than or equal to $\text{v}_p(k) = n(\alpha + 1)$. $\blacksquare$ Case 1.: $\text{v}_p(a_k) \le \alpha$. $\implies \text{v}_p(b)$$ \ge \text{v}_p(a_k^n)$$ \implies \text{v}_p(b-a_k^n) =\text{v}_p(a_k^n) \le \alpha $ contradiction. $\blacksquare$ Case 2.: $\text{v}_p(a_k) \ge \alpha +1$. $\implies \text{v}_p(a_k^n) \ge \text{v}_p(b) \implies \text{v}_p(b-a_k^n) = \text{v}_p(b) < n(\alpha + 1)$ contradiction. Henceforth, we conclude that $e_0 \equiv$$ 0 \pmod {n} \implies b=m^n$.

Take $p=$prime,$p\mid b$,$v_p(b)=\alpha$,$b=p^{\alpha}c$ $gcd(p,c)=1$.Take $k=p^{\alpha+1}$ $p^{\alpha+1}\mid p^{\alpha}c-a^n$,take $v_p(a)=\beta$ so $\alpha\le\beta n$.If $\beta n>\alpha$ then $p\mid c$ false! We must have $\alpha=\beta n$,but this is true for any prime that divides n so $b=A^n$ for some $A$

$b = p^{nq + r}b_1$ where $(b_1,p) = 1$. If $r \neq 0$, choose $p^{nq +r + 1} | p^{nq + r}b_1 - a^n \implies p^{nq + r} | p^{nq +r}b_1 - a^n$ but this means $p^{nq + r + 1} | a^n$ and therefore $p^{nq + r + 1} | b$, a contradiction.

ShaftDraftKiller wrote:

Well, you exactly showed if $p$, prime, divides $b$, so $p^n$ also divides $b$. But, that doesn't mean $b=A^n$ for some $A$. Maybe, you can do something like that, but with $v_p(b)$. Greetings ! ! !

Well, it looks like I solved a special case of this problem in this thread, so I might as well make the necessary changes and port it over Throughout this proof, let $\nu_p(m)$ denote the largest integer $t$ such that $p^t$ divides $m$. Suppose, by way of contradiction, that $b$ is not a perfect $n^{\text{th}}$ power. Pick a prime divisor $p$ of $b$ for which $\ell := \nu_p(b)$ is not divisible by $n$; such a $p$ must exist. Now choose $k = p^{\ell + 1}$, and suppose there exists $n$ such that $b\equiv a_k^n\pmod{p^{\ell + 1}}$. Certainly, $b\equiv a_k^n\pmod p$, so $a_k^n$ is divisible by $p$; in turn, $a_k$ is divisible by $p$. But now by assumption $\nu_p(b) = \ell$ cannot equal $\nu_p(a_k^n) = n\nu_p(a_k)$ (because then it'd be divisible by $n$!), so \[ \nu_p(a_k^n - b) = \min(\nu_p(a_k^n),\nu_p(b)) \leq \nu_p(b) = \ell. \]Hence $a_k^n - b$ is not divisible by $p^{\ell + 1}$, which is a contradiction. Since $a_k$ was arbitrary, we deduce that $b$ is not an $n^{\text{th}}$ power modulo $p^{\ell + 1}$, which contradicts the problem statement. Thus our assumption was wrong and $b=A^n$ for some $A$.

Suppose not. Then there exists $p$ such that $n\nmid \nu_p(b)$. Let $\nu_p(b) = t$. Setting $k = p^{t+1}$ gives $\nu_p(c^n) = n\nu_p(c) = \nu_p(b)$ for some $c$, which is impossible.

Take $k=b^2$ so that $a_{b^2}^n \equiv b \pmod{b^2}$. Then, $a_{b^2}^n = b(bj+1)$ for some nonnegative integer $j$, but $(b, bj+1)=1$, so $b=A^n$ for some integer $A$, as desired.

The main idea of the problem is the assertion $k=b^2$. Then for every prime $p$ dividing $b$, we clearly need $n\mid\nu_p(b)$. $\blacksquare$

$k=b^2$ implies that $a_{b^2}^n = b(1-cb)$ for some $c$. However, for all $p \mid b$, $\nu_p(b(1-cb)) = \nu_p(b)$ and we're done since $n \mid \nu_p(b(1-cb))$. $\square$

Another one liner? The assertion $$k=b^2\implies a_{b^2}^n = b(1-kb)\implies n\cdot v_pa_{b^2}=v_pa_{b^2}^n=v_p(b(1-kb))=v_pb\forall p\mid b\implies n\mid v_pb,$$which is just the problem rephrased since each exponent of a prime in b must be a multiple of n. $\blacksquare$

Consider a $k$ such that for every prime $p$ dividing $b, \nu_p(k)>\nu_p(b)$ (here $k=b^2$ works easily), note that $k\mid b-a_k^n$, if $\nu_p(b)=n\nu_p(a_k)$ we are done, so assume the contrary then \[\nu_p\left(b-a_k^n\right)=\min\{\nu_p(b),n\nu_p(a_k)\}>\nu_p(k)\]Which is impossible as $\nu_p(b)<\nu_p(k)$

Suppose $b = \prod p_i^{e_i}$, and construct $k = \prod p_i^{f_i}$ such that $f_i > e_i$ for all $i$. We must have \[a^n \equiv \prod p_i^{e_i} \pmod k,\] so for all $i$, we have \[v_{p_i}(a^n) = v_{p_i}(b) = e_i \implies n \mid e_i,\] which gives the desired. $\blacksquare$

For any $p \mid b$, we want to prove that $n \mid \nu_p(b)$. For any $p \mid b$, consider $k$ st $\nu_p(k) > \nu_p(b)$, then $\nu_p(b-a_k^n) > \nu_p(b)$. If $\nu_p(b) \neq \nu_p(a_k^n)$ we have $\min\{\nu_p(b), \nu_p(a_k^n)\}>\nu_p(b)$ which is impossible. Thus $\nu_p(b)=n \nu_p(a_k) \implies n \mid \nu_p(b)$.

I denote the number mapped to $k$ here by $r$ for the sake of fast writing : we have : $b-r^{n}=xk$ then $r^{n}=b(1-\frac{xk}{b})$ Then it's enough to take a good $k$ to make $gcd(b,1-\frac{xk}{b})=1$ Take $k=b^{t}$ where $t$ is a positive integer greater than 2

Posting for storage. Suppose there exists $p\mid b$ with $\nu_p(b) = a$ such that $(t-1)n < a < tn$. Take $k = p^{tn}$ to get that $p^{tn} \mid b - a_{k}^{n}$ so clearly $p\mid a_{k}$. Let $\nu_p(a_{k})=b$ if $b < t-1$ we have that $\nu_p(b-a_{k}) \le (t-1)n$ - false. If $b \ge t$ we have that $\nu_p(b-a_{k}) = a \le tn$ - false. So there isnt such prime and hence $b = A^{n}$.

Nice problem, didn't see the really slick choice for $k$ but this also works. Consider a prime $p \mid b$ such that $\nu_p(b) = nq+r$ for positive integers $q$ and $0<r<n$. Now, we have 3 possible cases. Then, by the given hypothesis, there exists a positive integer $a$ such that $p^{nq+r+1} \mid b-a^n$. We have then three possible cases. Case 1 : $\nu_p(b) > \nu_p(a^n)$. Then, $\nu_p(b-a^n)=\nu_p(a^n)=n\nu_p(a)$. Since $\nu_p(a^n) < \nu_p(b)=nq+r < n(q+1)$, so $\nu_p(a^n) \le nq < nq+r+1$, so the desired divisibility does not hold. Case 2 : $\nu_p(b) < \nu_p(a^n)$. Then, $\nu_p(b-a^n)=\nu_p(b) = nq+r < nq+r+1$, so again the desired divisibility cannot hold. Case 3 : $\nu_p(b)=\nu_p(a^n)=n\nu_p(a)$ which is a multiple of $n$. Thus, $n\mid \nu_p(b)=nq+r$, which is a clear contradiction based on our choice of $r$. Thus, there cannot exist such a prime $p$ implying that for all primes $p\mid b$, $n\mid \nu_p(b)$, i.e $b$ is a perfect $n^{\text{th}}$ power and thus can be written in the form $b=A^n$ for some positive integer $A$.

We prove that each individual prime factor of $b$ has exponent divisible by $n$. Assume some prime factor $p$ doesn't, let it have exponent $xn + c$ for $c < n$, then taking $k = p^{n(c + 1)}$ finishes, as all $n$th power residues modulo that value of $k$ should $\nu_p$ divisible by $n$.

Nice

OG!