Is Every Square-Free Integer a Product of Distinct Primes?

[SirMyztiq]

Homework Statement

An integer is called a square-free if it is not divisible by the square of any integer greater than 1: Show that:

Homework Equations

a is square free if and only if a = (+/-)P1*P2*P3*Pr where Pr are distinct primes.

The Attempt at a Solution

So,

a is in Z for all b in Z such that b^2 does not divide a and b>1 if and only if a=(+/-)P1P2P3***Pr where Pr are distinct primes



Hello, I'm taking a number theory class and the basic proofs are kicking my butt. I understand the concepts but it is very difficult for me to actually prove. For example, my solution I have to state the problem in mathematical equivalents. I don't know if I should make b in Z using the FOR ALL(backwards a) or there exists(mirrored E) for the equation. I want to play with the FTA but I don't know how I can incorporate the a|b into the solution. If and only if means I must go both ways and I'm at a loss. I can see why a must be a product of distinct primes because if p^r and r>=2 then it would be divisible by the square which would not make it square free.

 

[Office_Shredder]

I want to play with the FTA

Ok, so the FTA says that we can factor a into primes. You want to show that a can be factored into distinct primes. It sounds like it's ripe for proof by contradiction: what if the prime factorization does not have distinct primes?

 

[Dick]

By the FTA you know a=(+/-)p1^n1*p2^n2*...pr^(nr) and that that factorization is unique. As you said, if anyone of the ni>=2 then a is divisible by pi^2. So a is NOT square free. That proves IF a is square free THEN all of the ni=1. It's really a proof by contradiction. Now you have to prove the other direction. If all of the ni=1, then a is square free. Hint: pick a b^2 that divides a, and p to be a prime factor of b. Do it by contradiction again.

 

[SirMyztiq]

Ok, so the FTA says that we can factor a into primes. You want to show that a can be factored into distinct primes. It sounds like it's ripe for proof by contradiction: what if the prime factorization does not have distinct primes?

I was actually just playing with that. My professor keeps telling me that I just need to work slowly, I'm seeing it now. I get stuck on the little details and that completely throws me of for example:

How would you describe the integer that is squared. Should I use ∀ or ∃ for variable b in relation to a? When do you use those two? I would think I use ∀ since b^2 cannot divide a. Which would, at least to me, mean that any value of b. But, I might be wrong.

Alright, thanks for the tips. I'm going to continue playing with it.I think I got it! Thanks guys! I'll clear up some questions tomorrow with professor but you guys helped a lot!

 

[Office_Shredder]

I don't really understand. You seem to be hung up on these symbols. Just say what you want to say in words, and then worry about making it look good later

 

[SirMyztiq]

I don't really understand. You seem to be hung up on these symbols. Just say what you want to say in words, and then worry about making it look good later

You are very correct. I was caught up in writing what the problem stated rather than just reading it as it is.

I was trying to define two variables. But the way you guys explained it, I see now that I can just use the FTA to define 'a' and then imply that if 'a' is square free then all the exponents of the prime factorization of 'a' must be equal to one. So, then I supposed that some of the exponents where >= 2. Which means that a would be P^2 * P2...with P being distinct and whatnot. Which would mean 'a' can be divided by "p^2" which would make it NOT a square free number.