View Single Post
Old 2020-11-19, 14:51   #15
Dr Sardonicus
Dr Sardonicus's Avatar
Feb 2017

4,457 Posts

Originally Posted by paulunderwood View Post
Results for a=4:

[68368998319, 4]
[416032697359, 4]
[4752200398399, 4]

All semi-primes, p*q, where gcd(p-1,q-1)=2^i*3^j
No. If g= gcd(p-1,q-1) it is not g, but (p-1)/g and (q-1)/g that are 2*i*3^j; in most of the cases g = p-1.

Furthermore, in every single case, p-1 and q-1 are small multiples of a single prime.

I think there's enough numerical evidence to try to devise a script to construct counterexamples p*q to your test. For example, with a = 4, D = 12, E = 140, find primes l for which (say)

p = 6*l + 1 and q = 36*l + 1 are both prime

p*q is congruent to -1 (mod 560)

kronecker(12,p*q) = - 1

[there's another condition I'm too lazy to look up]

The congruence condition mod 560 produces something like 8 possibilities for l (mod 560).

The other examples show the multipliers 6 and 36 aren't the only possibilities.
Dr Sardonicus is offline   Reply With Quote