Double check - this is prime, yes?

1. Jul 25, 2007

CRGreathouse

Double check -- this is prime, yes?

I thought I had uncovered some kind of pseudoprime, since I found this number with pfgw and on checking it, found it to be composite. I tested it for pseudoprimality with a battery of tests, though, and it passed all of them -- leading me to think that I was mistaken in the first place and tested some other number by typo. But on the off chance it is a pseudoprime I'd like to know, since it would be the only known Baillie-Pomerance-Selfridge-Wagstaff pseudoprime.

The 9928-digit number is:
32986!/(2*(16493!)^2)+1

2. Jul 25, 2007

CompuChip

After about 4 minutes of thinking very hard, Mathematica confirms that
32986!/(2*(16493!)^2) + 1
is prime.

PS It found no divisors but 1 and itself. Which could be viewed as a confirmation of either the fact that it's prime, or that the PrimeQ[] function first finds the divisors and then checks how many there are

Last edited: Jul 25, 2007
3. Jul 25, 2007

CRGreathouse

I don't imagine you know what kind of test it used to determine that? I've run a (B)PSW test (a 2-strong plus a (21, -1)-Lucas test in this case) and 10 strong (Rabin-Miller) tests with random bases. The latter has worst-case error of 2^-20.

Last edited: Jul 25, 2007
4. Jul 25, 2007

rocomath

how much math should i have before i attempt to self-study number theory?

5. Jul 25, 2007

Kummer

It depends what kind. The most basic concepts form Elementary Number Theory and can even be learned while still in high school.

6. Jul 25, 2007

CompuChip

The http://reference.wolfram.com/mathematica/note/SomeNotesOnInternalImplementation.html#6849 [Broken] say that
• PrimeQ first tests for divisibility using small primes, then uses the Miller-Rabin strong pseudoprime test base 2 and base 3, and then uses a Lucas test.
• As of 1997, this procedure is known to be correct only for n<1016, and it is conceivable that for larger n it could claim a composite number to be prime.

I'm now re-running it using this package.
[update]The kernel crashed and I need it for something else now. It ran for over an hour though. [/update]

Last edited by a moderator: May 3, 2017
7. Jul 25, 2007

CRGreathouse

Thanks, that looks good.

I think the number is too long to reasonably prove prime, but it looks like we have shown it to be very likely to be a prime.

Last edited by a moderator: May 3, 2017