1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Question on theorem of arithmetic euclid's algorithm

  1. Oct 2, 2006 #1
    [​IMG]
    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!
     
  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?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Question on theorem of arithmetic euclid's algorithm
  1. Arithmetic question (Replies: 1)

  2. Euclid's Algorithm (Replies: 5)

Loading...