Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

marked as duplicate by lhf, Thomas Andrews, t.b., Asaf Karagila, Zev Chonoles Apr 1 '12 at 15:56

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

HINT: $b$ and $b^\prime$ are square-free and $b/b^\prime$ is a square in $\Bbb Q$. Thus..... – Andrea Mori Feb 29 '12 at 17:13

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$.)

share|cite|improve this answer

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

share|cite|improve this answer
The proof does use FTA (uniqueness of factorization) since it uses the equivalent property that if a prime divides a product then it divides some factor. – Bill Dubuque Feb 29 '12 at 18:33
Not true. Uniqueness of factorization is equivalent to the fact that irreducibles $\rm\:p\:$ are prime, i.e. $\rm\:p\ |\ ab\ \Rightarrow\ p\ |\ a\ or\ p\ |\ b,\:$ in every domain where elements $\ne 0$ can be factored into irreducibles. In fact, in any domain, products of primes always factor uniquely, i.e. that is the only factorization into irreducibles (up to order and associates). – Bill Dubuque Feb 29 '12 at 18:59
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. – Bill Dubuque Feb 29 '12 at 19:11

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.

share|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.