>>638
＞剰余類環の問題の発展のように思えて
うん，お題が数論だといつも意外に人気だね

＞計算量のOが全然違う数学的な新しい解法
>>558

＞アルゴリズムが存在するか
とりあえずユークリッドの互除法

>>640
本質的に >>555 は，
pn ≡ 1 (mod x)
を n について解く問題，これは　gcd(p, x) = 1 であることが必要十分条件．
gcd を求める一般的かつ効率的な方法は上掲のユークリッドの互除法なんだが，
>>640 には互除法たるループが含まれていないのが，ナイーブなぱっとみだが，かなり疑問
時間ができたら精査するね．