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

In summary, the statement "10|n^2 implies 10|n" holds because if \( n^2 \) is divisible by 10, then \( n \) must also contain the prime factors of 10 (2 and 5) to ensure \( n^2 \) is divisible by both. Conversely, "9|n^2 does not imply 9|n" is true because while \( n^2 \) being divisible by 9 means \( n \) must be divisible by 3 (the square root of 9), it does not guarantee \( n \) itself contains both factors of 3 needed for \( 9 \) (which is \( 3^2 \)). Thus, \(
  • #1
bremenfallturm
57
11
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!
 
Physics news on Phys.org
  • #2
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!
 
  • #3
fresh_42 said:
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?
 
  • #4
bremenfallturm said:
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
$$
bremenfallturm said:
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.##
bremenfallturm said:
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\;##?
 
  • #5
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.##
 
  • #6
fresh_42 said:
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.
fresh_42 said:
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.
fresh_42 said:
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:
1727423504440.png

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

1727423523414.png

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!
 
  • #7
bremenfallturm said:
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.
bremenfallturm said:
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).

bremenfallturm said:
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?
 
Last edited:

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

1. What does it mean for a number to divide another number?

In mathematics, we say that a number \( a \) divides another number \( b \) (written as \( a|b \)) if there exists an integer \( k \) such that \( b = ak \). This means that when \( b \) is divided by \( a \), there is no remainder.

2. Why does \( 10|n^2 \) imply that \( 10|n \)?

If \( 10|n^2 \), then \( n^2 \) can be expressed as \( n^2 = 10k \) for some integer \( k \). Since \( 10 = 2 \times 5 \), both \( 2 \) and \( 5 \) must divide \( n^2 \). If a prime number divides a square of an integer, it must also divide the integer itself. Therefore, both \( 2 \) and \( 5 \) divide \( n \), which means \( 10|n \).

3. Why doesn't \( 9|n^2 \) imply that \( 9|n \)?

For \( 9|n^2 \), we can express \( n^2 = 9k \) for some integer \( k \). The number \( 9 \) can be factored into \( 3^2 \). While \( 3^2 \) divides \( n^2 \), it does not guarantee that \( 3 \) divides \( n \). For instance, if \( n = 3 \), then \( n^2 = 9 \), but if \( n = 6 \), then \( n^2 = 36 \) which is divisible by \( 9 \), yet \( n = 6 \) is not divisible by \( 9 \). Therefore, \( 9|n^2 \) does not imply \( 9|n \).

4. Can you provide an example where \( 10|n^2 \) but not \( 10|n \)?

No, there is no integer \( n \) for which \( 10|n^2 \) is true while \( 10|n \) is false. If \( 10|n^2 \), it must follow that \( n \) is divisible by both \( 2 \) and \( 5 \), hence \( 10|n \) must also hold. This is a direct consequence of the properties of prime factorization.

5. What is the significance of understanding these divisibility rules?

Understanding these divisibility rules helps in number theory and algebra, especially

Similar threads

Prove ##|\{ q\in\mathbb{Q}: q>0 \} |=|\mathbb{N}|##.
Replies
3
Views
1K
Relatively prime proof involving a^n and b^n
Replies
3
Views
1K
Stuck on Proof by induction of 2^n>n^3 for all n>=10
Replies
4
Views
7K
24 divides m if n^2 -m and n^2 +m are perfect squares
Replies
2
Views
2K
Convergence of 10^-2^n. Linear, quadratic, cubic, quartic, hectic
Replies
10
Views
4K
B Extending the Fundamental Theorem of Arithmetic to the rationals
2
Replies
35
Views
4K
Integer Number Theory - n = p + a^2
Replies
4
Views
2K
Proof by induction: 5^n + 9 < 6^n for all integers n≥2
Replies
4
Views
14K
(for fun) Any non-perfect square has an irrational 2nd root
Replies
1
Views
2K
Show that square root of 3 is an irrational number
Replies
1
Views
1K

Hot Threads

Recent Insights

Back
Top