B Is the Proof for If a Divides b^2, then a Divides b Correct?

[MandelbrotI]

I was trying to find a proof concerning this statement, but I couldn't find anything. I have tried to come up with my own solution:

If a divides b^2, that means that :

a*x=b^2
a*(x/b) = b

This shows that b is divisible by a. Is this correct?

 

[BvU]

Hello Mandebroti,

Is this correct?

Not if x/b is not an integer, so you still have to prove that.

 

[member 587159]

I'm sorry. This is incorrect. Your mistake was that you assumed that $x/b$ was an integer.

Counterexample:

a = 9, b = 3

Then, obviously 9 divides 3^2, but 9 does not divide 3.

 

[MandelbrotI]

Hello Mandebroti,
Not if x/b is not an integer, so you still have to prove that.

Do you have a proof for that?
Maybe this works:

a*x=b^2
With the rule that a and b have to be integers, b can be split up into primes:
b=p1*p2*...pn

Using that for b^2:

a*x=p1*p1*p2*p2...pn*pn

We see that a has to divide one of these prime factors. And all of these factors can be found in b, so when
a divides, for example, py, then a divides b aswell.

 

[member 587159]

Do you have a proof for that?
Maybe this works:

a*x=b^2
With the rule that a and b have to be integers, b can be split up into primes:
b=p1*p2*...pn

Using that for b^2:

a*x=p1*p1*p2*p2...pn*pn

We see that a has to divide one of these prime factors. And all of these factors can be found in b, so when
a divides, for example, py, then a divides b aswell.

Please check my example above. This is not generally true.

 

[Mark44]

Another example (counterexample) is if b = 6 = 2 * 3, and a = 4. a | b², since 4 divides 36, but a doesn't divide b.

 

[MandelbrotI]

Please check my example above. This is not generally true.

I see that problem. The thing is, this statement is used by many people to proof that the square root of 2 is irrational.

sqr(2) = a/b
2 = a^2/b^2
2*b^2 = a^2

At this point, it says: 2 divides a^2, so 2 divides a -> a = 2* some variable. I assumed this is correct.
Of course, this is true as a square number can only be even if the original number is even. But this was used for square root 3 aswell. Anyways, is there another way to prove this? Is it necessary to define a such that a<b?

https://de.khanacademy.org/math/alg...hat-square-root-of-prime-number-is-irrational

 

[Mark44]

I see that problem. The thing is, this statement is used by many people to proof that the square root of 2 is irrational.

sqr(2) = a/b
2 = a^2/b^2
2*b^2 = a^2

At this point, it says: 2 divides a^2, so 2 divides a -> a = 2* some variable. I assumed this is correct.

I don't see how this is related to your original problem.
In the proof above, one assumption is that a/b is in reduced form; i.e., that a and be don't have any common factors.

In the last equation above, $2b^2 = a^2$, since there is a factor of 2 on the left side, there must also be a factor of 2 on the right side. But, since the right side is $a^2$, there can't be just a single factor of 2 -- there must be two factors of 2, so there must be an additional factor of 2 in $2b^2$ (in addition to the coefficient 2). That can't be, because of the assumption that a and b don't share common factors, so we reach a contradiction.

Of course, this is true as a square number can only be even if the original number is even. But this was used for square root 3 aswell. Anyways, is there another way to prove this? Is it necessary to define a such that a<b?

https://de.khanacademy.org/math/alg...hat-square-root-of-prime-number-is-irrational

 

[MandelbrotI]

Yes, the proof uses contradiction. But this contradiction only works, because, when p divides a², p also divides a. So p divides a and b -> contradiction. But for that to happen, the statement that when x divides y², x divides y, also has to be true. Only because of this you can say, that they share factors, which leads to a contradiction.

 

[member 587159]

Yes, the proof uses contradiction. But this contradiction only works, because, when p divides a², p also divides a. So p divides a and b -> contradiction. But for that to happen, the statement that when x divides y², x divides y, also has to be true. Only because of this you can say, that they share factors, which leads to a contradiction.

But, how can it be true if we gave you 2 valid counterexamples? Obviously, there is a flaw in your reasoning.

 

[MandelbrotI]

But, how can it be true if we gave you 2 valid counterexamples? Obviously, there is a flaw in your reasoning.

It is the reasoning of multiple "proofs" on the internet, including the video I posted.

 

[Mark44]

It is the reasoning of multiple "proofs" on the internet, including the video I posted.

Which is really irrelevant. If you make a general statement, such as the one in post #1, and others offer counterexamples, then your statement isn't true, regardless of whether there are proofs on the internet.

Either the proofs themselves are wrong, or you have misunderstood what it was that was being proved in the videos. I hope that it is now abundantly clear that if $a | b^2$, then it does not imply that $a | b$. We have provided several counterexamples that disprove this.

 

[MandelbrotI]

Which is really irrelevant. If you make a general statement, such as the one in post #1, and others offer counterexamples, then your statement isn't true, regardless of whether there are proofs on the internet.

Either the proofs themselves are wrong, or you have misunderstood what it was that was being proved in the videos. I hope that it is now abundantly clear that if $a | b^2$, then it does not imply that $a | b$. We have provided several counterexamples that disprove this.

Then the proofs on the internet are wrong. Thanks, the first insight I gained so far.

 

[SlowThinker]

Then the proofs on the internet are wrong. Thanks, the first insight I gained so far.

You learned the wrong lesson. The proofs are correct.
Notice that the proofs don't work for any square root, for example, sqrt(4) is an integer.

 

[MandelbrotI]

You learned the wrong lesson. The proofs are correct.
Notice that the proofs don't work for any square root, for example, sqrt(4) is an integer.

Yes, only for prime numbers.

 

[SlowThinker]

Yes, only for prime numbers.

I'd say it applies to $\sqrt 6$ too. You should spend some time thinking before jumping to conclusions.

 

[MandelbrotI]

I'd say it applies to $\sqrt 6$ too. You should spend some time thinking before jumping to conclusions.

Fine. I still don't understand, which part of any proof here is correct. I came with the question whether my proof is correct. Seemingly it is not. I tried another approach, still no conclusions. Both of these statements are used in various proofs on the internet. You tell me, they are correct. The others told me, they aren't.

 

[Mark44]

Fine. I still don't understand, which part of any proof here is correct. I came with the question whether my proof is correct. Seemingly it is not. I tried another approach, still no conclusions. Both of these statements are used in various proofs on the internet. You tell me, they are correct. The others told me, they aren't.

Here is what you posted to start this thread:

I was trying to find a proof concerning this statement, but I couldn't find anything. I have tried to come up with my own solution:
If a divides b^2, that means that :

a*x=b^2
a*(x/b) = b
This shows that b is divisible by a. Is this correct?

In a nutshell your work above purports to prove that "II a divides b², then a divides b"
More specifically, the proposition is "∀ a > 0, ∀ b > 0, a | b² ⇒ a | b, where a and b are positive integers"
The "for all" qualifiers mean that regardless of the choices of a and b, the statement must be true. The counterexamples provided already in this thread are sufficient to show that the statement is not true in general.

In your work above, I'm not sure you fully understand what "divides" means in the context of this problem. When someone says that a divides b (in symbols a | b), it means that there is some integer k such that ka = b. For example, 2 | 6, because 2 * 3 = 6. 2 does not divide 7 because there is no integer k such that 2 * k = 7.

In your work above, given that a | b², there is some integer x such that a * x = b². In your next step, you divided both sides of this equation by b, getting $a \frac x b = b$. There is no guarantee that $\frac x b$ is an integer, and that is where your "proof" falls down.

 

[MandelbrotI]

Here is what you posted to start this thread:

​

In a nutshell your work above purports to prove that "II a divides b², then a divides b"
More specifically, the proposition is "∀ a > 0, ∀ b > 0, a | b² ⇒ a | b, where a and b are positive integers"
The "for all" qualifiers mean that regardless of the choices of a and b, the statement must be true. The counterexamples provided already in this thread are sufficient to show that the statement is not true in general.

In your work above, I'm not sure you fully understand what "divides" means in the context of this problem. When someone says that a divides b (in symbols a | b), it means that there is some integer k such that ka = b. For example, 2 | 6, because 2 * 3 = 6. 2 does not divide 7 because there is no integer k such that 2 * k = 7.

In your work above, given that a | b², there is some integer x such that a * x = b². In your next step, you divided both sides of this equation by b, getting $a \frac x b = b$. There is no guarantee that $\frac x b$ is an integer, and that is where your "proof" falls down.

I appreciate your answer, and understand, that there are either certain guidelines a and b have to follow, or the proof is incorrect. In my initial statement, I left out an important detail. a and b can't share the same factors. This could lead to the proof being correct, as all counterexamples have a's and b's that share factors.
Anyways, what about the proof using prime factors, to show that 2, or specifically p, divides a and b, which creates a contradiction.

 

[SlowThinker]

Fine. I still don't understand, which part of any proof here is correct. I came with the question whether my proof is correct. Seemingly it is not. I tried another approach, still no conclusions. Both of these statements are used in various proofs on the internet. You tell me, they are correct. The others told me, they aren't.

In my opinion, the mistake you are making, is that you see a proof using number 2, and generalize it to any number $a$, which is not justified. The proof works for many numbers $a$, but not for all.
Can you figure out the condition that $a$ must satisfy, so that a | b² ⇒ a | b ?

 

[Mark44]

In my initial statement, I left out an important detail. a and b can't share the same factors.

That's a very important detail. Two of the counterexamples given in this thread, with a = 9, b = 3 and a = 4, b = 6 are no longer counterexamples with this restriction in place.

 

[MandelbrotI]

In my opinion, the mistake you are making, is that you see a proof using number 2, and generalize it to any number $a$, which is not justified. The proof works for many numbers $a$, but not for all.
Can you figure out the condition that $a$ must satisfy, so that a | b² ⇒ a | b ?

I am aware, that you can't generalise something with just one example being given. However, I assumed this in the first place, because I have already seen this way of proving the irrationality of primes with sqrt(2), sqrt(3) and others.

At the start of this proof, we assume that sqrt(2) (or sqrt(p)) is rational, so we define sqrt(p) as the quotient of a and b, with the fracture in it's smallest form. I guess, the only condition to satisfy is, that a and b are integers and don't share any factors.

 

[SlowThinker]

At the start of this proof, we assume that sqrt(2) (or sqrt(p)) is rational, so we define sqrt(p) as the quotient of a and b, with the fracture in it's smallest form. I guess, the only condition to satisfy is, that a and b are integers and don't share any factors.

Yes but a and b not sharing any factors, is the same as the fraction a/b being in its reduced form.
There is also a condition that p must satisfy. As I said before, $\sqrt 4$ is an integer. The condition is not that p is a prime, because it correctly proves that $\sqrt 6$ is irrational.

 

[MandelbrotI]

Yes but a and b not sharing any factors, is the same as the fraction a/b being in its reduced form.
There is also a condition that p must satisfy. As I said before, $\sqrt 4$ is an integer. The condition is not that p is a prime, because it correctly proves that $\sqrt 6$ is irrational.

Yes, I tried to say, that because of a/b is in it's smallest form, this automatically means a and b don't share any factors. But I can't think of a condition, the variable in the square root has to satisfy.

 

[SlowThinker]

Yes, I tried to say, that because of a/b is in it's smallest form, this automatically means a and b don't share any factors. But I can't think of a condition, the variable in the square root has to satisfy.

Ok so I finally watched the KhanAcademy video, and it has the proof that if p is a prime that divides $b^2$, then p divides $b$. You just incorrectly generalized it to all integer p.

With that explained, can you repeat what was your original question? Do you have trouble understanding the reasoning in the video? You aren't looking for all p for which the proof is valid, are you?

 

[MandelbrotI]

Ok so I finally watched the KhanAcademy video, and it has the proof that if p is a prime that divides $b^2$, then p divides $b$. You just incorrectly generalized it to all integer p.

With that explained, can you repeat what was your original question? Do you have trouble understanding the reasoning in the video? You aren't looking for all p for which the proof is valid, are you?

p was supposed to stand for prime... And no, no questions anymore.