6
$\begingroup$

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?

  • 6
    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.2012-05-02
  • 0
    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".2012-05-02
  • 0
    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](http://math.stackexchange.com/questions/21282/show-that-every-n-can-be-written-uniquely-in-the-form-n-ab-with-a-squa). (See [revision history](http://math.stackexchange.com/posts/139737/revisions).)2015-06-12

3 Answers 3

3

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.

  • 2
    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$.2012-05-02
  • 0
    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.2012-05-02
  • 0
    @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.2012-05-02
  • 0
    @AndréNicolas Could you please share your proof?2012-05-02
  • 0
    @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?2012-05-02
  • 0
    @André Ah, I didn't realize your comment was addressed to Mariano. It's not clear to me that he actually intends to use *divisibility* maximality in the existence proof, since he writes that, by maximality, $\rm\:ac = a,\:$ rather than $\rm\:ac\:|\:a$.2012-05-02
  • 0
    @Bill: inthe 1st paragraph, I got that the square of $ac$ divides $n$ so, my the maximality-for-divisibility, $ac\mid a$. As $a\mid ac$ too, this implies that $ac=a$ (everything in sight is positive)2012-05-02
  • 0
    @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.2012-05-02
  • 0
    I meant *maximal for the divisibility relation*. That's why I wrote what I wrote!2012-05-02
  • 0
    @MarianoSuárez-Álvarez Then the conclusion fo4 $c\mid a$ requires some addiitonal step with properties of the divisor lattice of $n$, e.g., that $a^2\mid n$ and $c^2\mid n$ implies $\operatorname{lcm}(a,c)^2\mid n$. If instead of "the set of divisors of $n$", we consider the set $S=\{1,2,3,4,6,9\}$, then $S$ contains *two* maximal-for-divisibility squares, namely $2^2$ and $3^2$, but $2\nmid 3$.2017-04-03
2

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.

  • 0
    But in this problem $a^2$ is not necessarily the largest square that divides $n$.2012-05-02
  • 0
    @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).$2012-05-02
1

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.