nt.number theory - Prime numbers and strings of symbols

I think there's an easier way (well, easier if you assume Dirichlet's Theorem - I think it's simpler than the strong form of Betrand's Postulate). Interpret the string as an integer M in base N; if it happens to be relatively prime to N, you're done - use Dirichlet to find a prime congruent to M modulo N^k where k is the length of the string. David's method places the given string as the most-significant digits of the prime, whereas this approach places it as the least-significant ones.

If M happens to have a common divisor with the base N, you can just pad it with a "1" at the end (e.g. replace 31415 with 314151 in base 10). The padding replaces M by NM+1 which is obviously relatively prime to N.