# Divisibility problem with prime numbers

1. Oct 26, 2009

### Detektyw

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) $$\wedge$$ p | (a^5 + b^5 + c^5), then
p | (a^2 + b^2 + c^2) $$\vee$$ 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.

Detektyw

2. Oct 26, 2009

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

3. Oct 26, 2009

### Detektyw

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.

4. Oct 26, 2009

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

5. Oct 26, 2009

### Detektyw

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.

6. Oct 26, 2009

### 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?

7. Oct 26, 2009

### Dick

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?

8. Oct 26, 2009

### willem2

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)

9. Oct 26, 2009

### Dick

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.