Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Number Theory-Square Free

  1. Sep 14, 2010 #1
    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


    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. jcsd
  3. Sep 14, 2010 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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?
  4. Sep 14, 2010 #3


    User Avatar
    Science Advisor
    Homework Helper

    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.
  5. Sep 14, 2010 #4
    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
  6. Sep 14, 2010 #5


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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
  7. Sep 14, 2010 #6
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook