3
$\begingroup$

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.

  • 0
    1 is a square, 1 = 1*1, 2 = 2*1, 3 = 3*12011-02-09
  • 6
    $1$ is both square-free and a square.2011-02-09

3 Answers 3

2

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

  • 0
    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.2012-05-02
2

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

  • 0
    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?2011-02-10
  • 0
    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}=$$2011-02-10
  • 0
    $$\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.2011-02-10
2

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
    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$.2011-02-10
  • 2
    @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$.2011-02-10
  • 1
    @Arturo: ah, right. It seems we need $(u,v)=1$, so not completely multiplicative after all. Thanks for the correction. Sorry for the noise.2011-02-10
  • 0
    @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$.2011-02-10
  • 0
    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.2011-02-10
  • 0
    @lhf, @Arturo: By the way, here's an interesting exercise to help fortity your understanding of "squarefree". Use the above to give a slick proof of the irrationality of $\sqrt{2}$. Hint: taking the squarefree part of $\rm\ 2\:a^2 = b^2\ $ yields $\rm\ 2 = 1\:$2011-02-10