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

I need to show that every positive integer $n$ can be written uniquely in the form $n = ab$, where $a$ is square-free and $b$ is a square. Then I need to show that $b$ is then the largest square dividing $n$.

The problem I have here is that I can't even see how this is true. How can $1$ be represented this way? Is $1$ a square number? If not, then I cannot see how this is possible. If it is, then I cannot see how $1$, $2$, or $3$ can be represented this way.

Please, any help you can offer giving me a push in the right direction here is greatly appreciated.

-
1 is a square, 1 = 1*1, 2 = 2*1, 3 = 3*1 –  Soarer Feb 9 '11 at 23:54
$1$ is both square-free and a square. –  mjqxxxx Feb 9 '11 at 23:54

$1=1^2$, so $1$ is square. There are two natural ways to prove this result. One is using the prime factorization, i.e., the fundamental theorem of arithmetic. The other is by induction: if $n$ does not have a square factor, then $n$ is squarefree and $n$=$n\cdot 1$. Otherwise, divide $n$ by a square factor and use the induction hypothesis on the quotient.

-
But this proof doesn't rule out the possibility that we can divide n by a different square factor which would lead to a different factorization. –  Lone Learner May 2 '12 at 17:59

As others have mentioned, the number 1 is both squarefree and a square. When $n=1$, we have $a=b=1$. When $n$ is a prime, we have $a=n$ and $b=1$. This is perfectly valid.

Let me expand on the first method mentioned by lhf. In general, let $$N=\prod_{\text{primes }p_i}p_i^{e_i}$$ be the prime decomposition of a number $N$. Note that $N$ is squarefree if and only if each $e_i$ is either 0 or 1, and $N$ is a square if and only if every $e_i$ is even. So if we want to write $n=ab$ where $a$ is squarefree and $b$ is a square, then if their prime factorizations are as follows, $$n=\prod_{\text{primes }p_i}p_i^{x_i}\hskip0.3in a=\prod_{\text{primes }p_i}p_i^{y_i}\hskip0.3in b=\prod_{\text{primes }p_i}p_i^{z_i}$$ then we want to solve $$n=\prod_{\text{primes }p_i}p_i^{x_i}=\prod_{\text{primes }p_i}p_i^{y_i+z_i}=ab$$ such that each $y_i$ is either 0 or 1, and each $z_i$ is even. Can you see why this uniquely specifies all the $y_i$'s and $z_i$'s, and hence uniquely specifies $a$ and $b$?

-
Is it enough to state that because each $y_i$ must be 0 or 1 and each $z_i$ must be even, that this uniquely specifies a and b? Or do I need to show that this will always be unique? –  user6548 Feb 10 '11 at 1:33
You need to show that (1) a natural number $N$ is squarefree iff every exponent in its prime factorization is either 0 or 1, (2) a natural number $N$ is a square iff every exponent in its prime factorization is even, and (3) given an arbitrary natural number $n$ with prime factorization $$n=\prod_{\text{primes }p_i}p_i^{x_i}$$, there exist unique values of $y_i$ and $z_i$ such that $x_i=y_i+z_i$, $z_i$ is even, and $y_i$ is either 0 or 1. Then you will have that $$n=\prod_{\text{primes }p_i}p_i^{x_i}=\prod_{\text{primes }p_i}p_i^{y_i+z_i}=$$ –  Zev Chonoles Feb 10 '11 at 1:56
$$\prod_{\text{primes }p_i}p_i^{y_i}\prod_{\text{primes }p_i}p_i^{z_i}$$ where $\prod_{\text{primes }p_i}p_i^{y_i}$ is squarefree and $\prod_{\text{primes }p_i}p_i^{z_i}$ is a square by the properties we chose the $y_i$ and $z_i$ to have. These are your $a$ and $b$, respectively. Because a natural number is uniquely specified by its prime decomposition, this means that $a$ and $b$ must be unique. –  Zev Chonoles Feb 10 '11 at 2:00

HINT $\$ The problem is multiplicative so it suffices to show that it's 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.

-
Actually, it's completely multiplicative and so a simple induction suffices. This observation gives another proof: if $n$ is prime, then it's done. Otherwise, let $n=uv$ be a non-trivial factorization. The squarefree factorizations of $u$ and $v$ combine to a squarefree factorization of $n$. –  lhf Feb 10 '11 at 0:18
@lhf: Not really. Say $n=64$, and I write $n=8\times 8$. The squarefree factorization of $8$ is $2\times 2^2$; the one for $8$ is $2\times 2^2$; I combine the $2^2\times 2^2 = (2\times 2)^2$ to get the square part for $64$, and combine the squarefree parts of the two factors, $2$ and $2$, to get $4$ as the "squarefree" part of $64$. –  Arturo Magidin Feb 10 '11 at 4:49
@Arturo: ah, right. It seems we need $(u,v)=1$, so not completely multiplicative after all. Thanks for the correction. Sorry for the noise. –  lhf Feb 10 '11 at 11:05
@lhf: It is necessary and sufficient that the squarefree parts of $u$ and $v$ are relatively prime; inductively, you could take the gcd and "move it" from, say, the squarefree part of $u$ to the square part of $v$. –  Arturo Magidin Feb 10 '11 at 14:16
Yes, $\rm\ (aAA)\:(bBB) = ab\:(AB)^2\$ and $\rm\ ab\$ is squarefree $\iff$ $\rm\ a,\:b\$ are squarefree and coprime. This is a prototypical example of a multiplicative function. As such it provides an excellent learning experience. I purposely chose not to give all the details so as not to rob the reader of that experience. That's one reason why I prefer to give hints rather than full solutions. –  Bill Dubuque Feb 10 '11 at 16:39