# Homework Help: Number Theory-Square Free

1. Sep 14, 2010

### SirMyztiq

1. The problem statement, all variables and given/known data

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

2. Relevant equations

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

3. 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.

2. Sep 14, 2010

### Office_Shredder

Staff Emeritus
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?

3. Sep 14, 2010

### Dick

By the FTA you know a=(+/-)p1^n1*p2^n2*...pr^(nr) and that that factorization is unique. As you said, if any one 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.

4. Sep 14, 2010

### SirMyztiq

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 alot!

Last edited: Sep 14, 2010
5. Sep 14, 2010

### Office_Shredder

Staff Emeritus
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

6. Sep 14, 2010

### SirMyztiq

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.