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

  • B
  • Thread starter MandelbrotI
  • Start date
In summary, the conversation discusses a proof for the statement that if a divides b^2, then a also divides b. The original claim is proven to be incorrect with two counterexamples provided. The conversation then moves on to a different topic, discussing the proof that the square root of a prime number is irrational. However, further analysis reveals a flaw in the reasoning of this proof as well.
  • #1
MandelbrotI
12
0
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?
 
Mathematics news on Phys.org
  • #2
Hello Mandebroti, :welcome:
MandelbrotI said:
Is this correct?
Not if x/b is not an integer, so you still have to prove that.
 
  • #3
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.
 
  • #4
BvU said:
Hello Mandebroti, :welcome:
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.
 
  • #5
MandelbrotI said:
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.
 
  • #6
Another example (counterexample) is if b = 6 = 2 * 3, and a = 4. a | b2, since 4 divides 36, but a doesn't divide b.
 
  • #7
Math_QED said:
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
 
Last edited:
  • #8
MandelbrotI said:
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.
MandelbrotI said:
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
 
  • #9
Yes, the proof uses contradiction. But this contradiction only works, because, when p divides a2, p also divides a. So p divides a and b -> contradiction. But for that to happen, the statement that when x divides y2, x divides y, also has to be true. Only because of this you can say, that they share factors, which leads to a contradiction.
 
  • #10
MandelbrotI said:
Yes, the proof uses contradiction. But this contradiction only works, because, when p divides a2, p also divides a. So p divides a and b -> contradiction. But for that to happen, the statement that when x divides y2, 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.
 
  • #11
Math_QED said:
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.
 
  • #12
MandelbrotI said:
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.
 
  • #13
Mark44 said:
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.
 
  • #14
MandelbrotI said:
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.
 
  • #15
SlowThinker said:
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.
 
  • #16
MandelbrotI said:
Yes, only for prime numbers.
I'd say it applies to ##\sqrt 6## too. You should spend some time thinking before jumping to conclusions.
 
  • #17
SlowThinker said:
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.
 
  • #18
MandelbrotI said:
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:
MandelbrotI said:
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 b2, then a divides b"
More specifically, the proposition is "∀ a > 0, ∀ b > 0, a | b2 ⇒ 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 | b2, there is some integer x such that a * x = b2. 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.
 
  • #19
Mark44 said:
Here is what you posted to start this thread:
In a nutshell your work above purports to prove that "II a divides b2, then a divides b"
More specifically, the proposition is "∀ a > 0, ∀ b > 0, a | b2 ⇒ 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 | b2, there is some integer x such that a * x = b2. 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.
 
  • #20
MandelbrotI said:
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 | b2 ⇒ a | b ?
 
  • #21
MandelbrotI said:
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.
 
  • #22
SlowThinker said:
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 | b2 ⇒ 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.
 
  • #23
MandelbrotI said:
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.
 
  • #24
SlowThinker said:
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.
 
  • #25
MandelbrotI said:
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?
 
  • #26
SlowThinker said:
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.
 

1. Can you explain the statement "If a divides b^2, a divides b"?

This statement means that if a number, called "a", divides the square of another number, called "b", then it also divides the original number, b. In other words, if b is a multiple of a squared, then b is also a multiple of a.

2. Why is this statement important in mathematics and science?

This statement is important because it is a fundamental property of divisibility and is used in many mathematical and scientific concepts. It helps in simplifying equations and finding common factors, which are crucial in solving problems in various fields such as algebra, number theory, and cryptography.

3. Can you provide an example of how this statement is used in practical applications?

One practical example is in the field of cryptography, where this statement is used in the RSA algorithm for encrypting and decrypting messages. In this algorithm, the security of the encryption relies on the fact that it is difficult to factorize large numbers, which is made possible by this statement.

4. Is this statement always true?

Yes, this statement is always true. It is a mathematical law known as the "division algorithm" and can be proven using basic principles of divisibility and prime factorization.

5. Are there any conditions or exceptions to this statement?

The statement is only valid for integers and does not apply to non-integer numbers. Additionally, if a and b are relatively prime (have no common factors except for 1), then a may not necessarily divide b^2. In all other cases, the statement holds true.

Similar threads

  • General Math
2
Replies
47
Views
3K
Replies
19
Views
2K
  • General Math
2
Replies
66
Views
4K
Replies
1
Views
866
  • General Math
Replies
11
Views
1K
  • General Math
Replies
22
Views
1K
Replies
13
Views
1K
  • General Math
Replies
3
Views
1K
Replies
18
Views
2K
Back
Top