このサイトはお使いのブラウザでは正常に動作しません。Google Chromeなど、別のブラウザを使用してください。
nを法とした整数の集合
【問題】nを2以上の自然数とする。nを法とした整数全体の集合を考える。条件「0,a,2a,...はnを法として0以上n-1以下のすべての整数を含む。」を満たすような0以上n-1以下の整数aを考える。n=360のとき、ありうるaの値は何通りか。
【質問】条件を満たすような整数aは n=360 と互いに素なaの値だろうと何となくわかるのですが、なぜaがnと互いに素であるときに条件が満たされるのか、ということがうまく説明できません。答えはあっていたのですが、解説が一切ないので困っています。誰か詳しい解説お願いしますm(_ _)m
回答
数の合同 $\equiv$ はすべて $n$ を法としたものとします.
条件を満たすことと $ka\equiv 1$ となる $k$ が存在することが同値になります. 実際, 条件を満たすなら $0,a,2a,\ldots$ の中に $1$ があるのである $k$ について $ka\equiv 1$ が成り立ちます. 逆にそのような $k$ が存在するとき任意の $b$ について $(bk)a\equiv b$ となるので条件が成り立ちます.
そして $ka\equiv 1$ となることと
$$ak+nm=1$$
が $(k,m)$ について整数解を持つことが同値であり, これは $n$ と $a$ が互いに素であることが同値になります. このことはユークリッドの互除法によって方程式の解を見つけられることからわかります.