Prime NumbersDate: 12/15/2000 at 14:14:40 From: Joel Dick Subject: Prime Numbers How can I prove that if A = (P1P2+1)^2-1 where P1 and P2 are two distinct primes, then A is a multiple of four distinct primes? Date: 12/15/2000 at 17:51:06 From: Doctor Roy Subject: Re: Prime Numbers Hello, I am not sure that you can prove this. Consider the case when P1 = 2 and P2 = 3, and we obtain that: A = (P1*P2 + 1)^2 - 1 = (2*3 + 1)^2 - 1 = 7^2 - 1 = 49 - 1 = 48 On the other hand, we know that 48 equals 16 * 3, which is 2^4 * 3. So, we have a case where A satisfies the equation, yet is only the multiple of two distinct primes, so we have a case in which the statement is not true, and therefore it cannot be true in general. Perhaps there is a slightly different statement of this problem that can be proved. I hope this helps, and please feel free to write back with any further questions you may have. - Doctor Roy, The Math Forum http://mathforum.org/dr.math/ Date: 12/17/2000 at 00:17:57 From: Joel Dick Subject: Re: Prime Numbers You're right! I got it wrong. I think it was: A = (P1*P2 + 1)^4 - 1 and A is a multiple of three distinct primes. I already factored A down to: P1*P2*(P1*P2-2)*((P1*P2-1)^2 + 1) So that takes care of two primes (P1 and P2) so now we have to prove that: (P1*P2-2)*((P1*P2-1)^2 + 1) is either, (1) prime and distinct from both P1 and P2 or, (2) a multiple of P1 and/or P2 and a third distinct prime. I've plugged in a few numbers for P1 and P2 and I've never found (1) to be true. So basically, it's narrowed down to proving that (1) is false and (2) is true, but I cannot factor P1 or P2 out of the above expression, so that's where I need your help. Thanks. Date: 12/18/2000 at 11:56:15 From: Doctor Rob Subject: Re: Prime Numbers Dr. Roy asked for help in answering your question. A = (P1*P2-1)^4 - 1 = ((P1*P2-1)^2 - 1)*((P1*P2-1)^2 + 1) = P1*P2*(P1*P2-2)*(P1^2*P2^2-2*P1*P2+2) There are two cases to be considered: when one of the primes is 2, and when neither is. Case 1: P1 = 2, P2 >= 3. Then: A = 2^3*P2*(P2-1)*(2*P2^2-2*P2+1) Call the last factor Q. Now it is possible for P2-1 to be a power of 2. In any case, Q = 1 (mod P2-1), so Q is relatively prime to 2, P2, and P2-1; so it must be divisible by at least one prime factor other than 2, P2, or any prime factor of P2-1. In this case, you may have exactly three distinct prime factors of A, such as when P2 = 3, and so A = 2^4*3*13. Case 2: 3 <= P1 < P2. Then all four factors of A odd. Furthermore, P1*P2-2 is relatively prime to P1 and P2, and is >= 13, so it must be divisible by a prime number other than P1 and P2. Furthermore, the last factor is also relatively prime to P1 and P2 and P1*P2-2, and is >= 197. This implies that A has at least four different prime factors. It may have just four, as when P1 = 3, P2 = 5, and A = 3*5*13*197; or it may have more, as when P1 = 3, P2 = 11, and A = 3*5^2*11*31*41; or P1 = 5, P2 = 7, and A = 3*5*7*11*13*89. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/