# 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. – Mariano Suárez-Alvarez May 2 '12 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". – Lone Learner May 2 '12 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.) – Martin Sleziak Jun 12 '15 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$. – 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.

-