4
$\begingroup$

I have a homework assignment to find the two smallest probable primes with $12$ digits, where a probable prime is defined as a number such that $a^{p-1} \equiv 1\ (\textrm{mod}\ p)$, where $a = 2, 3, 5, 7$.

I'm obviously not asking for this to be done for me, but I'm having trouble figuring out a way to do anything other than to brute-force it by checking each of the four congruences for each (odd) $12$ digit number $n$ until I find two of them.

Can someone offer me some hint, relevant theorem, or something that I might be able to use to figure out how to do find these numbers in a more efficient manner? Thanks for any help.

  • 0
    @Bill Dubuque: indeed, once i figured out what i was doing wrong I realized the relevance of what you were saying. Sorry about the confusion, I appreciate the help.2010-10-13

1 Answers 1

2

Since you already found your answers, I'll go ahead an post a solution. I find that python is a much better choice for problems like yours where you need large integer support (it's built in!) and where you don't have a lot of computation (python is slow, in general). This is all you need to do modular exponentiation with repeated squaring:

def modx(base,exp,mod):     r = 1;     while (exp > 0):         if (exp % 2 == 1):             r = (r * base) % mod         base = (base * base) % mod         exp = exp/2     return r 

Now another small function to test for your "probable prime" condition:

def probprime(s):     while (modx(2,s-1,s) != 1  or  modx(3,s-1,s) != 1  or modx(5,s-1,s) != 1 or modx(7,s-1,s) != 1):         s += 1     return(s) 

And you're done! Run python, input the two functions above and type:

>>> probprime(10**11) 100000000003 >>> probprime(probprime(10**11)+1) 100000000019 

...which matches your answers.

  • 1
    @RossMillikan True, to be more direct, it's the built-in `pow`([Python2](https://docs.python.org/2/library/functions.html#pow), [Python 3](https://docs.python.org/3/library/functions.html#pow)) with three arguments. I strongly recommend using it instead of the above (very limited) `modx` implementation.2015-02-18