Question on theorem of arithmetic euclid's algorithm

[singedang2]

http://img143.imageshack.us/img143/7461/divsuu6.jpg
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!

 

[e(ho0n3]

How about an argument using induction?

 

[singedang2]

i don't think this can proven with induction... any other comments?

 

[shmoe]

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?

 

[singedang2]

tell me more about this... gahhh i don't quite get it.

 

[shmoe]

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?