Lucas super-pseudoprime puzzle

Expand Messages
• ... Definition: The integer pair (q,n) is a Lucas super-pseudoprime (LSPS) pair if and only if n is composite, n q 0, and V(p,q,n) = p mod n, for every
Message 1 of 46 , Oct 31, 2010
• 0 Attachment

> Proposition: For *every* pair of integers (p,k), we have
> V(p, (11*k + 3)*29*43, 11*29*37*43) = p mod 11*29*37*43

Definition: The integer pair (q,n) is a "Lucas super-pseudoprime"
(LSPS) pair if and only if n is composite, n > q > 0, and
V(p,q,n) = p mod n, for every integer p.

With n = 11*29*37*43 = 507529, there are precisely 37 LSPS pairs
(q,n), namely those with q = (11*k + 3)*29*43, for k = 0 to 36.
Mike Oakes remarked that 507529 is not a Carmichael number.

Puzzle: Find an odd square-free non-Carmichael number
such that there exist more than 70,000 LSPS pairs (q,n).

Comment: There is a solution with n < 10^7.

• ... http://physics.open.ac.uk/~dbroadhu/cert/dbmo116.out gives my 116, in the format [n, factors, number of solutions] With n
Message 46 of 46 , Nov 9 5:30 AM
• 0 Attachment
"mikeoakes2" <mikeoakes2@...> wrote:

> > My revised count up to 2*10^10 is 116.
> My (original) count up to 2*10^10 was 105.
> So it must have missed 11, i.e. a bigger proportion.