4
$\begingroup$

Possible Duplicate:
Show that every $n$ can be written uniquely in the form $n = ab$, with $a$ square-free and $b$ a perfect square

I am trying to prove that for every $n \ge 1$ there exist uniquely determined integers $a \gt 0$ and $b \gt 0$ such that $n = a^2b$ where $b$ is square-free.

The fact that such $a$ and $b$ exist is easy to prove.

From the fundamental theorem of arithmetic, $n$ can be uniquely represented as $p_1^{a_1} p_2^{a_2} \cdots p_s^{a_s}$ where $s$ is a positive integer. Thus

\begin{align*} n & = \prod_{i=1}^s p_i^{a_i} \\\\ & = \prod_{i=1}^s p_i^{\left(2 \left\lfloor \frac{a_i}{2} \right\rfloor + a_i \bmod{2}\right)} \\\\ & = \prod_{i=1}^s p_i^{\left(2 \left\lfloor \frac{a_i}{2} \right\rfloor\right)} \cdot \prod_{i=1}^s p_i^{a_i \bmod{2}} \\\\ & = \left(\prod_{i=1}^s p_i^{\left\lfloor \frac{a_i}{2} \right\rfloor}\right)^2 \cdot \prod_{i=1}^s p_i^{a_i \bmod{2}}. \end{align*}

Clearly, $\left(\prod_{i=1}^s p_i^{\left\lfloor \frac{a_i}{2} \right\rfloor}\right)^2$ is a perfect square and $\prod_{i=1}^s p_i^{a_i \bmod{2}}$ is square free. Hence, we have shown that such $a$ and $b$ exist.

Now, how do we show that such a pair of $a$ and $b$ is unique?

I know how to start proving such a theorem. Let us assume that $n = a^2b = a'^2b'$ such that $a' \ne a$ and $b' \ne b$. Now since this is not possible this should lead us to some contradiction. But, I'm unable to reach a contradiction from this assumption. Could you please help me?

  • 1
    HINT: $b$ and $b^\prime$ are square-free and $b/b^\prime$ is a square in $\Bbb Q$. Thus.....2012-02-29

3 Answers 3

3

The proof of existence that you gave is fine, and can be adapted to produce a proof of uniqueness by using the essential uniqueness of prime power factorization.

But let us prove existence and uniqueness without explicit use of the representation of natural numbers as a product of powers of primes.

Existence: Call a natural number bad if it does not have a representation of the type we want. If there are bad natural numbers, there is a smallest bad number $n$. It is clear that $n>1$.

Thus $n$ is divisible by some prime $p$. Let $m=n/p$. By the minimality of $n$, the number $m$ is good, so has a representation as $a^2b$ where $b$ is square-free.

If $p$ does not divide $b$, then $n=pm=a^2(pb)$, and $pm$ is square-free, contradicting the badness of $n$.

If $p$ divides $b$, then b=pb' for some natural number b'. Note that b' is square-free. Then n=mp=(ap)^2b', again contradicting the badness of $n$.

Uniqueness: Suppose that there are natural numbers that have more than one representation. Call such a natural number bad. If there is a bad number, then there is a smallest bad number $n$. Clearly $n> 1$.

So $n$ has two different representations $n=a^2b$ and $n=c^2d$, where $c$ and $d$ are square-free. (Different here means that $a^2\ne c^2$ or $b\ne d$, or both.)

Since $n > 1$, there is a prime $p$ that divides $n$. Suppose first that $p^2$ does not divide $n$. Then $p$ cannot divide either $a$ or $c$. So $p$ must divide both $b$ and $d$. Let b=pb', d=pd', and let $m=n/p$. Then m=a^2b'=c^2d', and therefore $m$ is bad, contradicting the minimality of $n$.

If $p^2$ divides $n$, then since $p^2$ cannot divide $b$, we must have that $p$ divides $a^2$, and therefore $p$ divides $a$. Similarly, $p$ divides $c$. Let a=pa', and c=pc'. Let $m=n/p^2$. We conclude that m=(a')^2b=(c')^2d, again contradicting the minimality of $n$.

  • 0
    My first comment refers to your (original) claim that you "prove existence and uniqueness without using FTA". Since you've edited the answer to remove that claim, the point is now moot. It is important to be careful about remarks like that since they are the source of many errors in number theory.2012-02-29
1

For a proof using minimal machinery, I prefer:

Consider all representations of $n$ in the form $n=a^2b$, where $a$ and $b$ can be any positive integers. (These can be indexed by the set $A$ of positive integers $a$ such that $a^2\mid n$.) You can show that $A$ consists exactly of all divisors of a special integer $a_{max}\in A$, and then that in the representation $n=a^2b$ where $a\in A$, the corresponding $b$ is squarefree if and only if $a=a_{max}$. (Hint: if $a^2\mid n$ and $c^2\mid n$, then $(lcm[a,c])^2 \mid n$.)

0

Hint $\ $ The problem is multiplicative, thus it suffices to show that it is true for a prime power $\rm\ P^N\:.\ $ But that's trivial: $\rm\ P^{2N} =\ (P^N)^2,\ \ P^{\:2N+1} =\ P\ (P^N)^2\:,\ $ uniquely. $\ $ QED

Alternatively, examining the power of each prime in unique prime factorizations, the sought uniqueness reduces to the uniqueness of quotient and remainder (for division by $2$). Namely, suppose we have two squarefree factorizations $\rm\: A^2 B = n = C^2 D$ and suppose the prime $\rm p$ has power $\rm\:a,b,c,d\:$ in $\rm\:A,B,C,D\:$ resp. Since $\rm\:B,D\:$ are squarefree, $\rm\:0\le b,d\le 1.\:$ Now comparing the power of $\rm\:p\:$ in both decompositions, and using unique factorization we deduce

$\rm 2\:a+b\ =\ 2\:c + d\ \ \Rightarrow\ \ a=c,\: b = d$

which is clear by rewriting it $\rm\ 2\:(a-c)\: =\: d-b.\:$ Now $\rm\:|d-b| < 2\:$ $\Rightarrow$ $\rm\:d=b\:$ $\Rightarrow$ $\rm\:a=c$.

Note that squarefree decompositions may fail to be unique in domains lacking unique factorization, where one may have factorizations like $\rm\ p\:q = r^2\ $ for nonassociate non-prime irreducibles $\rm\:p,q,r$. Thus any proof must employ unique factorization or some closely related property.