合同式の問題 (多分)

質問

どこで見た問題かを忘れてしまったのですが、

1^2+2^2+3^2+4^2+・・・+n^2
(n=1,2,3,・・・・)
をkで割った時、余りに1,2,3,・・・k-1
の全てがあらわれる時のkをすべて求めよ。

という問題です。恥ずかしながら、方針すら立ちません。
一応、nは無限大まで考えることになっていますが、n=1,2,・・・6p-1 まで考えれば十分だと言うことは分かったのですが、それで? という感じで全く先に進みません。
まずは、ヒントをお願いします。
（ヒントで分からなければ、補足しますので、その時もよろしくお願いします。）

回答No.1

nakaizu · ベストアンサー

1^2+2^2+3^2+4^2+・・・+n^2 =S(n)=n(n+1)(2n+1)/6
と表すことにします。kを2、3以外の素数とします。
S(k)≡S(k-1)≡0 (mod k)であることがわかります。
またS(n)を並べた数列を mod kで見てみると周期kで循環しているのがわかります。f(x)が多項式のときは x≡yならばf(x)≡f(y) となるからです。
よってS(n)は mod k ではS(1)からS(k)までみれば良いわけですが、S(k)≡S(k-1)≡0
なので少なくとも一つ足りません。つまりkが2、3
以外の素数のときは条件を満たしません。
k=2とk=3が条件を満たすことは簡単に確認できます。
kが合成数の時にはkの素因数が条件を満たしていなければならないので、2、3
以外の素因数を含む合成数は条件をみたしません。
あとは素因数が2と3だけの合成数のときに成り立つことを証明すれば終わりです.

補足

あまり影響はありませんが、問題が微妙に違った気がします。
＞をkで割った時、余りに1,2,3,・・・k-1
と書きましたが、
余りに0,1,2・・・k-1
で「０」も入っていたと思います。

ｋが２と３以外の素数の時と、２，３ 以外の素因数を含む時に、題意を満たさないと言うことは分かりました。
でも、素因数が2と3だけの合成数の時に成り立つことを証明してみて、何となく気持ち悪い証明なんですが、この証明で大丈夫ですか?
また、他にいい証明方法はありますか?

k=k_1=2^p*3^qの時に題意を満たすと仮定する。
k=2k_1の時
S(6k_1)≡0 (mod k_1),S(6k_1)≠0 (mod 2k_1) ←合同でないという意味です
であるから、S(3*2k_1)≡k_1 (mod 2k_1) となる。
よって、S(6k_1+α)≡S(6k_1)+S(α)≡k_1+S(α) (mod 2k_1) (αは6k_1以下の自然数)・・・(1)
S(α)≡β (mod k_1) の時に (βは0以上k_1未満の整数)
S(α)≡β or S(α)≡k_1+β (mod 2k_1)と表せる。・・・(2)
よって、(1)より
S(α)≡β (mod 2k_1) ⇔ S(6k_1+α)≡k_1+β (mod 2k_1)・・・(3)
S(α)≡k_1+β (mod 2k_1) ⇔ S(6k_1+α)≡β (mod 2k_1)・・・(4)

またk=k_1の時題意を満たすと仮定しているので、βは0,1,2,・・・k_1-1の全てをとりうる。
だから、(3),(4)のいずれの場合でも、ｎ＝1,2,3,・・・12k_1の時に
S(n)を2k_1で割った余りは0,1,2・・・2k_1-1の全てをとる。

∴k=2k_1の時も成り立つ

k=3k_1の時
S(6k_1)≡k_1 or 2k_1 (mod 3k_1) かつ S(12k_1)≡k_1 or 2k_1 (mod 3k_1)
かつ S(6k_1)≠S(12k_1) (mod 3k_1) ←合同でないという意味です。
(この後はk=2k_1の時と同様にすれば省略できると思うので 後は省略します。)

k=1の時、明らかに成り立つので
2^p*3^q (p、qは0以上の整数)と表せる全ての実数で題意を満たす。