MultiplicativeOrder[37, 1000]
MultiplicativeOrder[10^100 + 1, 7919]        (*10^3th prime number  Prime[1000]*)
MultiplicativeOrder[10^1000 + 1, 15485863]       (*10^6th prime number*)
MultiplicativeOrder[10^10000 - 1, 22801763489]       (*10^9th prime number*)
MultiplicativeOrder[13, 1 + 10^80]
MultiplicativeOrder[11, 1 + 10^100]