失礼しました。訂正をします。
327さんの回答が思考停止的です。

>>337
gcd(a,b)=1のときだけを考えればいいのはすぐわかるでしょう。
gcd(a,b)=1とする。a,2a,3a,...,(b-1)a,ba のどれもが
mod.bでは互いに異なることが示せるので、(独力でどうぞ)
よって、とくに、xa≡1(mod.b)を満たす整数xの存在がいえる。
そのようなxに対しては、明らかに、xa=by+1を満たすような
整数yの存在がいえる。したがって、題意は示された。　　　　□