An integer n>1 is square-free if and only if?

[Math100]

Homework Statement

An integer is said to be square-free if it is not divisible by the square of any integer greater than $1$. Prove the following:

An integer $n>1$ is square-free if and only if $n$ can be factored into a product of distinct primes.

Relevant Equations

None.

Proof:

Suppose an integer $n>1$ is square-free.
Then we have $a^2\nmid n, \forall a\in\mathbb{Z}$.
Let $n=p_{1}^{a_{1}} p_{2}^{a_{2}}\dotsb p_{r}^{a_{r}}$ be the
prime factorization of $n$ such that each $a_{i}$ is a positive integer
and $p_{i}'s$ are prime for $i=1,2,3,...,r$ with $p_{1}<p_{2}<p_{3}<\dotsb <p_{r}$.
Note that $a^{2} m\neq n$
$\neq p_{1}^{a_{1}} p_{2}^{a_{2}}\dotsb p_{r}^{a_{r}}$ for some $m\in\mathbb{Z}$.
Thus, $n$ can be factored into a product of distinct primes.
Conversely, suppose $n$ cannot be factored into a product of distinct primes.
Then we have $n=ap^2$ for some $a\in\mathbb{Z}$ where $p$ is a prime number.
This means $p^2\mid n, \forall p\in\mathbb{Z}$.
Thus, an integer $n>1$ is not square-free.
Therefore, an integer $n>1$ is square-free if and only if $n$ can be factored into a
product of distinct primes.

 

[PeroK]

You have the same flaw again. You have $a > 1$ and not an arbitrary integer.

I'm not convinced by the first half of your proof. Where have you proved the assertion?

 

[Math100]

You have the same flaw again. You have $a > 1$ and not an arbitrary integer.

I'm not convinced by the first half of your proof. Where have you proved the assertion?

Then we have $a^2\nmid n$ for $a>1$.

And how should I prove the assertion for the first half of my proof?

 

[PeroK]

And how should I prove the assertion for the first half of my proof?

You have to find something that works.

 

[nuuskur]

Note that $a^{2} m\neq n$
$\neq p_{1}^{a_{1}} p_{2}^{a_{2}}\dotsb p_{r}^{a_{r}}$ for some $m\in\mathbb{Z}$.

What is $a$? What does this non-equality prove?

Thus, $n$ can be factored into a product of distinct primes.

What, now? Does the product consist of distinct primes if some $a_i\geqslant 2$? How would this relate to $n$ being square-free?

Conversely, suppose $n$ cannot be factored into a product of distinct primes.

You are not proving the converse statement. In one direction, you'd show
$$n\text{ square-free} \Rightarrow n\text{ factors distinctly}$$
The other direction is
$$n\text{ factors distinctly} \Rightarrow n\text{ square-free}$$
The converse supposition is either $n$ factors distinctly OR $n$ is not square-free.

I have noticed on a few occasions now that you are very detail-oriented when you are writing down obvious things. An example is

Let $n=p_{1}^{a_{1}} p_{2}^{a_{2}}\dotsb p_{r}^{a_{r}}$ be the
prime factorization of $n$ such that each $a_{i}$ is a positive integer
and $p_{i}'s$ are prime for $i=1,2,3,...,r$ with $p_{1}<p_{2}<p_{3}<\dotsb <p_{r}$.

It is correct and it makes sure there is no ambiguity. But why won't you apply the same kind of scrutiny when you write up the conclusions? You are not earning bonus points for pointing out things that are obvious when you fail to prove the statement. Details are important, but they are meaningless if you don't use them and proceed to write non-sequiturs or irrelevant statements.

Then we have $n=ap^2$ for some $a\in\mathbb{Z}$ where $p$ is a prime number.
This means $p^2\mid n, \forall p\in\mathbb{Z}$.

First statement is ok. The second statement is false.

 

[Math100]

Okay, so here's my revised proof:

Suppose an integer $n>1$ is square-free.
Let $n=p_{1}^{a_{1}} p_{2}^{a_{2}}\dotsb p_{r}^{a_{r}}$ be the
prime factorization of $n$ such that each $a_{i}$ is a positive integer
and $p_{i}'s$ are prime for $i=1,2,3,...,r$ with $p_{1}<p_{2}<p_{3}<\dotsb <p_{r}$.
Note that $a_{i}\geq 2$.
Then we have $p_{i}^2\mid n$.
This is a contradiction because an integer $n>1$ is square-free,
which implies that $a_{i}=1$.
Now we have $n=p_{1} p_{2}\dotsb p_{r}$ with $p_{i}\neq p_{j}$.
Thus, $n$ can be factored into a product of distinct primes.
Conversely, suppose an integer $n>1$ is not square-free.
Then we have $a^2\mid n$.
This means $n=a^2 m$ for some $m\in\mathbb{Z}$.
Let $a=q_{1}^{k_{1}} q_{2}^{k_{2}} q_{3}^{k_{3}}\dotsb q_{r}^{k_{r}}$.
Thus, $n=a^2 m$
$p_{1} p_{2} p_{3}\dotsb p_{r}=m (q_{1}^{2k_{1}} q_{2}^{2k_{2}} q_{3}^{2k_{3}}\dotsb q_{r}^{2k_{r}})$,
which implies that $q_{j}\mid p_{1} p_{2} p_{3}\dotsb p_{s}$.
The corollary states that if $p_{1} q_{1},q_{2},q_{3},...,q_{n}$ are all primes and
$p\mid q_{1} q_{2} q_{3}\dotsb q_{n}$, then $p=q_{i}$ for some $i=1,2,...,n$.
Factoring out $p_{i}$ and $q_{j}$ produces:
$p_{1} p_{2} p_{3}\dotsb p_{r}=m q_{1}^{2k_{1}} q_{2}^{2k_{2}} q_{3}^{2k_{3}}\dotsb q_{r}^{2k_{r}}$,
which implies that $q_{j}\mid p_{1} p_{2} p_{3}\dotsb p_{r}$.
Note that the original factorization $p_{1} p_{2} p_{3}\dotsb p_{r}$ is unique and
we factored out $q_{j}$.
Thus, an integer $n>1$ is square-free.
Therefore, an integer $n>1$ is square-free if and only if $n$ can be factored into a product of distinct primes.

 

[nuuskur]

Note that $a_{i}\geq 2$.
Then we have $p_{i}^2\mid n$.
This is a contradiction because an integer $n>1$ is square-free,
which implies that $a_{i}=1$.

1. IF some $a_i \geqslant 2$, then $p_i^2 \mid n$.
2. implies that $a_i=1$ for every $i$.

Conversely, suppose an integer $n>1$ is not square-free.
Then we have $a^2\mid n$.

Try to explain what new symbols mean. Say $a$ is an integer satisfying $a^2\mid n$ or that there exists $a\in\mathbb Z$ such that $a^2\mid n$. It's important make it clear how your statements are quantified.

What are you proceeding to prove, exactly? Where have you shown that $n$ does not factor distinctly? And if you are proving by contradiction, where have you reached a contradiction?

To use PeroK's analogy, you have checkmate in 2 here, but you are making nonsense moves.

 

[PeroK]

Okay, so here's my revised proof:

Suppose an integer $n>1$ is square-free.
Let $n=p_{1}^{a_{1}} p_{2}^{a_{2}}\dotsb p_{r}^{a_{r}}$ be the
prime factorization of $n$ such that each $a_{i}$ is a positive integer
and $p_{i}'s$ are prime for $i=1,2,3,...,r$ with $p_{1}<p_{2}<p_{3}<\dotsb <p_{r}$.

The first thing I'd do is swap these two lines over and have this first for the whole proof.

Let $n=p_{1}^{a_{1}} p_{2}^{a_{2}}\dotsb p_{r}^{a_{r}}$ be the
prime factorization of $n$ such that each $a_{i}$ is a positive integer
and $p_{i}'s$ are prime for $i=1,2,3,...,r$ with $p_{1}<p_{2}<p_{3}<\dotsb <p_{r}$.

The gist of the proof is then that $n$ is square free iff for all $i$ we have $a_i = 1$.

 

[nuuskur]

General remark. It is not the grader's job to decipher your proof attempt. It is your job to convince the grader (and yourself).

 

[Math100]

1. IF some $a_i \geqslant 2$, then $p_i^2 \mid n$.
2. implies that $a_i=1$ for every $i$.

Try to explain what new symbols mean. Say $a$ is an integer satisfying $a^2\mid n$ or that there exists $a\in\mathbb Z$ such that $a^2\mid n$. It's important make it clear how your statements are quantified.

What are you proceeding to prove, exactly? Where have you shown that $n$ does not factor distinctly? And if you are proving by contradiction, where have you reached a contradiction?

To use PeroK's analogy, you have checkmate in 2 here, but you are making nonsense moves.

For the second part (subproof) of my whole proof starting with 'Conversely'. What do you think is the better choice/idea? Should I use proof by contradiction or start out with $n$ factors distinctly and reach $n$ is square-free?

 

[PeroK]

For the second part (subproof) of my whole proof starting with 'Conversely'. What do you think is the better choice/idea? Should I use proof by contradiction or start out with $n$ factors distinctly and reach $n$ is square-free?

To me, you are almost finished after the first step:

Let $n=p_{1}^{a_{1}} p_{2}^{a_{2}}\dotsb p_{r}^{a_{r}}$ be the
prime factorization of $n$ such that each $a_{i}$ is a positive integer
and $p_{i}'s$ are prime for $i=1,2,3,...,r$ with $p_{1}<p_{2}<p_{3}<\dotsb <p_{r}$.

The gist of the proof is then that $n$ is square free iff for all $i$ we have $a_i = 1$.

Or, probably the simplest way to tackle this is to use the contraposition:

Show that $n$ is not square free iff there exists some $i$ with $a_i > 1$.

 

[Math100]

Okay, how about this revised proof below?

Let $n=p_{1}^{a_{1}} p_{2}^{a_{2}}\dotsb p_{r}^{a_{r}}$ be the prime factorization of $n$
such that each $a_{i}$ is a positive integer and $p_{i}'s$ are prime for $i=1,2,3,...,r$ with
$p_{1}<p_{2}<p_{3}<\dotsb <p_{r}$.
Suppose an integer $n>1$ is square-free and $a_{i}\geq 2$.
Then we have $p_{i}^2\mid n$.
This means $p_{i}^2 m=n$ for some $m\in\mathbb{Z}$.
Since $n>1$ is square-free,
it follows that $a_{i}=1$ for every $i$.
Thus, $n$ can be factored into a product of distinct primes.
Conversely, we will prove that if $n$ can be factored into a product of
distinct primes, then an integer $n>1$ is square-free using a proof by contradiction.
Suppose for the sake of contradiction that $n$ is divisible by the square of any integer
greater than $1$.
Then we have $n=a^2 m$ for some $a,m\in\mathbb{Z}$ such that
$a\geq 2$ and $m\geq 1$.
Let $a=q_{1}^{b_{1}} q_{2}^{b_{2}}\dotsb q_{k}^{b_{k}}$ be the prime factorization
of $a$ such that each $b_{i}$ is a positive integer and $q_{i}'s$ are prime for
$i=1,2,3,...,k$ with $q_{1}<q_{2}<q_{3}<\dotsb <q_{k}$.
Now we have $n=a^2 m$
$=(q_{1}^{b_{1}} q_{2}^{b_{q}}\dotsb q_{k}^{b_{k}})^2 m$
$=(q_{1}^{2b_{1}} q_{2}^{2b_{2}}\dotsb q_{k}^{2b_{k}}) m$.
Clearly, this contradicts the fact that $n$ can be factored into a product of
distinct primes.
Thus, an integer $n>1$ is square-free.
Therefore, an integer $n>1$ is square-free if and only if $n$ can be factored
into a product of distinct primes.

 

[nuuskur]

Suppose an integer $n>1$ is square-free and $a_{i}\geq 2$.
Then we have $p_{i}^2\mid n$.
This means $p_{i}^2 m=n$ for some $m\in\mathbb{Z}$.
Since $n>1$ is square-free,
it follows that $a_{i}=1$ for every $i$.

Quantify your statements.

Suppose an integer $n>1$ is square-free and $a_{i}\geq 2$ for some $i$

Due to $n$ being square-free, the above cannot be true, hence $a_i=1$ for every $i$ is forced.

Then we have $n=a^2 m$ for some $a,m\in\mathbb{Z}$ such that
$a\geq 2$ and $m\geq 1$.

This is fine, but you are working in $\mathbb N$ so you could also declare $a,m\in\mathbb N$ such that $a\geqslant 2$. A pedantic grader could also point out that if $a\in\mathbb Z$, then $a\geqslant 2$ need not follow.

Clearly, this contradicts the fact that $n$ can be factored into a product of
distinct primes.

This is bad style. You went through all this trouble of setting up the argument and then you declare the conclusion is obvious. Even more so, your supposition was for a contradiction. Do point out where lies a contradiction!

 

[PeroK]

I think it's better to say up front what you are doing. To follow on from my previous suggestion:

Let $n=p_{1}^{a_{1}} p_{2}^{a_{2}}\dotsb p_{r}^{a_{r}}$ be the
prime factorization of $n$ such that each $a_{i}$ is a positive integer
and $p_{i}'s$ are prime for $i=1,2,3,...,r$ with $p_{1}<p_{2}<p_{3}<\dotsb <p_{r}$.

We need to show that $n$ is square free iff for all $i$ we have $a_i = 1$ (i.e. iff $n$ can be factored into a product of distinct primes).

To do this, we will prove the equivalent contraposition:

That $n$ is not square free iff there exists some $i$ with $a_i \ge 2$.

Suppose some $a_i \ge 2$, then $p_i^2$ is a factor of $n$ and $n$ is not square free.

Suppose $n$ is not square free ...