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.

  • $\begingroup$ 1 is a square, 1 = 1*1, 2 = 2*1, 3 = 3*1 $\endgroup$ – Soarer Feb 9 '11 at 23:54
  • 6
    $\begingroup$ $1$ is both square-free and a square. $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – 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$?

  • $\begingroup$ 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? $\endgroup$ – user6548 Feb 10 '11 at 1:33
  • $\begingroup$ 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}=$$ $\endgroup$ – Zev Chonoles Feb 10 '11 at 1:56
  • $\begingroup$ $$\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. $\endgroup$ – 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.

  • 3
    $\begingroup$ 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$. $\endgroup$ – lhf Feb 10 '11 at 0:18
  • 2
    $\begingroup$ @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$. $\endgroup$ – Arturo Magidin Feb 10 '11 at 4:49
  • 1
    $\begingroup$ @Arturo: ah, right. It seems we need $(u,v)=1$, so not completely multiplicative after all. Thanks for the correction. Sorry for the noise. $\endgroup$ – lhf Feb 10 '11 at 11:05
  • $\begingroup$ @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$. $\endgroup$ – Arturo Magidin Feb 10 '11 at 14:16
  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque Feb 10 '11 at 16:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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