Bad me. There's a modulo inverse for all odd integers.
No, there's a modulo inverse for all numbers which are coprime with the modulus. Hence the link with Euclid's algorithm for finding gcd. (I'm not sure whether you realised this and that's why the bit about needing a drink, but even if you have it might be helpful for other people reading the thread).
I think your linked code is calculating inverses modulo 2^32 for odd integers, but the Javadoc isn't clear enough for me.
Thanks for that info , yes I have made a prime number generator.
I should add that in general you can use Euler's theorem
, and for primes that's Fermat's little theorem
: a^(p-1) == 1 (mod p)
provided that a
is not a multiple of p
. So if you already have a modular exponentiation function and you don't have an extended Euclid function, that's an alternative approach. I think they should have the same asymptotic complexity.