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?

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$. – Robert Israel May 2 '12 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. – Lone Learner May 2 '12 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. – Bill Dubuque May 2 '12 at 19:12
• @AndréNicolas Could you please share your proof? – Lone Learner May 2 '12 at 19:26
• @André I presumed that your your comment was in reply to the OP's prior comment (or RI's) which both concern divisibility maximality. I didn't think it was addressed to to Mariano, since it's just a more concise version of what he wrote in the first paragraph. What did you intend? – Bill Dubuque May 2 '12 at 19:42

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$. – Lone Learner May 2 '12 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).$ – Bill Dubuque May 2 '12 at 19:49

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.