3で割った余りは難しいからまず2で割った余り、即ち偶数か奇数かを 考えた方がいい。下記質問をやってからこの問題にいく方がいいです。 https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q10262469840 上記質問の回答(1000をnにして)を理解したという前提で書きます。 (1+x)^nをmod 3で展開する。mod 3の代表元は0,1,-1とする。 (1+x)^2=1-x+x^2,(1+x)^3=1+x^3,(1+x)^4=1+x+x^3+x^4,･･･ このとき係数が1である項の個数がAで、係数が-1の項の個数がBである。 nに対するA,Bを必要があればA[n],B[n]と書く。 (a+b)^3=a^3+b^3より(a+b)^(3^m)=a^(3^m)+b^(3^m) (a+b+c)^(3^m)=a^(3^m)+b^(3^m)+c^(3^m)が得られる。 nを3進法で表したときの桁数をmとしmに関する帰納法で証明する。 m=1のときnは1か2でn=1のときA=2,B=0でA-B=2,n=2のときA=2 B=1でA-B=1となり成りたっている。なお帰納法を使うためn=0の ときも必要でこのときA=1,B=0でA-B=1となりOK m≧1としてm桁以下では成りたっているとしてm+1桁のときを考える。 n=3^m+k,またはn=2･3^m+k (0≦k<3^m-1)とかける。 (1+x)^k=P-Q (P,Qは係数が1の単項式の和で共通の項はない)とかけて Pの項数がA[k]でQの項数がB[k]である。帰納法の仮定よりA[k]-B[k]は 2の累乗である。 n=3^m+kのとき (1+x)^n=(1+x)^(3^m)･(1+x)^k=(1+x^(3^m))(P-Q) =P+x^(3^m)･P-{Q+x^(3^m)･Q}となりP+x^(3^m)･Pも Q+x^(3^m)･Qも係数が1の単項式の和で共通の項はない。 それぞれの項の数はA[n]=2A[k],B[n]=2B[k]であるから A[n]-B[n]=2(A[k]-B[k])も2の累乗で成りたつ。 n=2･3^m+kのとき (1+x)^n=((1+x)^2)(3^m)･(1+x)^k=(1-x+x^2)(3^m)･(P-Q) 上の場合よりは多少面倒だがA[n]=2A[k]+B[k],B[n]=2B[k]+A[k] となりA[n]-B[n]=A[k]-B[k]となり成りたつ。 以上の証明から次のことがわかる。 nを3進法で表したときの1の個数をkとしたときA-B=2^k