It is impossible to solve this basic prime numbers problem

Printable View

May 6th 2010, 04:32 PM
rahulnaidu

It is impossible to solve this basic prime numbers problem

given odd number e find prime p and q such that ((p-1)*(q-1)-1) is evenly divisible by e
May 6th 2010, 04:35 PM
dwsmith

Quote:

Originally Posted by rahulnaidu

given prime number e find prime p and q such that ((p-1)*(q-1)-1) is evenly divisible by e

Could this be worded better as e divides (p-1)(q-1)-1 such $e,p,q \in P$ where P are prime numbers?
May 6th 2010, 04:38 PM
rahulnaidu

sorry u could take that way
May 6th 2010, 04:43 PM
rahulnaidu

I think it could be solved if some write a code for that, but if some one directly find those 2 numbers then the person math. genius
May 6th 2010, 04:43 PM
dwsmith

$2^n-1$ generates prime numbers so we have.

$(2^n-1-1)(2^p-1-1)+1=(2^n-2)(2^p-2)-1=2^{n+p}-2^{p+1}-2^{n+1}+3<br />$
This what I have though of so far but don't have time to continue so what you can come up with.

So we have $e|2^{n+p}-2(2^{p}+2^{n}-1)+1$ . What do you mean be evenly divisible?
May 6th 2010, 04:45 PM
rahulnaidu

am also trying for some time now couldn't figure it out.
May 6th 2010, 05:08 PM
rahulnaidu

if it is divisible by 2 times,4times,6 times, like that
May 6th 2010, 05:10 PM
rahulnaidu

Quote:

Originally Posted by rahulnaidu

given odd number e find prime p and q such that ((p-1)*(q-1)-1) is evenly divisible by e

sorry i changed the problem it is odd number e not prime number e
May 8th 2010, 08:52 AM
dwsmith

If e is odd, then e is of the form $2j+1$ .

$(2j+1)|2(2^{n+p-1}-2^{p}+2^{n}-1)+1$ . Now we have an odd number divides an odd number.

Are we actually looking for numbers or just solving a general case?

All times are GMT -8. The time now is 08:56 PM.