2
$\begingroup$

Let $a, b, n$ be elements of $\mathbb N$ such that $ a^n\mid b^n $. Show that $a\mid b$.

[P.S. Use the axioms of natural numbers.]

Are we using the properties of divisibility and afterwards induction? I kind of have an idea but I am not quite sure.

$\endgroup$
7
  • 1
    $\begingroup$ If you use the unique factorisation theorem, it follows pretty smoothly. $\endgroup$
    – user88595
    Dec 15, 2013 at 16:09
  • $\begingroup$ i am not allowed to use the unique factorization theorem,because i also thought of using that @user88595 $\endgroup$
    – a1bcdef
    Dec 15, 2013 at 16:14
  • $\begingroup$ You have zero accept answers so far. Please read about accepting answers here and here. $\endgroup$
    – Git Gud
    Dec 15, 2013 at 16:31
  • $\begingroup$ To prove this normally requires using something that is essentially equivalent to uniqueness of prime factorizations (e.g. see the many equivalents listed here). Do you have any of these available? If not, you will need to prove one of them (or, essentially, inline their (inductive) proofs in your proof). $\endgroup$ Dec 15, 2013 at 18:37
  • $\begingroup$ If you kind of have an idea, you should include the details, so that we know how to effectively help you. $\endgroup$ Dec 15, 2013 at 19:31

2 Answers 2

4
$\begingroup$

Hint $\rm\ \ (b/a)^n = k \in \Bbb Z\ \Rightarrow\ b/a\in \Bbb Z\ $ by the Rational Root Test, i.e. if $\,x\,$ is a rational root of the polynomial $\rm \,\color{#c00}1\cdot x^n-k\,$ then its least-terms denominator divides $\color{#c00}1,\,$ so $\,x\,$ is an integer.

$\endgroup$
1
  • $\begingroup$ From a foundational perspective (and possibly relevant to the OP's class), it's interesting to consider how the rational root test compares to the uniqueness of prime factorizations. The proof of the rational root test uses two number theory facts: (1) if $a$ and $b$ are coprime, then so are $a$ and $b^n$; (2) if $a$ and $b$ are coprime and $a$ divides $bc$, then $a$ divides $c$. Both of these can be proved from Bézout's identity alone, without using prime factorizations. $\endgroup$ Dec 15, 2013 at 19:30
1
$\begingroup$

Hint: let $p_1^{\alpha_1}\cdot…\cdot p_k^{\alpha_k}=a$, $q_1^{\beta_1}\cdot…\cdot q_m^{\beta_m}=b$ be prime decompositions. Then $a^n=p_1^{n\alpha_1}\cdot…\cdot p_k^{n\alpha_k}$, $b^n=q_1^{n\beta_1}\cdot…\cdot q_m^{n\beta_m}$. Now write up what $a^n|b^n$ means in term of prime powers.

$\endgroup$
1
  • 1
    $\begingroup$ OP is not allowed here to use the unique factorization theorem. See her comments. $\endgroup$
    – drhab
    Dec 15, 2013 at 16:35

Not the answer you're looking for? Browse other questions tagged .