View Single Post
Old 2017-04-17, 13:59   #8
science_man_88's Avatar
"Forget I exist"
Jul 2009

8,369 Posts

Originally Posted by Dr Sardonicus View Post
If you want to determine whether n/11 is prime or composite (n the exponent), ispseudoprime() is much faster than isprime(), although it can only prove compositeness. If you want to determine whether 10^n+7 itself is prime, about all I can suggest offhand is to look for possible small prime factors p, checking whether Mod(10,p)^n + 7 == 0.

I'm not sure how factoring the exponent might help here, but I'm also not sure it won't
you can speed that up in theory if you mod the exponent by p-1 as that's eulerphi of p for prime p. but here's a few results:

one part is even one part is odd so it doesn't divide by 2. both parts are 1 mod 3 so it doesn't divide by 3, the value is 2 mod 5 so it doesn't divide by 5. 3^n for any value n is not divisible by 7 so it won't divide by that. 11 has already shown not to divide into it. (-3)^n mod 13 cycles -3,9,-1,3,-9,1,-3 and none of these are -7 ( or +6 the equivalent) so it doesn't divide by 13. 17 produces (-7)^n+7 which goes 0,5,4,11,13,16,12,6,14,9,10,3,1,15,2,8, ... repeats which means if the exponent were 1 mod 16 it would divide however the exponent is 15 mod 16 it looks like. etc. edit:and once I felt like doing it it took under 1 minute to check all the way up to 2^30 that no primes divided it ( PARI/GP is pretty slow though at times).

Last fiddled with by science_man_88 on 2017-04-17 at 14:11
science_man_88 is offline   Reply With Quote