- ベストアンサー
拡張ユークリッド互除法について
大学で習ったのですが、いまいちピンとこないので教えてください。 例えば ax = 1 mod n みたいな場合、xがaの逆元になるのでしょうが、逆元を持つ条件として gcd(a,n)=1である必要があると思います。 法nがn=pq（p,qは素数）みたいな合成数でも、逆元はある時はありますよね？ aとnが互いに素であればいいのだから… それとも法は素数じゃないとダメなんでしょうか？ 私の解釈は間違ってますか？
- wataru_green
- お礼率0% (0/7)
- 数学・算数
- 回答数1
- ありがとう数0
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
法が素数でなくても逆元はありますよ．たとえば 3x = 1 (mod 4) は x = 3 が解です． 一般論としては合同式 ax = 1 (mod n) の解（逆元）が存在する必要十分条件が gcd(a, n) = 1 です．
