Is Integer Factorization Harder Than RSA Factorization?

Show that all of the powers in the prime power factorization of an integer n are even if n is a perfect square?

• show that all of the powers in the prime power factorization of an integer n are even if and only if n is a perfect square

• Answer:

  Well, this follows pretty immediately from the following two facts: (i) (x^m)^n = x^(mn), and (ii) (xy)^a = (x^a)(y^a). Now, let n = (P1^q1)(P2^q2)(P3^q3)...(Pj^qj), where the Pi's represent distinct primes. Then m = n² = [(P1^q1)(P2^q2)(P3^q3)...(Pj^qj)]² = (P1^q1)² • (P2^q2)² • (P3^q3)² • ... • (Pj^qj)² = [P1^(2•q1)] • [P2^(2•q2)] • ... • [Pj^(2•qj)]. So, reading forward gives the proof that a perfect square has even powers; reading backwards gives the proof that a product of even powers of primes is a perfect square. §