p = 12345678910111213141516171819

a = Random[Integer, {1, p - 1}]

Mod[PowerMod[a, p - 1, p], p]

Mod[PowerMod[2, p - 1, p], p]

FactorInteger[p]