4
$\begingroup$

Prove/Show that a number is square if and only if its prime decomposition contains only even exponents.

How would you write a formal proof for this.

  • 0
    Iff: First, assume a number is square and show that the prime factorization has even exponents. Then, assume the factorization has even exponents and show that the number is square. In general to prove $A \iff B,$ show both $A \implies B$ and $B \implies A.$2012-07-05
  • 0
    After proving this, it should be easy for you to generalize the problem to $n$th powers: integer is an $n$th power if and only if its prime factorization contains only multiples of $n$ as exponents.2012-07-05

2 Answers 2

6

Suppose $a = p_1^{r_1}...p_n^{r_n}$. If $r_i$ are all even, then let $b = p_1^{\frac{r_1}{2}} ... p_n^{\frac{r_n}{2}}$. Then $b^2 = a$.

Suppose $a = b^2$. Let $q_1^{s_1} ... q_m^{s_m}$ be the unique prime factorization of $b$. Then $a = q_1^{2s_1} ... q_m^{2s_m}$. So by unique factorization all primes of $a$ have even powers.

5

Suppose $x=y^2$ for some integer $y$. Let $$y=p_1^{e_1}\cdots p_n^{e_n}$$ be a decomposition of $y$ into primes. Then $$x=y^2=p_1^{2e_1}\cdots p_n^{2e_n}$$ so its prime decomposition has only even exponents.

Suppose the prime decomposition of $x$ has only even exponents, so we can write $$x=p_1^{2e_1}\cdots p_n^{2e_n}$$ for some set of primes $P_i$ and integers $e_i$. Then $$x=\left(p_1^{e_1}\cdots p_n^{e_n}\right)^2$$ so $x$ is a perfect square.