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

Various Proofs Regarding Divisors and Properties of Divisors

  1. Apr 13, 2012 #1
    Hello there. I have been reading G.H. Hardy's book "A Course of Pure Mathematics". It is a fantastic introduction to Analysis. I have no problems with the book so far, however, it does assume some knowledge in number theory. I just want to make sure that the following proofs for properties of numbers are done correctly and that there is no apparent logical flaw in them. Thank you for your critisism (if any).

    Proposition 1:

    If α divides β, then α divides β[itex]^{η}[/itex], where α and β are integers and η is a positive integer.


    If α divides β then (by definition) there exists some integer κ such that ακ=β.

    Raising both sides of the above equation to η yields the following;


    By use of the laws of exponents, we get


    We can then express α[itex]^{η}[/itex] as α*(α[itex]^{η-1}[/itex]).



    and we have shown that α divides β[itex]^{η}[/itex].

    Proposition 2:

    This proposition was the opposite of the above propostion. It states that if α divides β[itex]^{η}[/itex] then α divides β.

    The proof was done as an extremely simple contrapositive I'm sure you all can figure out.

    Proposition 3:

    Show that if α and β are coprime, then so are α and β[itex]^{η}[/itex], where α and β are integers and η is a positive integer.


    Assume there exists some common factor of α and β[itex]^{η}[/itex], call it ω.

    Let α=ωc and let β[itex]^{η}[/itex]=ωd where c and d are integers.




    The above can be expressed as


    and it is clear that α[itex]/β^{η}[/itex].

    But, from the preceding proofs, if α divides β[itex]^{η}[/itex], then α divides β. But this contradicts our supposition, since α and β are coprime. Hence, by contradiction, there exists no factor ω shared by both α and β[itex]^{η}[/itex] if α and β are coprime, i.e. α and β[itex]^{η}[/itex] are coprime.

    Also, can somebody tell me how to display the "divides" symbol please? Thank you all for your help!
  2. jcsd
  3. Apr 13, 2012 #2
    Yeah, I'm sure it was extremely simple. Only sad that the propositon isn't true.
  4. Apr 13, 2012 #3
    Why do you first say "I'm sure it was extremely simple" and then go on to state "only sad that the proposition isn't true"? That makes no sense. The contrapositive I talk of was found online. Assuming that proposition 1 is true, proposition 2 can be "proven" as follows.

    Assume α does not divide β, then it does not divide β[itex]^{η}[/itex] (by the first proposition).
    Therefore, in order for α to divide β raised to n, it must divide β.
    If you have an example of were this is not the case, please share. I know the proof is not very rigorous at all but I am mainly interested in the truth value of proposition 3. If the last two propositions are wrong, please state where and why they are wrong and offer a proof of proposition 3. Thank you.
    Last edited by a moderator: Apr 13, 2012
  5. Apr 13, 2012 #4
    Your use of the contrapositive isn't justified.
    The contrapositive of proposition 1 would be

    "If α does not divide βn, then α does not divide β"

    You somehow took the converse of that statement, which is not true.
  6. Apr 13, 2012 #5
    You asked for criticism. You didn't give a proof of the proposition, what could micromass have said?

    I'm not reading your proof. Here is a counter example: 4 divides 36 (6^2) but not 6.
  7. Apr 13, 2012 #6
    I apologize. I did not look at the definition of contrapositive. Again, I found the "proof" online and wanted to move quickly in proving proposition 3. I assumed converse and contrapositive were equal. My mistake. I will post a proof of proposition 3 in a moment obviously without the use of proposition 2. I thank you both for your help. Also, I am not angry, I simply don't like it when others are sarcastic. Tell me that I'm a moron for believing the internet and not testing the proof myself. I'd much rather read that. Thank you again.
  8. Apr 13, 2012 #7
    Hello, I found the following proof on a website for proposition 3.


    When the proof is completed it states "so a and bc are coprime". Now I noticed that what was done was a factorization of the expression in the form an+bm=1 to show that a and bc are coprime. However, it seems that the proof assumes the converse of "If a and be are coprime then there exist integers m and n such that am+bn=1", is true. I assume this is the case because the proof shows a(expression 1)+(expression 2)bc=1. And since the entire expression is in the form of am+bn=1 then it is assumed that a and bc are coprime (the converse of the original statement). Is this an accurate example of converse and is it a valid assumption to be made without explicit reference? Thank you and I apologize for calling you a buffoon.
  9. Apr 13, 2012 #8
    Yes, in general for a and b is true

    a and b are coprime if and only if there exist m and n such that am+bn=1.

    But you do need to prove both sides of the equivalence. Just saying that "this is the converse" is not good enough.

    But the implication from right to left is easy enough. Take d such that d divides both a and b. Then d divides am+bn. Thus d divides 1. It follows that d=1 or d=-1, so a and b are coprime
  10. Apr 13, 2012 #9
    Okay. Thank you very much! I realize that saying it is not enough. I was just wondering why the site did not move forward in showing that the converse was in fact true. Is it considered acceptable to not state such a thing in a proof that relies on such an argument?
  11. Apr 13, 2012 #10
    It's acceptable in advanced books. But I think the site should have given a proof.

    But now you saw such an argument, you can easily construct one yourself.
  12. Apr 13, 2012 #11
    Thank you again. Now, I have a few final questions. Forgive me for bothering you but I have no guidance. I notice that in a lot of these books, a lot of knowledge in other fields of mathematics is assumed. I am not yet in university and I have no structure in the subject or an order in which to learn it. I tend to find that I pick up a book, get through the first few chapters, and then become stuck because it has moved past my realm of knowledge. Is there any sort of path that you would personally recommend when in pursuit of the study of mathematics? Thank you again. You have been very helpful.
  13. Apr 13, 2012 #12
    Sure I can recommend a path. But a lot depends on what exactly you aim to study and what exactly you know already. So if you tell me that, then I can recommend you a good path.
  14. Apr 13, 2012 #13
    Well, what I have applied to is a double major in Mathematics and Physics. I want to become a theoretical physicist as I have a great passion for the study of nature. However, that said, I also very much enjoy pure mathematics. My knowledge in the area of mathematics extends through elementary algebra and calculus. Neither of the courses I took were very rigorous as they were high school courses. I have little knowledge in analysis and have some knowledge in naive set theory. I would essentially like to start from "the ground up" but in a more rigorous sense. I know that, as a physicist, I won't be required so much to know proofs as I will be to apply theorems, but that bothers me. I need to have a fundamental understanding of WHY something works and if it REALLY is TRUE. I guess I should probably read Euclid's Elements since it comes up in a lot of proofs. Thank you. If you need me to be more elaborate, I will try to explain myself better.
  15. Apr 13, 2012 #14
    I think the first thing you need to do now is to get a rigorous understanding of calculus. I suggest you work through the calculus book of Spivak. Be alarmed: the exercises in this book are NOT easy. But the book is still very good and I certainly recommend it.

    At the same time as studying calculus, you should take a look at linear algebra. Books like the one by Friedberg are very good introductions. Another good book is by Serge Lang.

    After that, you might want to do multivariable calculus and abstract algebra.

    Once you did calculus and linear algebra, the door is open to more exciting math. Doing a book like Spivak is an excellent preperation for a real analysis course. But you can also do things like differential geometry.

    But first things first, try to get acquainted with calculus and linear algebra first.
  16. Apr 13, 2012 #15
    About Euclid. Euclid's elements is a really neat book. But I don't recommend you to actually read it. You will not need it much in your academic carreer, and what you do need will be explained in modern books.

    It's still a nice book with many fun propositions, but it won't be that useful to you to read it now.
  17. Apr 13, 2012 #16
    Okay. Sounds good. Thank you very much and thanks for the wonderful recommendations for books. By the way, I like your remake of Oppenheimer's quote (or rather, the Bhagavad Gita).

    Is it safe to assume that you are either a physicist, a physicist in progress, or a polymath?
  18. Apr 13, 2012 #17
    Haha, no. I don't know very much about physics really. I'm a mathematician. But physics does interest me :tongue2:
  19. Apr 13, 2012 #18
    How can one have Physics without Mathematics? Love them both. Thank you again for your help and (perhaps more importantly) your time. As I read through Spivak's book, I will likely find myself on this wonderful site once again. I hope we bump into each other (in whatever ways one could "bump" into another over the internet) again. Thank you micromass (by the way, almost everything on this site suggests that you have a background in physics such as your name and signature. I understand now why it is foolish to assume.).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook