Prove that if $ a^n \mid b^n $ then $a\mid b$ (without use of GCD and factorization theorem).

  • 10
    $\begingroup$ Welcome. I don't know how you talk at home or with your friends, but here we enjoy a friendlier tone. In particular, some of us don't like being ordered to prove something, when being asked for help. Please phrase your question(s) a bit more politely. Thank you. $\endgroup$ – Alex B. Feb 20 '13 at 11:59
  • 2
    $\begingroup$ @AlexB. I'm so sorry about this subject for all visitors. I don't know about relationship in writing in in this site. before this comment, I think the question must be declared without exta subject as frank subject, I will do this in next topic and answer and respect to reader more and more.tnx $\endgroup$ – agustin Feb 21 '13 at 17:53

If $a^n|b^n$, then $b^n/a^n=(\frac{b}{a})^n$ is an integer. Since $\frac{b}{a}$ is rational, this implies that $\frac{b}{a}$ is an ordinary integer, by this theorem.
notice that the use of the theorem is suggested by @CalvinLin .

  • $\begingroup$ Without any use of GCD nor factorisation theorems. $\endgroup$ – awllower Feb 20 '13 at 12:01
  • 1
    $\begingroup$ OK, provided OP is familiar with algebraic integers (and providing you can develop their theory without GCD and factorization). $\endgroup$ – Gerry Myerson Feb 20 '13 at 12:01
  • 1
    $\begingroup$ You can just use the rational (integer) root theorem for the second line. $\endgroup$ – Calvin Lin Feb 20 '13 at 12:24
  • $\begingroup$ @CalvinLin Thanks for pointing out this! ^^ $\endgroup$ – awllower Feb 20 '13 at 12:26
  • 1
    $\begingroup$ @CalvinLin This use of the Rational Root Test can be viewed more generally as the fact the GCD domains are integrally closed. More generally these and related proofs (e.g. irrationality of radicals) can be done very elegantly by employing Dedekind's notion of conductor ideals (discussed in some of my prior posts). $\endgroup$ – Bill Dubuque Mar 13 '14 at 15:04

Suppose that $x=\frac pq$ where $p$ and $q$ are relatively prime; that is, there are $a$ and $b$ so that $$ ap+bq=1\tag{1} $$ Suppose that there are integers $c_k$ so that $$ x^n+\sum_{k=0}^{n-1}c_kx^k=0\tag{2} $$ Equation $(1)$ says $x=\frac{1-bq}{aq}$, and substituting into $(2)$ yields $$ \begin{align} 0 &=\left(\frac{1-bq}{aq}\right)^n+\sum_{k=0}^{n-1}c_k\left(\frac{1-bq}{aq}\right)^k\\ &=\frac1{(aq)^n} +\sum_{k=0}^{n-1}\binom{n}{k}\frac1{(aq)^k}\left(-\frac ba\right)^{n-k} +\sum_{k=0}^{n-1}c_k\left(\frac{1-bq}{aq}\right)^k\tag{3} \end{align} $$ Multiply $(3)$ by $a^nq^{n-1}$ and move $\frac1q$ to the left side $$ \frac1q =b\sum_{k=0}^{n-1}\binom{n}{k}(-bq)^{n-k-1} -a\sum_{k=0}^{n-1}c_k(1-bq)^k(aq)^{n-k-1}\tag{4} $$ Everything on the right side of $(4)$ is an integer, so $\frac1q$ must also be an integer. Thus, $x=\frac pq$ is also an integer.

Therefore, any rational number $x$ which satisfies $(2)$ with integer $c_k$ must be an integer.

Finish off as awllower does. Let $x=\frac ba$. We are given that $x^n-k=0$ for some integer $k$. The argument above says that $x=\frac ba$ is an integer.

  • $\begingroup$ Intricate discussion of rational numbers. +1 Well done. $\endgroup$ – awllower Feb 20 '13 at 17:00
  • $\begingroup$ why we have for $({\frac{a}{b}})^n: x^n+\sum_{k=0}^{n-1}c_kx^k=0$? $\endgroup$ – agustin Feb 23 '13 at 19:41
  • $\begingroup$ @agustin: We are given that $a^n\mid b^n$ which means that $\left(\frac ba\right)^n\in\mathbb{Z}$, or equivalently, there is a $k\in\mathbb{Z}$ so that $$ \left(\frac ba\right)^n-k=0\tag{$\ast$} $$ Letting $x=\frac ba$, we see that $(\ast)$ is in the form of $(2)$, where $x$ is rational. The result above then says that $x=\frac ba$ is an integer. Thus, $a\mid b$. $\endgroup$ – robjohn Feb 23 '13 at 21:04
  • $\begingroup$ Simpler: Bezout $\rm\color{#c00}{lead}$ term only. Let $\ x=\frac{p}q,\,\ ap\!+\!qb=1,\,$ and $\,\ 0\,=\,x^{n+1}+c_n x^n+\,\cdots\qquad$ $\tag*{}$ Note $\,(aq)^n \color{#c00}{x^{n+1}}\!=x(aqx)^n=x(ap)^n = x(1\!-\!qb)^n=x(1\!-\!qk)=\color{#c00}{x\!-\!pk},\,$ for some $\,k\in\Bbb Z\qquad$ $\tag*{}$ Also $\ (aq)^n (\color{#0a0}{c_n x^n + c_{n-1}x^{n-1}+\cdots)\, =\, m}\in\Bbb Z\ \ $ by $\ \ q^i x^i=(qx)^i=p^i\in\Bbb Z$ $\tag*{}$ $\,0=\,(aq)^n(\color{#c00}{x^{n+1}}+\color{#0a0}{c_n x^n+\cdots})\,=\,\color{#c00}{x-pk}\color{#0a0}{+m}\,\Rightarrow\, x = pk-m\in \Bbb Z\ \ \ {\bf QED}$ $\tag*{}$ $\endgroup$ – Bill Dubuque Mar 15 '14 at 2:54
  • $\begingroup$ The Rational Root Test can be proved without Bezout, e.g. see here for a 2-line proof using Euclid's Lemma. $\endgroup$ – Bill Dubuque Feb 25 '15 at 23:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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