# Prove that every positive integer $n$ is a unique product of a square and a squarefree number

I am trying to prove that for every integer $n \ge 1$, there exists uniquely determined $a > 0$ and $b > 0$ such that $n = a^2 b$, where $b$ is squarefree.

I am trying to prove this using the properties of divisibility and GCD only. Is it possible?

Let me assume that $n = a^2 b = a'^2b'$ where $a \ne a'$ and $b \ne b$'. Can we show a contradiction now?

• The question this has been dupped to did not include the added condition of using only properties of divisibility and of the GDC—indeed, the answers there do not satisfy this condition. Commented May 2, 2012 at 4:26
• Please reopen this question. This question is not a duplicate. This question requires proof by contradiction which I can't find in the link provided as "possible duplicate". Commented May 2, 2012 at 17:50
• It is probably worth mentioning that the question to which the previous comments refer is Show that every n can be written uniquely in the form n=ab, with a square-free and b a perfect square. (See revision history.) Commented Jun 12, 2015 at 8:50

For existence: given $n\geq1$, there is a maximal-for-divisibility integer $a$ such that $a^2$ divides $n$ and then $n=a^2b$ for some $b$. If $b$ is divisible by the square of a positive integer $c$, then $n$ is divisible by $(ac)^2$, then the maximality of $a$ implies that $ac=a$, that is that $c=1$: this means that $b$ is squarefree.

For uniqueness: suppose now that we also have $n=c^2d$ with $d$ squarefree. The maximality of $a$ implies that $c\mid a$, so there is an $e$ such that $a=ce$, and then from $c^2e^2b=a^2b=c^2d$ we get $e^2b=d$: since $d$ was supposed to be square free, $e=1$. It follows that $a=c$ and $b=d$.

It should be noted that proving there exists a maximal-for-divisibility $a$ such that $a^2\mid n$ depends on the basic properties of the divisibility relation and the GDC. All the rest is more or less tech-free.

• Is it so obvious that $\text{gcd}(a^2, b^2) = (\text{gcd}(a,b))^2$? I think this is needed for the existence of that maximal-for-divisibility $a$. Commented May 2, 2012 at 4:30
• In addition to what RobertIsrael asked, I have another question about this: "The maximality of a implies that c ∣ a." - Why? I know this is true but as far as this proof is concerned, this is a property that has not been introduced in the book yet. Commented May 2, 2012 at 18:07
• @André But the proof isn't using maximality with respect to absolute value but, rather, w.r.t. to a certain divisibility condition, more precisely, the property proved in the prior question that I link to. It would be helpful if the author stated this more precisely, since it seems to have confused at least a couple readers. Commented May 2, 2012 at 19:12
• @AndréNicolas Could you please share your proof? Commented May 2, 2012 at 19:26
• @Mariano Of course I know the inference. Could you please say in your answer precisely what you mean by "maximal-for-divisibility". If I'm not sure what you intend, then I doubt students will fare better. Commented May 2, 2012 at 21:09

For existence, let $a$ be the largest integer, in the usual ordering, such that $a^2$ divides $n$. If $n=a^2q$, then $q$ must be square-free.

For uniqueness, call a positive integer bad if it has two different decompositions $a^2 c$ and $b^2 d$, where $c$ and $d$ are square-free, and $a$ and $b$ are positive. If there are bad positive integers, let $M$ be the smallest bad one.

If $a$ and $b$ are not relatively prime, we can produce a bad positive integer smaller than $M$. So $a$ and $b$ are relatively prime.

We show that $a^2$ and $b^2$ are relatively prime. There are various approaches. One I like is that there exist integers $x$ and $y$ such that $ax+by=1$. Cube both sides. We get $$a^2(ax^3+3x^2by)+b^2(3axy^2+by^3)=1,$$ which says that $a^2$ and $b^2$ are relatively prime.

Since $a^2c=b^2d$ and $a^2$ and $b^2$ are relatively prime, we have $a^2\mid d$. This contradicts the fact that $d$ is square-free, unless $a=1$. Similarly, $b=1$, and therefore $M$ cannot be bad.

Hint $\$ If $\rm\: a^2 d =n = b^2 c\:$ for squarefree $\rm\:d,c\:$ then $\rm a\:|\:b\:|\:a\:\Rightarrow\:a=b,\:$ since, by your prior question, for $\rm\: z\:$ squarefree, $\rm\ x^2\:|\:y^2 z\:\Rightarrow\: x\:|\:y,\:$ which we apply twice above, in both directions.

• But in this problem $a^2$ is not necessarily the largest square that divides $n$. Commented May 2, 2012 at 19:25
• @LoneLearner But my proof in the linked thread doesn't use that. Rather, it uses only that $\rm\:c\:$ is squarefree (necessarily true when its cofactor $\rm\:b^2\:$ is a maximal square divisor of $\rm\:n = b^2 c,\:$ else $\rm\:d^2\:|\:c,\ d > 1\:$ $\Rightarrow$ $\rm\:(bd)^2\:|\:n,\ bd > b,\:$ contra maximality of $\rm\:b).$ Commented May 2, 2012 at 19:49