1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Divisibility problem with prime numbers

  1. Oct 26, 2009 #1
    1. The problem statement, all variables and given/known data

    Let's take a prime number p not equal to 5.
    Now let's take three integers a,b,c.

    Prove that if p | (a + b + c) [tex]\wedge[/tex] p | (a^5 + b^5 + c^5), then
    p | (a^2 + b^2 + c^2) [tex]\vee[/tex] p | (a^3 + b^3 + c^3)

    2. Relevant equations

    I think:

    (a + b + c)^2 = a^2 + b^2 + c^2 + 2ab + 2ac + 2bc
    and
    the same for third and fifth power.

    3. The attempt at a solution

    If either (a^2 + b^2 + c^2) or (a^3 + b^3 + c^3) is divisible by p, then the product of them will too be divisible by p.

    (a^2 + b^2 + c^2) * (a^3 + b^3 + c^3) = (a + b + c)^5 - 3(a + b + c)^2 * (ba^2 + ca^2 + ab^2 + cb^2 + ac^2 + bc^2 + 2ab) - 2(a + b + c)^3 * (ab + bc + ca) + 6(((a + b + c)^2 - (a^2 + b^2 + c^2)) * ((a + b + c)^3 - (a^3 + b^3 - c^3)))

    (a^2 + b^2 + c^2) * (a^3 + b^3 + c^3) = (a + b + c)^5 - 3(a + b + c)^2 * (ba^2 + ca^2 + ab^2 + cb^2 + ac^2 + bc^2 + 2ab) - 2(a + b + c)^3 * (ab + bc + ca) + 6((a + b +c)^5 - (a + b + c)^2 * (a^3 + b^3 + c^3) - (a + b + c)^3 * (a^2 + b^2 + c^2) + (a^2 + b^2 + c^2) * (a^3 + b^3 + c^3))

    By moving 6 * (a^2 + b^2 + c^2) * (a^3 + b^3 + c^3) on the right hand side:

    -5 * (a^2 + b^2 + c^2) * (a^3 + b^3 + c^3) = 7 * (a + b + c)^5 - 3 * (a + b + c)^2 * (ba^2 + ca^2 + ab^2 + cb^2 + ac^2 + bc^2 + 2ab) - 2 * (a + b + c)^3 * (ab + bc + ca) - 6 * (a^2 + b^2 + c^2) * (a + b + c)^3 - 6 * (a^3 + b^3 + c^3) * (a + b + c)^2

    In a different arrangement:

    -5 * (a^2 + b^2 + c^2) * (a^3 + b^3 + c^3) = (a + b + c)^2 * (7 * (a + b + c)^3 - 3 * (ba^2 + ca^2 + ab^2 + cb^2 + ac^2 + bc^2 + 2ab) - 2 * (a + b + c) * (ab + bc + ca) - 6 * (a^2 + b^2 + c^2) * (a + b + c) - 6 * (a^3 + b^3 + c^3))

    Which basically proves that 5 * (a^2 + b^2 + c^2) * (a^3 + b^3 + c^3) is divisible by p, as every term on the right hand side is a product of (a + b + c) and something else, which by the assumptions is divisible by p.

    It seems that I'd have to figure out some way to prove that either (a + b + c)^2 is divisible by 5, or that 7 * (a + b + c)^3 - 3 * (ba^2 + ca^2 + ab^2 + cb^2 + ac^2 + bc^2 + 2ab) - 2 * (a + b + c) * (ab + bc + ca) - 6 * (a^2 + b^2 + c^2) * (a + b + c) - 6 * (a^3 + b^3 + c^3) is divisible by 5, as either of these would prove the thesis.

    Comments and hopefully pointers appreciated.

    Thanks in advance,
    Detektyw
     
  2. jcsd
  3. Oct 26, 2009 #2

    Mark44

    Staff: Mentor

    Re: Divisibility

    Maybe I missed it, but I can't find anywhere that you have used the hypothesis that p | a + b + c.
     
  4. Oct 26, 2009 #3
    Re: Divisibility

    Well, I'm using it to state that because I can factor out (a + b + c)^2 from the right hand side, this means that it's divisible by p.
     
  5. Oct 26, 2009 #4

    Mark44

    Staff: Mentor

    Re: Divisibility

    In your very first line there is a problem.
    This is what you are trying to prove. You can't start off by assuming that either (a^2 + b^2 + c^2) or (a^3 + b^3 + c^3) is divisible by p.

    If you want to do a proof by contradiction, you could assume that neither expression is divisible by p, and then work with your given information to establish a contradiction.

    If you prove your statement directly, start with the given information that p is a prime not equal to 5, p | a + b + c, and p | a^5 + b^5 + c^5.

    If p | a + b + c, then for some integer r, pr = a + b + c. Use the same sort of logic for p | a^5 + b^5 + c^5.
     
  6. Oct 26, 2009 #5
    Re: Divisibility

    Sorry if I stated something wrong. The sentence "If either (a^2 + b^2 + c^2) or (a^3 + b^3 + c^3) is divisible by p, then the product of them will too be divisible by p." is true. Actually the thing I was using is the reverse, which is true as a, b and c are integers.

    "If the product of (a^2 + b^2 + c^2) and (a^3 + b^3 + c^3) is divisible by p, then either (a^2 + b^2 + c^2) or (a^3 + b^3 + c^3) is divisible by p".

    Now in the third step of the original post I set out to prove that (a^2 + b^2 + c^2) * (a^3 + b^3 + c^3) is divisible by p using the statements "p | (a + b + c) and p | (a^5 + b^5 + c^5)". Therefore, I don't assume that either (a^2 + b^2 + c^2) or (a^3 + b^3 + c^3) is divisible by p.

    I'm aiming for a direct proof but seem to be a little stuck with the algebra here.
     
  7. Oct 26, 2009 #6

    Mark44

    Staff: Mentor

    Re: Divisibility

    It's difficult following your logic here because some of your steps are huge ones and some are redundant. Some of the steps have explanations that are unclear. Example of huge step:
    It's not at all obvious why the first term on the right side is (a + b + c)^5. When you multiply the two factors on the left, you'll have 9 terms, and will need to do a lot of rearranging to get (a + b + c)^5, or for that matter, (a + b + c)^2.

    Example of redundant step. I believe these two equations are identical.
    Unclear descriptions.
    Are you moving it to the right side? Or just moving it from one place on the right side to another place on the same side?
    What did you do to get the new arrangement?
     
  8. Oct 26, 2009 #7

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Re: Divisibility

    There is a direct proof and I think you might already have it. To make stuff easier to write let's define f(n)=a^n+b^n+c^n. Then you claim to have written 5*f(2)*f(3) as an expression where each term contains factors of f(1) or f(5), correct? That's the same thing I found. I haven't checked your algebra, I've got my own to worry about. But if that's ok, then since p divides f(1) and f(5), p must divide 5*f(2)*f(3). And that's basically the end. Why are you worried about proving that things are divisible by 5?
     
  9. Oct 26, 2009 #8
    Re: Divisibility

    (a^2 + b^2 + c^2) * (a^3 + b^3 + c^3) = (a + b + c)^5 - 3(a + b + c)^2 * (ba^2 + ca^2 + ab^2 + cb^2 + ac^2 + bc^2 + 2ab) - 2(a + b + c)^3 * (ab + bc + ca) + 6(((a + b + c)^2 - (a^2 + b^2 + c^2)) * ((a + b + c)^3 - (a^3 + b^3 - c^3)))

    This is wrong . 2ab in the second line can't be right and the last minus sign has to be a plus because of symmetry. even with 2abc instead of 2ab and +c^3 instead of c^3 it's still wrong. try a=b=1, c=0.

    I used computations (mod p) myself. All equations are (mod p) from this point.

    we know a = - (b+c) and a^5 = -(b^5 + c^5)

    a^5 = - (b+c)^5 = -(b^5 + c^5) => 5 bc (b^3+2b^2c+2bc^2+c^3) =
    5bc[(b+c)^3 - b^2c - bc^2] = 0
    p isn't 5, so bc[(b+c)^3 - b^2c - bc^2] = 0 (lemma 1)

    now let's compute (a^2+b^2+c^2)(a^3+b^3+c^3) =
    a^5+b^5+c^5 + a^3(b^2+c^2) + a^2(b^3+c^3) + b^3c^2 + b^2c^3

    replace a with -(b+c) and using a^5+b^5+c^5 =0 you get

    -(b+c)^3(b^2+c^2) + (b+c)^2(b^3+c^3) + b^3c^2 + b^2c^3 =

    -(b+c)^3(b^2+c^2) + (b+c)^3(b^2+c^2-bc) + b^3c^2 + b^2c^3 =

    -bc[(b+c)^3 - b^2c - bc^2] wich happens to be 0 because of lemma 1

    so (a^2+b^2+c^2)(a^3+b^3+c^3) =0 (mod p) and p | (a^2+b^2+c^2) or
    p | (a^3+b^3+c^3)
     
  10. Oct 26, 2009 #9

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Re: Divisibility

    Yeah, I was assuming the 2ab was a typo and there could probably be more. Which I ignored. But the OP was claiming 5*f(2)*f(3) was divisible by p, which is exactly what I got. So I didn't try detailed checking of the algebra. I was more worried about why the OP thought divisibility by 5 was something that ought to be checked.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Divisibility problem with prime numbers
  1. Division problem (Replies: 6)

Loading...