Find a number which generates all the integers mod q

Question

Consider the integers modulo q where q is prime, a generator is any integer 1 < x < q so that x^1, x^2, ..., x^(q-1) covers all q-1 of the integers between 1 and q-1. For example, consider the integers modulo 7 (which we write as Z_7). Then 3, 3^2 mod 7 = 2, 3^3 = 27 mod 7 = 6, 3^4 = 81 mod 7 = 4, 3^5 = 243 mod 7 = 5, 3^6 = 729 mod 7 = 1 covers all the values 3, 2, 6, 4, 5, 1 covers all the integers 1..6 as required.

The task is to write code that takes an input n and outputs a generator for Z_n. You cannot use any builtin or library that does this for you of course.

The only restriction on the performance of your code is that you must have tested it to completion with n = 4257452468389.

Note that 2^n means 2 to the power of n. That is ^ represents exponentiation.

Answer 1

Pyth, 16 15 bytes

f-1m.^T/tQdQPtQ

Test suite

If p is the input, we know that g^(p-1) = 1 mod p, so we just need to check that g^a != 1 mod p for any smaller a. But a must be a factor of p-1 for that to be possible, and any multiple of an a with that property will also have that property, so we only need to check that g^((p-1)/q) != 1 mod p for all prime factors q of p-1. So, we check all integers g in increasing order until we find one that works.

Explanation:

f-1m.^T/tQdQPtQ
f                  Return the first value T such that the following is truthy:
            PtQ    Take the prime factorization of the input - 1.
   m               Map those prime factors to
       /tQd        Take the input - 1 divided by the factor
    .^T    Q       Raise T to that exponent mod input,
                   performed as modular exponentiation, for performance.
 -1                Check that 1 is not found among the results.

Answer 2

Mathematica, 52 bytes

Inspired by isaacg's answer.

1//.i_/;PowerMod[i,Divisors[#-1],#]~Count~1!=1:>i+1&