Let $a,b,n \in \mathbb{N}.$ Prove that if $a^n \mid b^n$, then $a \mid b$.

$\textit{Proof.}$ Consider the prime factorizations for $a$ and $b$ as follows:

$$a=p_1 \cdots p_r, $$ $$b=q_1 \cdots q_s.$$

Where $q_i, p_j$ are all prime numbers. Observe that $p_k$ could be equal to $p_m$ for some $m≠k$, and similarly for $q$. (In other words, for simplicity I decided not to write $a=p_1^{\alpha_1} \cdots p_r^{\alpha_r}$).

Then, we have $$a^n=p_1^n \cdots p_r^n,$$ $$b^n=q_1^n \cdots q_s^n.$$

Note that the prime factors of $b$ are exactly the same prime factors of $b^n$, but each prime factor of $b^n$ is to the $n$-th power.

Since $a^n \mid b^n$, then $b^n=a^n \cdot q$ for some integer $q$, so that

$$b^n = p_1^n \cdots p_r^n \cdot q$$

If $p_i$ for some $i$ doesn't appear in the prime factors of $b$, then $p_i$ couldn't appear in the prime factors of $b^n$. Then, each $p_i$ appearing in $b^n$, will appear in $b$. Hence, $b=p_1 \cdots p_n \cdot p$ for some integer $p$. Then $b=ap$, as desired.

... $\textit{Q.E.D.}$??

  • 1
    $\begingroup$ The last step is that $p\mid b^n$ implies $p\mid b$, because $p\mid ab$ always implies $p\mid a$ or $p\mid b$ for $p$ prime. You should write this formally. $\endgroup$ – Dietrich Burde Aug 4 '19 at 16:59
  • $\begingroup$ @DietrichBurde Thanks! $\endgroup$ – rowcol Aug 4 '19 at 17:15
  • $\begingroup$ "If pi for some i doesn't appear in the prime factors of b, then pi couldn't appear in the prime factors of bn." ... yeah... but this doesn't address how many times the $p_i$ occurs. You get $p_i = q_j$ for some $q_j$ but then you have $p_m =p_i$ and so maybe $p_m = q_j$ and you never the other $q_j$. For example $12\not \mid 18$ and yet $12 =3*2*2;p_1=3;p_2=2;p_3=2$ so $12^n = 3^n*2^n*2^n$ and $18=2*3*3;q_1=2;q_2=3;q_3=3$ and we have $p_1=q_2$ and $p_2=q_1$ and $p_3=q_1$. we have $12=q_2q_1q_1$ and $q_2q_1|b$ but we don't have $q_2q_1q_1=q_2q_1$ $\endgroup$ – fleablood Aug 4 '19 at 17:51
  • $\begingroup$ NOT a duplicate as this is a "critique my proof" and not a "how do I prove it" question. $\endgroup$ – fleablood Aug 4 '19 at 18:10

I think you have a problem with if $p_i=p_j$ and $p_i$ must be one of the $q_r$ and $p_j$ must be one of the $q_s$, you haven't distinguished that if we chose $p_i$ as $q_r$ that we can not also choose $p_j$ as the same instance of $q_r$. You haven't come up with a method of removing $q_r$ from the pool once its been use.

For instance if $a = 12$ and $b =18$ and $p_1 = 2; p_2=2; p_3=3$ and $q_1=2; q_2 =3; q_3=3$ we'd have each $p_j$ equal to some $q_i$: $p_1 = q_1$ and $p_2 = q_1$ and $p_3 = q_2$. We haven't got a method to say if $p_1 = q_1$ we can't use $q_1$ a second time.

I can see why you wanted to avoid powers but... I think you need them.

If $a= \prod p_i^{v_i}$ and $b = \prod q_j^{w_j}$ then $a^n= \prod p_i^{n*v_i}|b^n = \prod q_j^{n*w_j}$ so $\{p_i\}\subset \{q_j\}$.

Relabel the variables and write $b$ as $\prod p_i^{u_i} \prod_{q_j\not \mid a} q_j^{w_j}$. So we have $b^n = \prod p_i^{n*u_i} \prod_{q_j\not \mid a} q_j^{n*w_j}$ and we have for each $n*vi \le n*u_i$. Which means $u_i \le v_i$. So $b = \prod p_i^{u_i\ge v_i} \prod_{q_j\not \mid a} q_j^{w_j}$. And thus $a = \prod p_i^{v_i}| \prod p_i^{u_i\ge v_i} \prod_{q_j\not \mid a} q_j^{w_j} = b$.


Note: https://math.stackexchange.com/a/1815338/280126 is a similar proof that doesn't require unique prime factorisation but that if $\frac ba \in \mathbb Q$ and we represent it as $\frac {b'}{a'}$ where $a'$ and $b'$ are relatively prime we get a contradiction if we assume $b' \ne 1$.

I don't know if it is easy, nor do I understand, the frequent complaint "You don't need unique factorization[1]" (Yeah, ... but is there are reason to avoid it?) But it's worth a looksie as basically the same concept, but with much of the tedious mechanics we had to slog through rather simplified.

[1]Of course this requires that rationals can be written in lowest terms and that all integers have a prime factor and those presume unique factorization so it isn't avoided.


This question have be answered before, here is an answer by Bill Dubuque.

Hint $\,\ \dfrac{b^n}{a^n} = k\in \Bbb Z$ $\ \Rightarrow\ $ $x = \dfrac{b}a\ $ root of $\ x^n\!-k$ $\!\!\!\!\underbrace{\Rightarrow\,x\in\Bbb Z}_{\text{ Rational Root Test}}\!\!\!\!\!$ $\,\Rightarrow\, a\mid b $

Another answer in a different way by awllower,

Prime factorization is not needed: we only need the fact that every integer $\ne\pm1$ has a prime divisor.
Define $r=a/b\in\mathbb Q.$ As $b^n\mid a^n,$ we know $r^n\in\mathbb Z.$
Write $r=a'/b'$ with $\gcd(a',b')=1.$ Let $s=r^n.$ Then $r^n=s$ implies that $(a')^n=(b')^n\cdot s.$ This shows that every prime divisor of $b'$ divides $(a')^n;$ by the definition of a prime, this means that every prime divisor of $b'$ divides $a'.$ This contradicts $\gcd(a',b')=1.$ Therefore $b'$ has no prime divisor, and is equal to $\pm1.$ Thus $r=a/b=a'/b'=\pm a'\in\mathbb Z.$ So $b$ divides $a.$

  • 2
    $\begingroup$ The OP asked if his/her proof was valid. He/she didn't ask for an alternative proof. $\endgroup$ – fleablood Aug 4 '19 at 18:11

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.