Integer a_k such that b - a^n_k is divisible by k

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

orl

3647 posts

orl

#1 h Jul 13, 2008, 1:41 PM • 7 Y

Y by narutomath96, raknum007, itslumi, HWenslawski, Adventure10, Mango247, NicoN9

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: Dan Brown, Canada

This post has been edited 3 times. Last edited by v_Enhance, Jan 18, 2016, 2:13 AM
Reason: Fix obsolete TeX

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ali666

352 posts

ali666

#2 h Jul 13, 2008, 1:55 PM • 66 Y

Y by narutomath96, anantmudgal09, PRO2000, Ankoganit, bgn, rafayaashary1, tarzanjunior, Problem_Penetrator, Swag00, jt314, Goodhao, Gems98, Akeyla, pavel kozlov, othman, Wizard_32, pablock, vsathiam, Pluto1708, Polynom_Efendi, Mario_Leopoldo, Illuzion, djmathman, Lifefunction, Severus, Keith50, Cindy.tw, mathleticguyyy, mijail, snakeaid, vsamc, lneis1, myh2910, rama1728, HWenslawski, Adventure10, PRMOisTheHardestExam, HappyMathEducation, green_leaf, lazizbek42, megarnie, WGM_RhuanSA, Mathlover_1, Perceval, Kimchiks926, soelinhtetptn20204, Quidditch, mistakesinsolutions, two_steps, starchan, Mango247, eduD_looC, vrondoS, kiyoras_2001, Sedro, White_Tiger_Wolf, ehuseyinyigit, aidan0626, farhad.fritl, NicoN9, H_Taken, ZZzzyy, and 4 other users

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

The QuattoMaster 6000

1184 posts

The QuattoMaster 6000

#3 h Oct 5, 2008, 1:10 AM • 4 Y

Y by narutomath96, vsathiam, Adventure10, Mango247

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

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ZetaX

7579 posts

ZetaX

#4 h Oct 5, 2008, 1:32 AM • 5 Y

Y by pavel kozlov, AlastorMoody, Cindy.tw, Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mazur89

19 posts

mazur89

#5 h Feb 12, 2009, 3:10 PM • 1 Y

Y by Adventure10

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ZetaX

7579 posts

ZetaX

#6 h Feb 12, 2009, 3:20 PM • 1 Y

Y by Adventure10

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

SnowEverywhere

801 posts

SnowEverywhere

#7 h Mar 9, 2011, 2:31 AM • 5 Y

Y by narutomath96, raknum007, Illuzion, RaMathuzen, Adventure10

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Mathatator

75 posts

Mathatator

#8 h Nov 7, 2016, 3:04 PM • 1 Y

Y by Adventure10

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Anar24

475 posts

Anar24

#9 h Nov 25, 2016, 1:20 PM • 2 Y

Y by Adventure10, Mango247

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?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

vjdjmathaddict

502 posts

vjdjmathaddict

#10 h Oct 14, 2017, 2:33 PM • 3 Y

Y by lneis1, Adventure10, Mango247

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.

This post has been edited 2 times. Last edited by vjdjmathaddict, Oct 14, 2017, 2:57 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lebathanh

464 posts

lebathanh

#12 h Dec 3, 2017, 8:16 AM • 2 Y

Y by Adventure10, Mango247

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)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

maxo

498 posts

maxo

#13 h Dec 28, 2017, 6:48 AM • 2 Y

Y by Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Leartia

93 posts

Leartia

#14 h Feb 21, 2018, 1:38 AM • 2 Y

Y by Wictro, Adventure10

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Samusasuke

30 posts

Samusasuke

#15 h Mar 18, 2018, 4:57 AM • 2 Y

Y by Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

e_plus_pi

756 posts

e_plus_pi

#16 h May 26, 2018, 7:49 AM • 3 Y

Y by Satops, Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

BorisAngelov1

15 posts

BorisAngelov1

#60 h Apr 29, 2024, 9:52 AM • 1 Y

Y by topologicalsort

maybe not a fakesolve

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

shendrew7

796 posts

shendrew7

#61 h Jun 4, 2024, 9:54 PM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

de-Kirschbaum

201 posts

de-Kirschbaum

#62 h Jul 11, 2024, 2:36 AM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

alba_tross1867

44 posts

alba_tross1867

#63 h Aug 5, 2024, 2:19 PM

Y by

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

This post has been edited 1 time. Last edited by alba_tross1867, Aug 5, 2024, 7:08 PM
Reason: Typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

SomeonesPenguin

129 posts

SomeonesPenguin

#64 h Aug 5, 2024, 2:54 PM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cursed_tangent1434

634 posts

cursed_tangent1434

#65 h Aug 14, 2024, 9:33 AM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ezpotd

1272 posts

ezpotd

#66 h Oct 19, 2024, 11:18 PM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lelouchvigeo

183 posts

lelouchvigeo

#68 h Dec 10, 2024, 6:44 AM

Y by

Nice
Sol

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

sansgankrsngupta

143 posts

sansgankrsngupta

#69 h Feb 15, 2025, 5:55 AM

Y by

OG!
one or 2 liner, is it a fakesolve?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Ilikeminecraft

651 posts

Ilikeminecraft

#70 h Mar 7, 2025, 9:16 PM

Y by

Let $p$ be any prime, and $\ell = \nu_p(b).$ Pick $k = p^{\ell + 1}.$ This implies that $\nu_p(a_{k}^n) = \ell,$ so $n\mid \ell.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Mapism

19 posts

Mapism

#71 h Mar 10, 2025, 8:41 PM

Y by

$\forall l\ge 1,\ k=bl \implies a_{bl}^n=b(lm_l-1)$ for some $m_l\in \mathbb{Z}$ . Note for any $p\mid b,\ p\mid a_{bl}$ . If gcd $(b,lm_l+1)=1$ , we obtain for any $p\mid b,\ \nu_p(a_{bl}^n)=\nu_p(b(lm_l+1))=\nu_p(b) \implies n\nu_p(a_{bl})=\nu_p(b) \implies n\mid \nu_p(b)$ which is the desired result. Thus take any $b\mid l$ to guarantee gcd $(b,lm_l+1)=1$ , namely $l=b$ , and we're done.

This post has been edited 1 time. Last edited by Mapism, Mar 10, 2025, 8:43 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

OronSH

1745 posts

OronSH

#72 h Mar 13, 2025, 1:00 AM • 1 Y

Y by megarnie

Let $\nu_p(b)=c$ , so $k=p^{c+1}$ implies $\nu_p(a_k^n)=c\implies n\mid c$ as desired.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

shanelin-sigma

165 posts

shanelin-sigma

#75 h Apr 7, 2025, 6:55 AM

Y by

The original problem seemed to be easy because if $n\nmid \nu_p(b)$ for some prime $p$ , then we can just pick $k=p^{\nu_p(b)+1}$ and get a contradiction.
How about this version, can we also ensure that $b$ is a perfect n-power number?

07N2 Ex version wrote:

Let $b,n > 1$ be integers. Suppose that for each prime $p$ there exists an integer $a_p$ such that $b - a^n_p$ is divisible by $p$ . Is it true that there always exists an integer $A$ such that $b = A^n$ ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ZZzzyy

2 posts

ZZzzyy

#76 h Apr 23, 2025, 11:40 AM

Y by

Let $\nu_p(b) = x = qn + r > 1$ , we have $p^{x+1} = p^{qn + r + 1} \mid b + a_{p^{x+1}} ^n$ , as $p^{qn + r} \mid b \Rightarrow p^{qn+r} \mid a_{p^{x+1}}^n$ . Assume $r > 1$ , then $\nu_p(a_{p^{x+1}}) \geq q + 1$ , so $p^{qn+r+1} \mid a_{p^{x+1}}^n \Rightarrow p^{qn+r+1} \mid b$ , contradiction, so $r = 0$ , which shows $b = A^n$

This post has been edited 2 times. Last edited by ZZzzyy, Apr 23, 2025, 11:42 AM
Reason: error with argument

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Aiden-1089

293 posts

Aiden-1089

#77 h May 3, 2025, 4:51 AM

Y by

Assume $b$ is not a power of $n$ .
Consider some prime $p$ dividing $b$ such that $(\alpha-1) n < v_p(b)< \alpha n$ for some positive integer $\alpha$ .
Then choose $k=p^{\alpha n}$ , we would have $n \nmid v_p(b)=v_p(a_k^n)=n v_p(a_k)$ which is not possible.

Z K Y