少なくともというキーワード

(1)は3で割った余りで分類すれば問題ないです。

(2)はどう証明しますか。

ポイントは、「少なくとも」という言葉です。

場合の数・確率もそうですが、この言葉があるときは基本「逆を考える」です。

確率だと余事象、命題だと否定のことです。

なので、背理法が有効です。