# Is this proof about divisibility correct?

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

• 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. – Dietrich Burde Aug 4 '19 at 16:59
• @DietrichBurde Thanks! – rowcol Aug 4 '19 at 17:15
• "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$ – fleablood Aug 4 '19 at 17:51
• NOT a duplicate as this is a "critique my proof" and not a "how do I prove it" question. – 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.$$

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