Simple number theory, divisibility

[TheFurryGoat]

Can you help me with this problem:
if a^2 divides b^2, show that a divides b.

This was a homework question that I had a while ago and it was solved by using the fundamental theorem of arithmetic.

I instead tried to solve it with proof by contradiction:
a^2 divides b^2 implies a divides b^2
counterassumption: a does not divide b => b = q*a + r, 0< r < a

Now b^2 = q^2*a^2 + 2qar + r^2, now a divides q^2*a^2 and 2qar, but what about r^2.

At this part I got confused, and went out for a beer.
Can you help with this?

 

[HallsofIvy]

Can you help me with this problem:
if a^2 divides b^2, show that a divides b.

This was a homework question that I had a while ago and it was solved by using the fundamental theorem of arithmetic.

I instead tried to solve it with proof by contradiction:
a^2 divides b^2 implies a divides b^2.

You mean "a divides b"

counterassumption: a does not divide b => b = q*a + r, 0< r < a

Now b^2 = q^2*a^2 + 2qar + r^2, now a divides q^2*a^2 and 2qar, but what about r^2.

At this part I got confused, and went out for a beer.
Can you help with this?

The point is to prove that a² does NOT divide that!

 

[rrronny]

Let $$v_p(\cdot)$$ denote the p-adic valuation (see http://en.wikipedia.org/wiki/Valuation_(algebra)#p-adic_valuation").
$$a \nmid b \iff v_p(\frac{b}{a})=v_p(b)-v_p(a)<0$$
Then:
$$v_p(\frac{b^2}{a^2})=2[v_p(b)-v_p(a)]<0 \iff a^2 \nmid b^2$$

 

[Office_Shredder]

This is obviously beyond the scope of the exercise rrronny. Moving to a more realistic view:

Now b^2 = q^2*a^2 + 2qar + r^2, now a divides q^2*a^2 and 2qar, but what about r^2.

a divides q²*a² + 2qar + r² if and only if a divides r². See if you can figure out why

As your goal is a proof by contradiction, your objective in the proof then is to prove that a does not divide r² using only the fact that r<a.

 

[TheFurryGoat]

Let $$v_p(\cdot)$$ denote the p-adic valuation (see http://en.wikipedia.org/wiki/Valuation_(algebra)#p-adic_valuation").
$$a \nmid b \iff v_p(\frac{b}{a})=v_p(b)-v_p(a)<0$$
Then:
$$v_p(\frac{b^2}{a^2})=2[v_p(b)-v_p(a)]<0 \iff a^2 \nmid b^2$$

rrronny, I think you are using the fundamental theorem of arithmetic or Unique-Prime-Factorization Theorem here...

I was hoping to go around it some how.

counter axample: a=4, b=6 => r=2, now 4 divides 16 + 4*2*2 + 2^2

Obviously I have to contradict with a^2 doesn't divide the eaquation.

 

[TheFurryGoat]

I've got it. There is nothing special about it:
Let b = ka + r and
b^2 = k^2*a^2 + 2akr + r^2.

Now a^2 | b^2 <=> b^2 = q*a^2 => r^2 + 2akr + k^2*a^2 = q*a^2

Rearranging we get
r^2 + 2akr + (k^2-q)a^2 = 0,

Now r = ½(-2ak + sqrt[4a^2*k^2 - 4(k^2 - q)a^2]),
we take 4a^2 out of the square root

= ½(-2ak + 2a*sqrt[k^2 - k^2 + q]) = a(k + sqrt(q)).
But r cannot be greater than a.

 

[ramsey2879]

I've got it. There is nothing special about it:
Let b = ka + r and
b^2 = k^2*a^2 + 2akr + r^2.

Now a^2 | b^2 <=> b^2 = q*a^2 => r^2 + 2akr + k^2*a^2 = q*a^2

Rearranging we get
r^2 + 2akr + (k^2-q)a^2 = 0,

Now r = ½(-2ak + sqrt[4a^2*k^2 - 4(k^2 - q)a^2]),
we take 4a^2 out of the square root

= ½(-2ak + 2a*sqrt[k^2 - k^2 + q]) = a(k + sqrt(q)).
But r cannot be greater than a.

r = a(sqrt(q) - k) but the proof seems correct otherwise. 0<r<a

 

[TheFurryGoat]

r = a(sqrt(q) - k) but the proof seems correct otherwise. 0<r<a

Well, actually nothing stops sqrt(q)-k being smaller than 1. I think the Division algorithm is not quite enough for this problem.

 

[ramsey2879]

Well, actually nothing stops sqrt(q)-k being smaller than 1. I think the Division algorithm is not quite enough for this problem.

since r = a(sqrt(q)-k) = b-ak we have a*sqrt(q) = b. Since a<b are integers then sqrt(q) = m/n where m and n are coprime integers.

am=nb. But "a" does not divide n because if it did then the a's cancel out in the formula b^2 = a^2m^2/n^2. The only answer is that "a" must divide b. Or is that based on the fundamental theorem of arithmetic again.

 

[Bingk]

How about this:

Given $$a^2|b^2$$

Assume $$a \nmid b \Rightarrow a^2 \nmid b^2$$

We have our contradiction

The other thing you could do is:

$$a^2|b^2 \Rightarrow ma^2=b^2$$

Since a and b are square numbers, m must be a square number also

let $$n^2=m$$

$$n^2a^2=b^2$$
$$(na)^2=b^2$$
$$na=b \Rightarrow a|b$$

That's basically working backwards ($$a|b \Rightarrow a^2|b^2$$)

 

[TheFurryGoat]

since r = a(sqrt(q)-k) = b-ak we have a*sqrt(q) = b. Since a<b are integers then sqrt(q) = m/n where m and n are coprime integers.

am=nb. But "a" does not divide n because if it did then the a's cancel out in the formula b^2 = a^2m^2/n^2. The only answer is that "a" must divide b. Or is that based on the fundamental theorem of arithmetic again.

I would never have thought of doing that. Very nice!
I checked out all the possibilities and I came up with a problem:

If n=a => m = b but a^2 | b^2 so b^2/a^2 is an integer and so forth.
I couldn't disprove this situation (as well as if n | a)

Bingk: Can you walk me through your implications? I wasn't able to prove these myself.

 

[Bingk]

Not sure which part you want me to walk you through, so I'll go over everything ... and I just noticed that I'll have to make a slight modification :), which you'll see later.

If a|b, then there exists an integer (say n) such that na = b (by definition of divisibility) => (na)^2 = b^2 => a^2|b^2

So, if a$$\nmid$$b, then there doesn't exist an integer such that na = b, and so we can't get (na)^2 = b^2 ... so a^2$$\nmid$$b^2.


The other way is this:

a^2|b^2 => there exists an integer (say m) such that ma^2 = b^2

Since b^2 is a square number, m must be an even powered number, say n^(2k). If it's not of an even power, then when you take the square roots, you'll get an irrational number, but b is an integer, so we have a contradiction. Thus, it must be of an even power.

So, n^(2k)*a^2 = b^2
(n^k * a)^2 = b^2
n^k * a = b => a|b

 

[Bingk]

since r = a(sqrt(q)-k) = b-ak we have a*sqrt(q) = b. Since a<b are integers then sqrt(q) = m/n where m and n are coprime integers.

am=nb. But "a" does not divide n because if it did then the a's cancel out in the formula b^2 = a^2m^2/n^2. The only answer is that "a" must divide b. Or is that based on the fundamental theorem of arithmetic again.

I have some questions about this.

1) How did you get that a<b? I can get that a$$\leq$$b since we're trying to show that a|b. But the division algorithm doesn't say that a<b, and it still works, if a>b.
What you do get though, is that if a>b, then k<0, and so we get r = a(sqrt(q)+|k|) ... (that's the absolute value of k), and Furry's contradiction (r can't be greater than a) works. As for the case when a<b, recall that

r^2 + 2akr + k^2*a^2 = q*a^2 => q*a^2$$\geq$$k^2*a^2 => q$$\geq$$k^2 => sqrt(q)$$\geq$$k

when sqrt(q)=k, we have that r = 0, and obviously a divides be since we will have b = ka + 0
when sqrt(q)>k, we have that r>a, which is another contradiction ... so it still works.

2) You need to clarify ... if a divides n, what's wrong if the a's cancel out? You'd be left with b^2 = m^2 / j^2, where aj = n. And all this says is that b^2|m^2 and j^2|m^2

3) Why did you let sqrt(q) = m/n (with m and n coprime) to begin with? this implies that q = m^2 / n^2 ... and since m and n are coprime, m^2 /n^2 is not an integer ... so q is not even an integer, which is a contradiction.
I think if we modify it abit, we come out with the same thing that I was saying ... since a*sqrt(q) = b, sqrt(q) must be an integer => q is a square number. But we don't even need that, we can straight away say let Y=sqrt(q) => aY = b => a|b :)

 

[TheFurryGoat]

Not sure which part you want me to walk you through, so I'll go over everything ... and I just noticed that I'll have to make a slight modification :), which you'll see later.

If a|b, then there exists an integer (say n) such that na = b (by definition of divisibility) => (na)^2 = b^2 => a^2|b^2

So, if a$$\nmid$$b, then there doesn't exist an integer such that na = b, and so we can't get (na)^2 = b^2 ... so a^2$$\nmid$$b^2.

This part seemed to be a bit too trivial... The proof seems to assume quite a lot and I'm not sure which part is bothering me.

The other way is this:

a^2|b^2 => there exists an integer (say m) such that ma^2 = b^2

Since b^2 is a square number, m must be an even powered number, say n^(2k).

where do we know this from?

 

[Bingk]

There's nothing wrong with trivial :) ... if you want, you can look at the prime factorization of a and b. So basically n contains all the prime factors missing from a to make it equal to b. If a does not divide b, it means that a contains at least one prime which is not in b, so no matter what you multiply a by, there will always be an extra prime that won't let them be equal (but if you multiplied b by that prime, then they could be equal). So, if you raise a to the power of 2, that extra prime is also raised to the power of 2, but it still isn't in b, so there's no way a^2 could divide b^2.

Assuming that a and b are integers, then a^2 and b^2 are integers. So, if a^2|b^2, then ma^2 = b^2. Now, we are allowed to take the square root of b^2, because that would give us an integer b ... so if we take the square root of (ma^2), we're left with a * sqrt(m) and since a and b are integers, sqrt(m) must be an integer. So, if we assume that m is an odd powered number, say m = n^(2k+1), if we take the square root of it, we get sqrt(m) = n^(k+1/2), and that half power will disable us from getting an integer, so sqrt(m) won't be an integer, which is a contradiction.

Also, just to be clear, n is a "reduced" number ... so things like 9^3 is actually 3^6 (i.e. (3^2)^3).

Hope that helps ...

 

[ramsey2879]

I have some questions about this.

1) How did you get that a<b?

I didn't since both m and n could be 1 as far as I am concerned. By "coprime" I meant reduced to their lowest form.

What you do get though, is that if a>b, then k<0, and so we get r = a(sqrt(q)+|k|) ... (that's the absolute value of k), and Furry's contradiction (r can't be greater than a) works.

I don't see how you got that.

2) You need to clarify ... if a divides n, what's wrong if the a's cancel out? You'd be left with b^2 = m^2 / j^2, where aj = n. And all this says is that b^2|m^2 and j^2|m^2

I think that the a's cancel out would contradict the premise that a^2|b^2

3) Why did you let sqrt(q) = m/n (with m and n coprime) to begin with? this implies that q = m^2 / n^2 ... and since m and n are coprime, m^2 /n^2 is not an integer ... so q is not even an integer, which is a contradiction.

Not if n|a

I think if we modify it abit, we come out with the same thing that I was saying ... since a*sqrt(q) = b, sqrt(q) must be an integer => q is a square number. But we don't even need that, we can straight away say let Y=sqrt(q) => aY = b => a|b :)

That would be true only if n = 1 and Y were an integer but how did you come to the conclusion that n = 1? The answer is that if n must divide a but if n were greater than 1 that would contradict the premise that a^2|b^2. Anyway TheFurryGoat is trying to avoid the use of the fundamental theorem of arithmetic. I don't think your proofs avoid the use of that nor do I think it is possible to give a proof that does not relie on it in some way.

 

[Bingk]

1) "Since a<b are integers then sqrt(q) = m/n where m and n are coprime integers" ... that's what you said, so I'm wondering how you got "since a<b" ... and I got what you meant by coprime :)

2) b = ka + r ... if a>b, then k = 0 (my mistake and r = b ... and from "r = a(sqrt(q) - k)" which Furry got, we get that r = a*sqrt(q) > a, so we still get the contradiction :).

3) Could you show how if the a's cancel out, it would contradict the premise that a^2|b^2?
This is what I get:
As you said, n|a, and if a|n => a = n => b^2 = m^2 => b = m => a = 1. I don't see any problems with a = 1, although it is a trivial case ...

4) By definition of division .. X|Y iff there exists and integer Z such that XZ = Y
So, if a^2|b^2, then there exists an INTEGER q such that qa^2 = b^2. If sqrt(q)=m/n (reduced fraction), then q = m^2/n^2 ... which is still a reduced fraction, so it's a rational number, not an integer, unless n = 1.
Yes, if n|a, then b is still an integer, but q itself is not an integer anymore (unless n = 1), so it still doesn't work unless n = 1.

5) I agree with your statement "The answer is that if n must divide a but if n were greater than 1 that would contradict the premise that a^2|b^2", that also works out, but for me, the reason n = 1 is because sqrt(q) is also an integer (so if we consider the set of rationals, then q is in the subset of the rationals in which the denominator is 1).

Please remember, this is in reference to this statement that you made:
"since r = a(sqrt(q)-k) = b-ak we have a*sqrt(q) = b. Since a<b are integers then sqrt(q) = m/n where m and n are coprime integers.

am=nb. But "a" does not divide n because if it did then the a's cancel out in the formula b^2 = a^2m^2/n^2. The only answer is that "a" must divide b. Or is that based on the fundamental theorem of arithmetic again."

Here's an example ...
36^2 = 1296 = (4^2 / 3^2) * 27^2 ... there, that example should work ... b = 36, a = 27, m = 4, and n = 3). I believe all your conditions are satisfied, n|a, m and n are relatively prime, and a does not divide n. Does a|b (27|36)?

My main problem is that in your proof, you did NOT indicate that n=1 (you just said that a does not divide n, which can be true), and the reason I find this to be a problem is that it contradicts the fact that q is an integer. That's how I get n=1, because if n is not 1, then q is not an integer. Another minor issue is that you did not include the special case where a|n and a|b, this is when a = n = 1, but again, you did not mention anything that says there would be a problem if n|a, with n>1.

6) Yes, my previous post did invoke the FTA, but just as another way you can look at it. Aside from that, I don't think the FTA needs to be invoked outright.

Example:
a and b are integers such that a^2|b^2 => ma^2 = b^2
Since the square root of b^2 = b, then we can take the sqrt(ma^2) = a*sqrt(m) = b.
Since a and b are integers, sqrt(m) must also be an integer
=> a|b

I don't see the FTA there ... and you could probably use the same idea for a^x|b^x => a|b

Furry, if you want, you can ask your teacher if he/she would find the above proof to be acceptable :) ... and if it's not, please let me know what he/she thinks is wrong with it :)

 

[ramsey2879]

1) "Since a<b are integers then sqrt(q) = m/n where m and n are coprime integers" ... that's what you said, so I'm wondering how you got "since a<b" ... and I got what you meant by coprime :)

2) b = ka + r ... if a>b, then k = 0 (my mistake and r = b ... and from "r = a(sqrt(q) - k)" which Furry got, we get that r = a*sqrt(q) > a, so we still get the contradiction :).

3) Could you show how if the a's cancel out, it would contradict the premise that a^2|b^2?
This is what I get:
As you said, n|a, and if a|n => a = n => b^2 = m^2 => b = m => a = 1. I don't see any problems with a = 1, although it is a trivial case ...

4) By definition of division .. X|Y iff there exists and integer Z such that XZ = Y
So, if a^2|b^2, then there exists an INTEGER q such that qa^2 = b^2. If sqrt(q)=m/n (reduced fraction), then q = m^2/n^2 ... which is still a reduced fraction, so it's a rational number, not an integer, unless n = 1.
Yes, if n|a, then b is still an integer, but q itself is not an integer anymore (unless n = 1), so it still doesn't work unless n = 1.

5) I agree with your statement "The answer is that if n must divide a but if n were greater than 1 that would contradict the premise that a^2|b^2", that also works out, but for me, the reason n = 1 is because sqrt(q) is also an integer (so if we consider the set of rationals, then q is in the subset of the rationals in which the denominator is 1).

Please remember, this is in reference to this statement that you made:
"since r = a(sqrt(q)-k) = b-ak we have a*sqrt(q) = b. Since a<b are integers then sqrt(q) = m/n where m and n are coprime integers.

am=nb. But "a" does not divide n because if it did then the a's cancel out in the formula b^2 = a^2m^2/n^2. The only answer is that "a" must divide b. Or is that based on the fundamental theorem of arithmetic again."

Here's an example ...
36^2 = 1296 = (4^2 / 3^2) * 27^2 ... there, that example should work ... b = 36, a = 27, m = 4, and n = 3). I believe all your conditions are satisfied, n|a, m and n are relatively prime, and a does not divide n. Does a|b (27|36)?

My main problem is that in your proof, you did NOT indicate that n=1 (you just said that a does not divide n, which can be true), and the reason I find this to be a problem is that it contradicts the fact that q is an integer. That's how I get n=1, because if n is not 1, then q is not an integer. Another minor issue is that you did not include the special case where a|n and a|b, this is when a = n = 1, but again, you did not mention anything that says there would be a problem if n|a, with n>1.

6) Yes, my previous post did invoke the FTA, but just as another way you can look at it. Aside from that, I don't think the FTA needs to be invoked outright.

Example:
a and b are integers such that a^2|b^2 => ma^2 = b^2
Since the square root of b^2 = b, then we can take the sqrt(ma^2) = a*sqrt(m) = b.
Since a and b are integers, sqrt(m) must also be an integer
=> a|b

I don't see the FTA there ... and you could probably use the same idea for a^x|b^x => a|b

Furry, if you want, you can ask your teacher if he/she would find the above proof to be acceptable :) ... and if it's not, please let me know what he/she thinks is wrong with it :)

Your right about the requirenent that n must be one. Guess I overlooked that fact at first. But I think you need the FTA to say since a and b are integers sqrt(m) must also be an integer. Otherwise it could be m/n where n|a.

 

[Bingk]

Wouldn't it be closure?

 

[Bingk]

I gave it some thought, and I kind of get what you're saying. I still think it's okay to claim it to be closure since we're dealing with integers only (divisibility, in this case, is defined for integers only ... because really, any number, except zero, divides any other number, it's just that the quotient might not be "neat"), but incase you don't think so, here's another way to look at it:

It obviously can't be an irrational number, nor a complex with non-zero imaginary part. It could be a natural number, an integer, or a rational number. If it's natural, no prob, because that's a subset of the integers. If it's an integer, then we're done.

If it's assumed to be a rational, this is what we get
a * sqrt(q) = b
Since a and b are integers, and we assume sqrt(q) to be a rational m/n with (m,n) = 1.

sqrt(q) = m/n

(sqrt(q))^2 = q = m^2 / n^2

q is an integer, so n^2 | m^2 ... and now we're back to the same problem of having to show that since n^2 | m^2, then n|m.


If n does not divide m, then n^2 does not divide m^2.
Aside: * There's 2 ways to show this, one uses the FTA (and I kinda explained it previously). The other is this:
n does not divide m implies that there does not exist an integer r such that rn = m, so there does not exist an integer r, such that r^2 * n^2 = m^2. So, there might exist an integer s, which is not a square integer, such that s * n^2 = m^2. Since s is not a square integer, when we take it's square root, it will be irrational (n^2 and m^2 are positive, so s has to be positive, so it can't be a complex number with an imaginary part). So, sqrt(s) * n = m => m is irrational. Contradiction => there doesn't exist an integer s, such that s*n^2 = m^2. Thus, there doesn't exist any integer t, square or otherwise, such that t*n^2=m^2 => n^2 does not divide m^2

So, n divides m => n = 1, since (m,n) = 1. => sqrt(q) is an integer.

The difference between showing a^2|b^2 => a|b and n^2|m^2 => n|m, is that a and b are missing the condition that (a,b)=1. But, we can take advantage of the proof for "if n does not divide m, then n^2 does not divide m^2" (which I did in the beginning), to prove that a|b, since if a does not divide b, then a^2 does not divide b^2, which is a contradiction, so a|b.

P.S. I bolded a certain section above, because you might wonder if sqrt(s) * n = m defies our given that n does not divide m. In this case, it's okay, since we've already said that sqrt(s) is an irrational number, not an integer, so sqrt(s) * n = m does not imply that n|m.

 

[ramsey2879]

If it's assumed to be a rational, this is what we get
a * sqrt(q) = b
Since a and b are integers, and we assume sqrt(q) to be a rational m/n with (m,n) = 1.

sqrt(q) = m/n

(sqrt(q))^2 = q = m^2 / n^2

q is an integer, so n^2 | m^2 ... and now we're back to the same problem of having to show that since n^2 | m^2, then n|m.

Since sqrt(q) = b/a it is not irrational. Since q = b^2/a^2 it is an integer as a^2|b^2, so we have established the validity of your assumbtion that q is an integer and must be a square since sqrt(q) is not irrational. Thus a|b. Is that your point?

 

[TheFurryGoat]

3) Could you show how if the a's cancel out, it would contradict the premise that a^2|b^2?
This is what I get:
As you said, n|a, and if a|n => a = n => b^2 = m^2 => b = m => a = 1. I don't see any problems with a = 1, although it is a trivial case ...

I can't see where you get a must be 1.
If a=n => am/n=am/a=m=b and b^2/a^2 is an integer. why does a have to be 1?

 

[TheFurryGoat]

I gave it some thought, and I kind of get what you're saying. I still think it's okay to claim it to be closure since we're dealing with integers only (divisibility, in this case, is defined for integers only ... because really, any number, except zero, divides any other number, it's just that the quotient might not be "neat"), but incase you don't think so, here's another way to look at it:

It obviously can't be an irrational number, nor a complex with non-zero imaginary part. It could be a natural number, an integer, or a rational number. If it's natural, no prob, because that's a subset of the integers. If it's an integer, then we're done.

If it's assumed to be a rational, this is what we get
a * sqrt(q) = b
Since a and b are integers, and we assume sqrt(q) to be a rational m/n with (m,n) = 1.

sqrt(q) = m/n

(sqrt(q))^2 = q = m^2 / n^2

q is an integer, so n^2 | m^2 ... and now we're back to the same problem of having to show that since n^2 | m^2, then n|m.


If n does not divide m, then n^2 does not divide m^2.
Aside: * There's 2 ways to show this, one uses the FTA (and I kinda explained it previously). The other is this:
n does not divide m implies that there does not exist an integer r such that rn = m, so there does not exist an integer r, such that r^2 * n^2 = m^2. So, there might exist an integer s, which is not a square integer, such that s * n^2 = m^2. Since s is not a square integer, when we take it's square root, it will be irrational (n^2 and m^2 are positive, so s has to be positive, so it can't be a complex number with an imaginary part). So, sqrt(s) * n = m => m is irrational. Contradiction => there doesn't exist an integer s, such that s*n^2 = m^2. Thus, there doesn't exist any integer t, square or otherwise, such that t*n^2=m^2 => n^2 does not divide m^2

So, n divides m => n = 1, since (m,n) = 1. => sqrt(q) is an integer.

The difference between showing a^2|b^2 => a|b and n^2|m^2 => n|m, is that a and b are missing the condition that (a,b)=1. But, we can take advantage of the proof for "if n does not divide m, then n^2 does not divide m^2" (which I did in the beginning), to prove that a|b, since if a does not divide b, then a^2 does not divide b^2, which is a contradiction, so a|b.

P.S. I bolded a certain section above, because you might wonder if sqrt(s) * n = m defies our given that n does not divide m. In this case, it's okay, since we've already said that sqrt(s) is an irrational number, not an integer, so sqrt(s) * n = m does not imply that n|m.

This seems to be correct. I didn't find anything suspicious or that sorts. I'd vote closure!
Thanks everyone! I learned a lot thanks to you!

 

[Bingk]

Yes ramsey, that was basically my point :)

Furry, I think it has to do with the fact that a^2|b^2 that's how I got a=1, but you're right, it's not that a has to equal 1, it's just that that's one of the possible solutions, the main point is that I didn't see anything wrong if the a's canceled out.

you're welcome ... ah, and I just got another idea from ramsey's post, hahaha ... but I agree, I think we've discussed this enough :)