 mersenneforum.org factorisation for p-1, p is prime
 Register FAQ Search Today's Posts Mark Forums Read  2020-05-22, 13:19   #23
Dr Sardonicus

Feb 2017
Nowhere

3,251 Posts Quote:
 Originally Posted by bhelmes if I regard only the primes p>=5 with p=x²+1 (x>1) and the primes p with p | (x²+1 ) with p > x can i derive any suggestion about the factorisation of p-1 in advance (except divisible by 4 :-) )
Quote:
 Originally Posted by bhelmes if p=x²+1 then x | p-1 if p | (x²+1) ??? Can I calculate q=x²+1 with q=r*p and x and r known; then f | p-1 ; f ???
Quote:
 Originally Posted by bhelmes I have the factorisation of f(n)=n²+1=r*p where r element of N and p is prime
It might help if you wouldn't keep trying to change the question.

In the first above-quoted post, you're asking whether knowing the x < p for which p divides x2 + 1 is of any help in factoring p-1. The answer is "No."

In the second above-quoted post, your hypothesis "x and r known" is nonsensical.

In the third above-quoted post, are assuming that n is given (this variable was named x in previous posts; so in addition to changing the question, you are also gratuitously changing your notation). And, apparently, you are now asking whether, knowing n and a prime factor p of n2 + 1, helps factor p - 1.

Again, the answer is "No." What you do know is that n (mod p) is one of the square roots of -1 (mod p); -n (mod p) is the other square root of -1 (mod p).

Knowing the square roots of -1 (mod p) can help find a and b such that p = a2 + b2. You could then check whether the condition I mentioned in this post is satisfied; and, if you're very lucky and it is satisfied, obtain a (hopefully non-trivial) factorization of p-1. But as I pointed out, the primes p for which the condition is satisfied are thin on the ground. And unfortunately, they appear to be thinner on the ground than primes p == 1 (mod 4) for which (p-1)/4 is actually prime. I'm guessing that p == 1 (mod 4), p <= X for which (p-1)/4 is prime have an asymptotic of order X/log2(X). The ones satisfying the condition I mentioned before, I have no idea, except numerical data indicate a smaller asymptotic.

Perhaps someone who knows the subject better than I could indicate what is known for the proportion of primes p == 1 (mod 4) for which the largest prime factor of p-1 is greater than pc where 0 < c < 1.   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post bhelmes Math 1 2018-08-08 20:19 devarajkandadai Factoring 7 2013-07-06 03:44 Brian-E Math 25 2009-12-16 21:40 fivemack Math 7 2007-11-17 01:27 Robertcop Math 2 2006-02-06 21:03

All times are UTC. The time now is 17:18.

Sun May 31 17:18:38 UTC 2020 up 67 days, 14:51, 1 user, load averages: 1.47, 1.62, 1.68