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

Homework Help: Question on theorem of arithmetic euclid's algorithm

  1. Oct 2, 2006 #1
    http://img143.imageshack.us/img143/7461/divsuu6.jpg [Broken]
    i know this question has to do with theorem of arithmetic and euclidean algorithm, but i don't even know where to start. help pls!!! thank you!
     
    Last edited by a moderator: May 2, 2017
  2. jcsd
  3. Oct 2, 2006 #2
    How about an argument using induction?
     
  4. Oct 3, 2006 #3
    i don't think this can proven with induction... any other comments?
     
  5. Oct 3, 2006 #4

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Try comparing prime factorizations of a and b. Suppose a prime p appears as p^k in the prime factorization of a and as p^m in the prime factorization of b.

    what do those divisbility critrea tell you about m and k?
     
  6. Oct 3, 2006 #5
    tell me more about this... gahhh i don't quite get it.
     
  7. Oct 3, 2006 #6

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Start with the first condition, a|b^2. You should be able to come up with an inequality for k and m from this.

    How does divisibility relate to the exponents in a prime factorization?
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook