Why does 10|n^2 imply that 10|n, and why does 9|n^2 not imply that 9|n

[bremenfallturm]

Homework Statement

a) Is it true that if $10|n^2\implies 10|n$?
b) Is it true that if $9|n^2\implies 9|n$?
(where $n$ is an integer).

Relevant Equations

Definition that $a|b$ if $b$ can be written as an integer multiple of a, that is $a|b\implies b=ka, k\in \mathbb Z$

The answer key only states that a) "is true" and b) "is false" but does not give any further context as to why.
My reasoning went as far as that the fundamental theorem of arithmetics and the fact that a perfect square (square of an integer) has even exponents in its prime factorization could come into play, but I don't understand how to apply it to this particular problem.
Help is appreciated!

 

[fresh_42]

A prime number $p$ is a number that is different from $\pm 1$ and for which
$$
p\,|\,(a\cdot b) \Longrightarrow p\,|\,a\text{ or }p\,|\,b
$$
holds. In case of $n=2\cdot 5$ we have $10\,|\,n^2 \Longrightarrow 2\,|\,n^2 \Longrightarrow 2\,|\,n$ and the same holds for the prime number $p=5.$ We thus have $2\,|\,n$ and $5\,|\,n.$ Since $2$ and $5$ are coprime, we get $10\,|\,n.$ Can you prove that this holds for coprime divisors, i.e. that
$$
k\,|\,n \text{ and } l\,|\,n \text{ and } \operatorname{gcd}(k,l)=1 \Longrightarrow k\cdot l\,|\,n\quad \text{ ?}
$$
The easiest way is probably by using the fundamental theorem of arithmetic.

Your second example is $9=3\cdot 3$ which are not coprime. We can only conclude that $3\,|\,n.$ Try to find a counterexample!

 

[bremenfallturm]

A prime number $p$ is a number that is different from $\pm 1$ and for which
$$
p\,|\,(a\cdot b) \Longrightarrow p\,|\,a\text{ or }p\,|\,b
$$
holds. In case of $n=2\cdot 5$ we have $10\,|\,n^2 \Longrightarrow 2\,|\,n^2 \Longrightarrow 2\,|\,n$ and the same holds for the prime number $p=5.$ We thus have $2\,|\,n$ and $5\,|\,n.$ Since $2$ and $5$ are coprime, we get $10\,|\,n.$ Can you prove that this holds for coprime divisors, i.e. that
$$
k\,|\,n \text{ and } l\,|\,n \text{ and } \operatorname{gcd}(k,l)=1 \Longrightarrow k\cdot l\,|\,n\quad \text{ ?}
$$
The easiest way is probably by using the fundamental theorem of arithmetic.

Your second example is $9=3\cdot 3$ which are not coprime. We can only conclude that $3\,|\,n.$ Try to find a counterexample!

Thank you! I got a little further thanks to this but I'm still not all the way there.
Let me just double check that you could write $2\,|\,n^2 \Longrightarrow 2\,|\,n$ because $2$ is prime so $2|n\cdot n$ but $2$ can only divide $n$. Is that because that $n^2$ has one unique prime factorization, where each (relevant) prime number (potentially raised to an exponent) appears once?

For the proof, I'm quite unsure where to start, but what I thought about is that:
We know that $k$, $l$ has unique prime factorizations dues to the fundamental theorem of arithmetic.
We know that $k|n\implies n=\alpha k, l|n\implies n=\beta l, \text{ where }\alpha, \beta \in \mathbb Z$.
We know that $\alpha, \beta$ also has unique prime factorizations.
We also know that $k\nmid l$, so $k$ and $l$ does not share any prime factors.
So if $k=p_1^ap_2^b...$ then $l$ does not have $p_1$ nor $p_2$ in the prime factorization. So $n$ contains both prime factors from $k$ and $l$ which are independent of each other? Is that a reasonable way of reasoning?

 

[fresh_42]

Thank you! I got a little further thanks to this but I'm still not all the way there.
Let me just double check that you could write $2\,|\,n^2 \Longrightarrow 2\,|\,n$ because $2$ is prime so $2|n\cdot n$ but $2$ can only divide $n$. Is that because that $n^2$ has one unique prime factorization, where each (relevant) prime number (potentially raised to an exponent) appears once?

No. It is by definition of a prime number. A number is prime if in case it divides a product then it divides one of the factors (see post #2). Numbers that cannot be factored are called irreducible (school definition of a prime number). That irreducible numbers are prime and prime numbers are irreducible is a theorem. It should be in your textbook or lecture notes. It is usually one of the first theorems that is proven after the two definitions. The definition of prime numbers $p$, however, is that $p\neq \pm 1$ and $p\,|\,ab \Longrightarrow p\,|\,a \text{ or }p\,|\,b.$ Since $2$ is prime and divides $10$ we have $2\,|\,10\,|\,n^2=n\cdot n$ and by the definition of a prime number we get $2\,|\,n.$ The same holds for the prime number $5$
$$
5\,|\,10\,|\,n^2=n\cdot n \Longrightarrow 5\,|\,n
$$

For the proof, I'm quite unsure where to start, but what I thought about is that:
We know that $k$, $l$ has unique prime factorizations dues to the fundamental theorem of arithmetic.
We know that $k|n\implies n=\alpha k, l|n\implies n=\beta l, \text{ where }\alpha, \beta \in \mathbb Z$.
We know that $\alpha, \beta$ also has unique prime factorizations.
We also know that $k\nmid l$, so $k$ and $l$ does not share any prime factors.

We need the stronger requirement that $k$ and $l$ don't have any prime factor in common, which is called $k$ and $l$ are coprime or $\operatorname{gcd}(k,l)=1.$ $k\nmid l$ alone is not sufficient. E.g. $6\nmid 9$ but $6$ and $9$ are not coprime since they share the factor $3.$

So if $k=p_1^ap_2^b...$ then $l$ does not have $p_1$ nor $p_2$ in the prime factorization. So $n$ contains both prime factors from $k$ and $l$ which are independent of each other? Is that a reasonable way of reasoning?

Yes. That's the idea. You can list all prime factors of $n,$ say $P_n=\{p_1,\ldots,p_m\}$ and some are also prime factors of $k$ and others prime factors of $l.$ Since $k$ and $l$ have no prime factors in common, those sets are disjoint subsets of $P_n$ and their union is still a subset of $P_n$ so $k\cdot l\,|\,n.$

It does not work if they share a common prime because we would need two of them for $k\cdot l\,|\,n$ and there is no guarantee that it occurs twice in $P_n.$

Did you find a counterexample for $9\,|\,n^2$ but $9\,\nmid\,n\;$?

 

[fresh_42]

Another idea is using Bézout's Lemma. It states that we can write $s\cdot k + t\cdot l =\operatorname{gcd}(k,l)$ for any two numbers $k,l.$ It is basically the Euclidean algorithm, i.e. ordinary division. In our case, we get $s\cdot k + t\cdot l=1$ since $k$ and $l$ are coprime. Now take $n=\beta\cdot l$ and consider everything modulo $k.$

 

[bremenfallturm]

A number is prime if in case it divides a product then it divides one of the factors

Ah yes, of course it's by definition. I think I'm so used to hearing "a number is prime if only divisible by itself and 1" but of course it follows from that what you wrote.

Did you find a counterexample for 9|n2 but 9∤n?

Well, we can write $9=3\cdot 3$ but $9\nmid 3$, as a simple example.

We need the stronger requirement that k and l don't have any prime factor in common

I see, thanks to your trivial example as well.
Is that what was missing from my reasoning or is there more I was missing?
I tried to reason again and ended up with this reasoning:

(^looks like the "t" in "not" slipped of and fell down in the image above, sorry about that!)

So I can see that we can see that $P_{n^2}$ consists of all factors in both $P_k$ and $P_l$ and I wrote down the definition of a prime number. But I am now just a little unsure about how I can apply the definition to conclude that $P_n$ contains all factors in both $P_k$ and $P_l$.

Thanks for help with the final push!

 

[fresh_42]

Ah yes, of course it's by definition. I think I'm so used to hearing "a number is prime if only divisible by itself and 1" but of course it follows from that what you wrote.

That is the definition of irreducible numbers, numbers that cannot be reduced to proper factors (except $\pm 1$ of course). Irreducible integers are prime and vice versa. This is not true for some other number systems so it makes sense to distinguish the two properties. The true definition of a prime number $p\neq \pm 1$ is
$$
p\,|\,(a\cdot b) \Longrightarrow p\,|\,a \text{ or } p\,|\,b
$$
which is more convenient in proofs about congruences.

Well, we can write $9=3\cdot 3$ but $9\nmid 3$, as a simple example.

A better example is $36.$ We have $9\,|\,36=6\cdot 6$ but $9\,\nmid\,6.$ Hence $9$ is not prime.

We cannot know whether $d$ is prime or not. But partitioning the the prime factors of $n$ into arrays of prime factors of $k$ and prime factors of $l$ and the rest works.

It is usually more convenient in algebra to use indirect proofs. We want to show
$$
k\,|\,n \text{ and }l\,|\,n \text{ and }\operatorname{gcd}(k,l)=1 \Longrightarrow (k\cdot l)\,|\,n
$$
Assume that $(k\cdot l)\,\nmid \,n.$ Then there is a factor $d\,|\,(k\cdot l)$ such that $d\,\nmid\,n.$ Then there is a prime power $p^q$ that divides $d$ but does not divide $n.$ From $p\,|\,p^q\,|\,d\,|\,(k\cdot l)$ we get by the definition of a prime number $p$ that $p\,|\,k$ or $p\,|\,l.$ Now, if even $p^q\,|\,k$ then $p^q\,|\,k\,|\,n$ and likewise $p^q\,|\,l\,|\,n$ which we excluded. Hence $p^r\,|\,k$ for some $q>r>0$ and $p^s\,|\,l$ for some $q>s>0.$ But then $p\,|\,k$ and $p\,|\,l$ which contradicts the condition that $k$ and $l$ are coprime.

I know I got dizzy, too, while writing it. But that is how such proofs in abstract algebra usually work. The problem here was to reduce the situation from $d$ to a prime $p$ so that I could use the definition of primality which $p$ has and $d$ does not. The principle I used here is called the pigeonhole principle. It is about distributing more pigeons than there are holes (or the other way around).

I see, thanks to your trivial example as well.
Is that what was missing from my reasoning or is there more I was missing?
I tried to reason again and ended up with this reasoning:
View attachment 351568
(^looks like the "t" in "not" slipped of and fell down in the image above, sorry about that!)

View attachment 351569
So I can see that we can see that $P_{n^2}$ consists of all factors in both $P_k$ and $P_l$ and I wrote down the definition of a prime number. But I am now just a little unsure about how I can apply the definition to conclude that $P_n$ contains all factors in both $P_k$ and $P_l$.

Keep the example of $9\,|\,36$ in mind. I have proven a different statement, namely that if two coprime numbers divide another number $n$ then their product also divides $n$. This is enough to conclude
\begin{align*}
10\,|\,n^2 &\Longrightarrow 2\,|\,10\,|\,n^2=n\cdot n\text{ and }5\,|\,10\,|\,n^2=n\cdot n\\
&\Longrightarrow 2\,|\,n\text{ and } 5\,|\,n \text{ since } 2 \text{ and }5\text{ are prime}\\
&\Longrightarrow (2\cdot 5)\,|\,n\text{ since } 2 \text{ and }5 \text{ are coprime}
\end{align*}
Operating with $n^2$ instead makes the situation unnecessarily complicated. We only need to consider the prime factors of $n.$

The other proof is with Bézout's lemma. It is shorter and far less dizzy. It states that there are always integers $s,t$ such that
$$
\operatorname{gcd}(k,l)= s\cdot k + t\cdot l
$$
Are we allowed to use this theorem?