nを法とした整数の集合に関する問題がわかりません(急募！)

【問題】
nを2以上の整数とする。
条件「0,a,2a,…はnを法として0以上n-1以下の全ての整数を含む。」
を満たすような0以上n-1以下の整数aを考える。
n=360のとき、ありうるaの値は何通りか。

【質問】
n=360と互いに素であるような整数aが条件を満たす、という「予想」は出来るのですが、なぜそう言えるのかが全くわかりません。この問題の解説が一切ないので困っています。誰かわかる方がいれば教えてほしいですm(_ _)m
ちなみに答えは96通りです。

質問者からの補足コメント

• 一応「nを法として」について補足しておきます。
  これは、「nで割ったときの余り」を考えるということです。

    補足日時：2021/12/28 21:30

No.1 ベストアンサー 回答者： stomachman 回答日時： 2021/12/28 22:30

nとaの最大公約数mが1でないとすると、

　　mj=a ∧ mk=n ∧ 1＜k＜n
となるj, kが存在する。で、
　　ka = kmj = nj ≡ 0 mod n

この回答へのお礼

この説明を見て、答えにたどり着くまでのしっかりとした解答を書くことができました。回答ありがとうございます！

お礼日時：2021/12/29 03:03

No.2 回答者： Tacosan 回答日時： 2021/12/29 01:03

a が n と互いに素でない (つまり 1 でない公約数を持つ) なら,

0, a, 2a, ... は全て「a と n の最大公約数」の倍数
になるので「全ての整数を含む」とはならない.

逆に a と n が互いに素なら
ax + ny = 1
となる整数 x, y が必ず存在する.

この回答へのお礼

「aとnの最大公約数の倍数」という表現が解答を書く時のヒントになりました。回答ありがとうございます！

お礼日時：2021/12/29 03:03