Numbers with exactly 4 factors - when you sum the factors is it always a multiple of 3?

[NeedingWD40]

Numbers that are the product of 2 primes have exactly 4 factors e.g 6 has 1, 2, 3, 6 sums to 12; 15 has 1, 3, 5, 15, sums to 24 etc

My question is, is the sum of those factors always a multiple of 3?

For the case where 2 is one of the primes then I think so:

If 2 is one of the prime factors of x, 2 and x must be even, 1 and the other prime factor must be odd (as 2 is the only even prime). We can express all odd numbers as two times a number plus 1 e.g. 2*a +1. So the factors of x are 1, 2, 2*a+1, 2(2*a+1) as x must be the product of 2 and the other factor. The sum of these is 1+2+2a+1+2(2a+1) = 1 + 2 + 2a + 1 + 4a + 2 = 6 + 6a = 3(2 + 2a) so is always a multiple of 3.

But when I tried this approach with two distinct odd primes e.g. 2a+1 and 2b+ 1 I end up with
1, 2a+1, 2b+ 1, (2a+1)(2b+1) which sum to 4 + 4ab + 4a + 4b... definitely a multiple of 4 but doesn't look like a multiple of 3...

 

[lev888]

But when I tried this approach with two distinct odd primes e.g. 2a+1 and 2b+ 1 I end up with
1, 2a+1, 2b+ 1, (2a+1)(2b+1) which sum to 4 + 4ab + 4a + 4b... definitely a multiple of 4 but doesn't look like a multiple of 3...

You proved that it's a multiple of 4, but you didn't prove that it's not a multiple of 3.

 

[JeffM]

[math]7 * 13 = 91.[/math]
[math]1 + 7 + 13 + 91 = 12 + 100 = 112.[/math]
[math]112 \div 3 = 37 + \dfrac{1}{3}.[/math]
No, the sum of the factors of product of two primes is NOT always a multiple of 3.

 

[JeffM]

My previous post was a specific example of this generic idea.

Let p and q be primes > 3 and

[math]p = 3u + 1 \text { and } q = 3v + 1 \implies 1 + p + q + pq =[/math]
[math]1 + 3u + 1 + 3v + 1 + 9uv + 3u + 3v + 1 = 3 + 6u + 6v + 9uv + 1 = 3 * \text {some integer} + 1.[/math]

 

[lev888]

My previous post was a specific example of this generic idea.

Let p and q be primes > 3 and

[math]p = 3u + 1 \text { and } q = 3v + 1 \implies 1 + p + q + pq =[/math]
[math]1 + 3u + 1 + 3v + 1 + 9uv + 3u + 3v + 1 = 3 + 6u + 6v + 9uv + 1 = 3 * \text {some integer} + 1.[/math]

To use this proof we should demonstrate that 3u+1 primes exist in the first place, right? And if we need to come up with an example for the proof to work, how useful is it? Just use the example of 7 and 13.

 

[Deleted member 4993]

To use this proof we should demonstrate that 3u+1 primes exist in the first place, right? And if we need to come up with an example for the proof to work, how useful is it? Just use the example of 7 and 13.

Any prime u >2 is odd → 3u is odd →(3u + 1) is even → (3u+1) is NOT a prime

 

[lev888]

Any prime u >2 is odd → 3u is odd →(3u + 1) is even → (3u+1) is NOT a prime

"Let p and q be primes > 3" - p and q are primes, not u and v.

 

[JeffM]

To use this proof we should demonstrate that 3u+1 primes exist in the first place, right? And if we need to come up with an example for the proof to work, how useful is it? Just use the example of 7 and 13.

This is a remarkably silly post. I wasn’t trying to emulate Bourbaki, but to show that 7 * 13 is not a special case and to demonstrate it in the spirit of the OP’s question, not for publication in a journal on number theory.

Moreover, it is not correct that it is necessary to prove that any prime with a remainder of 1 when divided by 3 exists to prove that the sum of the factors of the product of any pair of such primes will not be a multiple of three. If X, then Y does not presuppose X.

[math]m \text { is a prime } > 3 \implies m = 3i + r, \text { where } r = 1 \text { or } r = 2.[/math]
[math]\text {CASE I: } \exists \text { a pair of primes } p \text { and } q \text { such that } 3 < p = 3u + 1 \text { and } 3 < q = 3v + 1.[/math]
[math]1 + p + q + pq = 1 + 3u + 1 + 3v + 1 + 9uv + 3u + 3v + 1 = 3(1 + 2u + 2v + 3uv) + 1 \implies[/math]
[math] 3 \not | \ (1 + p + q + pq).[/math]
[math]\text {CASE II: } \exists \text { a pair of primes } p \text { and } q \text { such that } 3 < p = 3u + 2 \text { and } 3 < q = 3v + 2.[/math]
[math]1 + p + q + pq = 1 + 3u + 2 + 3v + 2 + 9uv + 6u + 6v + 4 = 3(3 + 2u + 2v + 3uv) \implies[/math]
[math] 3 \ | \ (1 + p + q + pq).[/math]
[math]\text {CASE III: } \exists \text { a pair of primes } p \text { and } q \text { such that } 3 < p = 3u + 1 \text { and } 3 < q = 3v + 2.[/math]
[math]1 + p + q + pq = 1 + 3u + 1 + 3v + 2 + 9uv + 6u + 3v + 2 = 3(2 + 2u + 2v + 3uv) \implies[/math]
[math] 3 \ | \ (1 + p + q + pq).[/math]
Thus, to prove that the hypothesis is true, it is necessary to show that there do not exist any primes with a remainder of 1 when divided by 3. Of course, there are such primes; every twin prime has such a prime. Attacking the problem this way shows the conditions when the hypothesis is true and when false, which an example will not do. That is why we generalize in mathematics. Moreover it does generate a neat little factoid: the sum of the factors of any pair of twin primes is divisible by 3.

 

[lev888]

This is a remarkably silly post. I wasn’t trying to emulate Bourbaki, but to show that 7 * 13 is not a special case and to demonstrate it in the spirit of the OP’s question, not for publication in a journal on number theory.

Moreover, it is not correct that it is necessary to prove that any prime with a remainder of 1 when divided by 3 exists to prove that the sum of the factors of the product of any pair of such primes will not be a multiple of three. If X, then Y does not presuppose X.

[math]m \text { is a prime } > 3 \implies m = 3i + r, \text { where } r = 1 \text { or } r = 2.[/math]
[math]\text {CASE I: } \exists \text { a pair of primes } p \text { and } q \text { such that } 3 < p = 3u + 1 \text { and } 3 < q = 3v + 1.[/math]
[math]1 + p + q + pq = 1 + 3u + 1 + 3v + 1 + 9uv + 3u + 3v + 1 = 3(1 + 2u + 2v + 3uv) + 1 \implies[/math]
[math] 3 \not | \ (1 + p + q + pq).[/math]
[math]\text {CASE II: } \exists \text { a pair of primes } p \text { and } q \text { such that } 3 < p = 3u + 2 \text { and } 3 < q = 3v + 2.[/math]
[math]1 + p + q + pq = 1 + 3u + 2 + 3v + 2 + 9uv + 6u + 6v + 4 = 3(3 + 2u + 2v + 3uv) \implies[/math]
[math] 3 \ | \ (1 + p + q + pq).[/math]
[math]\text {CASE III: } \exists \text { a pair of primes } p \text { and } q \text { such that } 3 < p = 3u + 1 \text { and } 3 < q = 3v + 2.[/math]
[math]1 + p + q + pq = 1 + 3u + 1 + 3v + 2 + 9uv + 6u + 3v + 2 = 3(2 + 2u + 2v + 3uv) \implies[/math]
[math] 3 \ | \ (1 + p + q + pq).[/math]
Thus, to prove that the hypothesis is true, it is necessary to show that there do not exist any primes with a remainder of 1 when divided by 3. Of course, there are such primes; every twin prime has such a prime. Attacking the problem this way shows the conditions when the hypothesis is true and when false, which an example will not do. That is why we generalize in mathematics. Moreover it does generate a neat little factoid: the sum of the factors of any pair of twin primes is divisible by 3.

I am not sure what kind of intent you are seeing behind my post. It may be wrong, obviously - I'll review your comments. But am not sure it deserves the "silly" characterization. In case you didn't notice, there were 2 question marks, so I was not announcing some verdict from on high, I was trying to understand how useful that approach was for that particular problem.

 

[NeedingWD40]

My previous post was a specific example of this generic idea.

Let p and q be primes > 3 and

[math]p = 3u + 1 \text { and } q = 3v + 1 \implies 1 + p + q + pq =[/math]
[math]1 + 3u + 1 + 3v + 1 + 9uv + 3u + 3v + 1 = 3 + 6u + 6v + 9uv + 1 = 3 * \text {some integer} + 1.[/math]

Thanks for the 7*13 = 91 example, that's perfect... it shows that not all the sums of the factors of products of two primes are divisible by 3 (but they are by 4, incidentally!) but I think this general form will only apply to primes that are of the form 3u + 1 so doesn't give a general proof of not being divisible by 3.

 

[NeedingWD40]

[math]7 * 13 = 91.[/math]
[math]1 + 7 + 13 + 91 = 12 + 100 = 112.[/math]
[math]112 \div 3 = 37 + \dfrac{1}{3}.[/math]
No, the sum of the factors of product of two primes is NOT always a multiple of 3.

Thank you, just what I needed, I was barking up the wrong tree!

 

[NeedingWD40]

This is a remarkably silly post. I wasn’t trying to emulate Bourbaki, but to show that 7 * 13 is not a special case and to demonstrate it in the spirit of the OP’s question, not for publication in a journal on number theory.

Moreover, it is not correct that it is necessary to prove that any prime with a remainder of 1 when divided by 3 exists to prove that the sum of the factors of the product of any pair of such primes will not be a multiple of three. If X, then Y does not presuppose X.

[math]m \text { is a prime } > 3 \implies m = 3i + r, \text { where } r = 1 \text { or } r = 2.[/math]
[math]\text {CASE I: } \exists \text { a pair of primes } p \text { and } q \text { such that } 3 < p = 3u + 1 \text { and } 3 < q = 3v + 1.[/math]
[math]1 + p + q + pq = 1 + 3u + 1 + 3v + 1 + 9uv + 3u + 3v + 1 = 3(1 + 2u + 2v + 3uv) + 1 \implies[/math]
[math] 3 \not | \ (1 + p + q + pq).[/math]
[math]\text {CASE II: } \exists \text { a pair of primes } p \text { and } q \text { such that } 3 < p = 3u + 2 \text { and } 3 < q = 3v + 2.[/math]
[math]1 + p + q + pq = 1 + 3u + 2 + 3v + 2 + 9uv + 6u + 6v + 4 = 3(3 + 2u + 2v + 3uv) \implies[/math]
[math] 3 \ | \ (1 + p + q + pq).[/math]
[math]\text {CASE III: } \exists \text { a pair of primes } p \text { and } q \text { such that } 3 < p = 3u + 1 \text { and } 3 < q = 3v + 2.[/math]
[math]1 + p + q + pq = 1 + 3u + 1 + 3v + 2 + 9uv + 6u + 3v + 2 = 3(2 + 2u + 2v + 3uv) \implies[/math]
[math] 3 \ | \ (1 + p + q + pq).[/math]
Thus, to prove that the hypothesis is true, it is necessary to show that there do not exist any primes with a remainder of 1 when divided by 3. Of course, there are such primes; every twin prime has such a prime. Attacking the problem this way shows the conditions when the hypothesis is true and when false, which an example will not do. That is why we generalize in mathematics. Moreover it does generate a neat little factoid: the sum of the factors of any pair of twin primes is divisible by 3.

You're pushing my formal maths with this!

So [math] 3 \not | \ [/math] must mean is not a factor of...

This is telling me that all primes must be of the form a multiple of 3 + 1 or a multiple of 3 plus 2. It then looks at the three cases, and finds in the first case the result isn't a multiple of 3, in the second and third it is.

which is why I found so many examples it works for!

Many thanks

 

[JeffM]

You're pushing my formal maths with this!

So [math] 3 \not | \ [/math] must mean is not a factor of...

This is telling me that all primes must be of the form a multiple of 3 + 1 or a multiple of 3 plus 2. It then looks at the three cases, and finds in the first case the result isn't a multiple of 3, in the second and third it is.

which is why I found so many examples it works for!

Many thanks

Yes, [imath]\not | [/imath] means “does not divide evenly” in number theory, which is just another way to say “is not an integer factor of.”

Yes, every integer when divided by 3 has a remainder of 0, 1, or 2. But no prime greater than 3 has a remainder of 0 when divided by 3 because a prime larger than 3 is not evenly divisible by 3 by definition.

Yes, we can develop proofs for three cases: both primes greater than 3 and each with a remainder of 1, both primes with a remainder of 2, or exactly one of the two primes with a remainder of 1. The sum of the factors of the product of the two primes is never evenly divisible by 3 in the first case, but always evenly divisible in the next two cases.

Your instincts for math are good; you tried to generalize with your observation about all primes greater than 2 being odd. As lev pointed out, that leads to a correct result but one irrelevant to your question. I suspect that your dealing with 2 as a special case got you thinking along the lines of even versus odd, which turns out to be a dead end with respect to this specific question.

Here I think is the exhaustive approach. Every prime when divided by 3 has a remainder of 0, 1, or 2. The sum of the divisors of the product of any two primes, not necessarily distinct, is evenly divisible by 3 if and only if the remainder of at least one of the primes is 2.

 

[JeffM]

@lev888

Upon reflection, I realize that my post #8 was intemperate, and I apologize.

You were correct that the example in post #3 was sufficient to prove as false the proposition that the sum of the factors of the product of any two primes is evenly divisible by 3.

You were also correct that, to use my argument in post #4 to prove false the preceding proposition, it would be necessary either to prove the general existence of primes that have a remainder of 1 when divided by 3 or to demonstrate the existence of at lease one such pair by example, in which case the generalization was not needed.

What annoyed me, excessively to be sure, was the apparent implication of post #5 that generalization was inappropriate and that the original poster's only interest was to prove the falsity of a very narrow proposition. I was reading the OP's interest as being under what circumstances the proposition about the divisibility of the sum of the factors of the product of two primes by 3 was true and under what circumstances false. And that question is not answered by examples, but by generalization, an approach he had actually attempted. And, because examples abound of primes with a remainder of 1 when divided by 3 and because the statement was a conditional statement that actually made no assertion about their existence, there was no technical need to prove their existence.

Anyway, I am sorry to have offended you. I'd ask Subhotosh to edit post #8, but I am not sure how to disentangle the substantive part of it from the emotional part.

 

[lev888]

@lev888

Upon reflection, I realize that my post #8 was intemperate, and I apologize.

You were correct that the example in post #3 was sufficient to prove as false the proposition that the sum of the factors of the product of any two primes is evenly divisible by 3.

You were also correct that, to use my argument in post #4 to prove false the preceding proposition, it would be necessary either to prove the general existence of primes that have a remainder of 1 when divided by 3 or to demonstrate the existence of at lease one such pair by example, in which case the generalization was not needed.

What annoyed me, excessively to be sure, was the apparent implication of post #5 that generalization was inappropriate and that the original poster's only interest was to prove the falsity of a very narrow proposition. I was reading the OP's interest as being under what circumstances the proposition about the divisibility of the sum of the factors of the product of two primes by 3 was true and under what circumstances false. And that question is not answered by examples, but by generalization, an approach he had actually attempted. And, because examples abound of primes with a remainder of 1 when divided by 3 and because the statement was a conditional statement that actually made no assertion about their existence, there was no technical need to prove their existence.

Anyway, I am sorry to have offended you. I'd ask Subhotosh to edit post #8, but I am not sure how to disentangle the substantive part of it from the emotional part.

Thank you. I think I misunderstood post #4. When you wrote that the 7 * 13 example was "a specific example of this generic idea." I understood it as "instead of the 7 * 13 example to answer the OP's question we can use this generic proof". So my reply was me "thinking aloud" about how this substitution didn't appear to work for the specific question "is the sum of factors always a multiple of 3". Of course, your general approach is good, especially as a part of the analysis covering all 3 cases.

 

[JeffM]

I have been busy with other things lately. I thought I might put this thread to bed rather late.

It is given that p and q are primes such that p = 3u + x and 3v + y, where u, v, x, and y are non-negative integers, x < 3, and y < 3. We define t = 1 + p + q + pq. Prove

[math]3 \ | \ t \iff \{x = 2\} \lor \{y = 2\}[/math].

[math]\text {CASE I: } x = 2.[/math]
[math]t = 1 + p + q + pq = 1 + 3u + 2 + 3v + y + (3u + 2)(3v + y) =[/math]
[math]= 3 + 3u + 3v + y + 9uv + 3uy + 6v + 2y = 3(1 + u + 3v + 3uv + y) \implies 3 \ | \ t.[/math]
[math]\text {CASE II: } y = 2.[/math]
[math]t = 1 + p + q + pq = 1 + 3u + x + 3v + 2 + (3u + x)(3v + 2) =[/math]
[math]= 3 + 3u + 3v + 9uv + 6u + 3vx + x + 2x = 3(1 + 3u + v + 3uv + x) \implies 3 \ | \ t.[/math]
[math]\text {CASE III: } \{0 \ne 2\} \land \{y \ne 2\}[/math].

[math]t = 1 + p + q + pq = 1 + 3u + x + 3v + y + (3u + x)(3v + y) =[/math]
[math]3u + 3v + 9uv + 3uy + 3vx + 1 + x + y + xy = 3(u + v + uv + uy + vx) + (1 + x + y + xy).[/math]
[math]\text {By hypothesis, } 0 \le x \le 1 \text { and } 0 \le y \le 1.[/math]
[math]\therefore 1 + x + y + xy = 1 \text { or } 2 \text { or } 4 \implies 3 \ \not | \ t \implies[/math]
[math]\neg \{3 \ \not | \ t \} \implies \neg \{\{x \ne 2\} \land \{y \ne 2\}\} \implies 3 \ | \ t \implies \{x = 2\} \lor \{y = 2\}.[/math]