Why can 25 not be a primitive root mod 620351. Assuming 620351 is prime???

I dont understand how to do this without doing any explicit calculations

if phi of 620351 is 620350, then how can i show the order of a number smaller than that is congruent to modulo 620351???

HELP!!

thanks