Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Simple number theory, divisibility

  1. Sep 16, 2009 #1
    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?
     
  2. jcsd
  3. Sep 16, 2009 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    You mean "a divides b"

    The point is to prove that a2 does NOT divide that!
     
  4. Sep 16, 2009 #3
    Last edited by a moderator: Apr 24, 2017
  5. Sep 16, 2009 #4

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

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

    a divides q2*a2 + 2qar + r2 if and only if a divides r2. 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 r2 using only the fact that r<a.
     
  6. Sep 18, 2009 #5
    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.
     
    Last edited by a moderator: Apr 24, 2017
  7. Sep 18, 2009 #6
    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.
     
  8. Sep 18, 2009 #7
    r = a(sqrt(q) - k) but the proof seems correct otherwise. 0<r<a
     
  9. Oct 5, 2009 #8
    Well, actually nothing stops sqrt(q)-k being smaller than 1. I think the Division algorithm is not quite enough for this problem.
     
  10. Oct 6, 2009 #9
    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.
     
    Last edited: Oct 6, 2009
  11. Oct 17, 2009 #10
    How about this:

    Given [tex]a^2|b^2[/tex]

    Assume [tex]a \nmid b \Rightarrow a^2 \nmid b^2[/tex]

    We have our contradiction

    The other thing you could do is:

    [tex]a^2|b^2 \Rightarrow ma^2=b^2[/tex]

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

    let [tex]n^2=m[/tex]

    [tex]n^2a^2=b^2[/tex]
    [tex](na)^2=b^2[/tex]
    [tex]na=b \Rightarrow a|b[/tex]

    That's basically working backwards ([tex]a|b \Rightarrow a^2|b^2[/tex])
     
  12. Oct 18, 2009 #11
    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.
     
  13. Oct 18, 2009 #12
    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[tex]\nmid[/tex]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[tex]\nmid[/tex]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
     
  14. Oct 18, 2009 #13
    I have some questions about this.

    1) How did you get that a<b? I can get that a[tex]\leq[/tex]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 cant 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[tex]\geq[/tex]k^2*a^2 => q[tex]\geq[/tex]k^2 => sqrt(q)[tex]\geq[/tex]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 :)
     
  15. Oct 19, 2009 #14
    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.

    where do we know this from?
     
  16. Oct 19, 2009 #15
    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 wont 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) wont 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 ....
     
  17. Oct 20, 2009 #16
    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.
    I don't see how you got that.

    I think that the a's cancel out would contradict the premise that a^2|b^2
    Not if n|a
    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.
     
    Last edited: Oct 20, 2009
  18. Oct 21, 2009 #17
    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 :)
     
  19. Oct 21, 2009 #18
    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.
     
  20. Oct 22, 2009 #19
    Wouldn't it be closure?
     
  21. Oct 22, 2009 #20
    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 ... cuz 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 cant 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, cuz 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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Simple number theory, divisibility
Loading...