平成２８年５月８日

[流れ星]

　　　　　第334回数学的な応募問題

　　　　　　＜解答募集期間：５月８日〜６月１２日＞

［割った余り］

問題１　ｐを自然数としたとき、３３^ｐを１０で割った余りを求めよ。

問題２　ｐを自然数としたとき、３３^ｐを９０で割った余りを求めよ。

NO1「uchinyan」 05/08 12時51分　受信 更新 6/12

問題１：

mod 10 の合同式と二項定理を用いて，

33^p ≡ (30 + 3)^p

≡ 30^p + pC1 * 30^(p-1) * 3 + … + pC(p-1) * 30 * 3^(p-1) + 3^p

≡ 3^p

そこで，

p が 4 で割って 0 余る数のとき，1，

p が 4 で割って 1 余る数のとき，3，

p が 4 で割って 2 余る数のとき，9，

p が 4 で割って 3 余る数のとき，7，

になります。

問題２：

p = 1 のときは，明らかに 33 です。

p が 2 以上の整数の場合，

mod 90 の合同式と二項定理を用いて，

33^p ≡ (30 + 3)^p

≡ 30^p + pC1 * 30^(p-1) * 3 + … + pC(p-1) * 30 * 3^(p-1) + 3^p

≡ 3^p

そこで，

p が 4 で割って 2 余る数のとき，9，

p が 4 で割って 3 余る数のとき，27，

p が 4 で割って 0 余る数のとき，81，

p が 4 で割って 1 余る数のとき，63，

です。

結局，まとめると，

p = 1 のとき，33，で，それ以外は，

p が 4 で割って 2 余る数のとき，9，

p が 4 で割って 3 余る数のとき，27，

p が 4 で割って 0 余る数のとき，81，

p が 4 で割って 1 余る数のとき，63，

になります。

(感想)

このタイプの問題は，初見では少し戸惑うかも知れませんが，

具体的に調べれば規則性も容易に分かり，解きやすい問題だと思います。

また，ある程度心得てくれば，二項定理や合同式を使って容易に解くことができます。

その意味でも，是非，現役の高校生には解いてもらいたい問題ですね。

なお，どちらの問題も最後の辺りは厳密には数学的帰納法を使うのがいいと思いますが，

ほとんど明らかなので省略しました。

NO2「早起きのおじさん」 05/08 21時21分　受信 更新 6/12

問題1

とは、次の式から10で割ったときの余りが同じです。

10で割ったときの余りを考えるときは、の下1桁だけみていけばよいことになります。

p＝1のとき、3

p＝2のとき、3²＝9

p＝3のとき、3³＝27＝10×2＋7

p＝4のとき、3⁴＝81＝10×8＋1

p＝5のとき、35＝243＝10×24＋3

よって余りは（k：自然数として）、

p＝4k−3のとき、3

p＝4k−2のとき、9

p＝4k−1のとき、7

p＝4kのときは、1

問題2

とは、p≧2のとき、次の式から90で割ったときの余りが同じです。

p＝1のとき、余りは33です。

p＝2のとき、3²＝9

p＝3のとき、3³＝27

p＝4のとき、3⁴＝81

p＝5のとき、3⁵＝243＝2×90＋63

p＝6のとき、3⁶＝729＝8×90＋9

ですが、90進法で表したときの、下1桁が必要なので、63×3＝189＝2×90＋9とできます。

よって余りは（k：自然数として）、

p＝1のとき、33

p＝4k＋1のとき、63

p＝4k−2のとき、9

p＝4k−1のとき、27

p＝4kのとき、81

NO3「スモークマン」 05/09 22時03分　受信 更新 6/12

問題１　ｐを自然数としたとき、３３^ｐを１０で割った余りを求めよ。

回答

(30+3)≡3　mod 10

(30+3)^2≡3^2

以降…

33^p≡3^p

3-9-7-1

so…kは自然数

p=4kのとき…余り=1

p=4k-1・・・7

p=4k-2・・・9

p=4k-3・・・3

問題２　ｐを自然数としたとき、３３^ｐを９０で割った余りを求めよ。

回答

(30+3)≡33　mod 90

(30+3)^2≡3^2

(30+3)^3≡3^2*(30+3)≡27

(30+3)^4≡27*3=81

(30+3)^5≡-9*3=-27≡63

(30+3)^6≡-27*3=-81≡9

so…kは自然数

p=1のとき・・・余り=33

p=4k-2のとき・・・余り=9

P=4k-1・・・27

P=4k・・・81

P=4k+1・・・63

という周期になるんですね ^^

NO4「浜田明巳」 　　05/10 12時16分　受信 更新 6/12

問題１
　３３^ｐ≡３^ｐ（mod １０）であり，
　　３^１＝３
　　３^２＝９
　　３^３≡７（mod １０）
　　３^４≡１（mod １０）
　　３^５≡３（mod １０）
　故に求める余りは，ｎを正整数とするとき，
　　ｐ＝４ｎ−３のとき，３
　　ｐ＝４ｎ−２のとき，９
　　ｐ＝４ｎ−１のとき，７
　　ｐ＝４ｎのとき，１

問題２
　　３３^１＝３３
　　３３^２＝(３０＋３)^２＝３０^２＋２・３０・３＋３^２＝９０(１０＋２)＋９≡９（mod ９０）
　　３３^３≡９・３３＝９(３０＋３)＝９０・３＋２７≡２７（mod ９０）
　　３３^４≡２７・３３＝(３０−３)(３０＋３)＝９００−９≡−９≡８１（mod ９０）
　　３３^５≡−９・３３≡−２７≡６３（mod ９０）
　　３３^６≡−２７・３３≡９（mod ９０）
　故に求める余りは，ｎを正整数とするとき，
　　ｐ＝１のとき，３３
　　ｐ＝４ｎ−２のとき，９
　　ｐ＝４ｎ−１のとき，２７
　　ｐ＝４ｎのとき，８１
　　ｐ＝４ｎ＋１のとき，６３

NO4「他力本願」 　　05/16 16時05分　受信 更新 6/12

【問題１】

33 = 3 * 11 で、11 と 10 が互いに素なので、

10 を法とする合同式において、

※ 以下、n^m は、n の m 乗を表す

33^n = 3^n

が成り立つので、順次計算すると、

33^1 ≡ 3^1 ≡ 3

33^2 ≡ 3^2 ≡ (3^1) * 3 ≡ 3 * 3 ≡ 9

33^3 ≡ 3^3 ≡ (3^2) * 3 ≡ 9 * 3 ≡ 27 ≡ 7

33^4 ≡ 3^4 ≡ (3^3) * 3 ≡ 7 * 3 ≡ 21 ≡ 1

となり、以降繰り返し。

問題２への布石として、p を自然数として、

関数 r(p) の値が 33^p を 10 で割った余りだとすると、

r(1) = 3

r(2) = 9

r(3) = 7 = 10 - 3 = 10 - r(1)

r(4) = 1 = 10 - 9 = 10 - r(2)

r(5) = 3 = 10 - 7 = 10 - r(3)

r(6) = 9 = 10 - 1 = 10 - r(4)

となるので、p >= 3 の時、以下が成立している。

r(p) = 10 - r(p - 2)

次に、この形の漸化式の一般項を考える。

a(0) = u, a(1) = v, a(n) = w - a(n - 2)

ここで、三角関数の周期性から、n を整数として、

0 から順次 1 ずつ増加させると、

sin(2 * n * π / 4) = sin(n * π / 2): 0, 1, 0, -1, …

cos(2 * n * π / 4) = cos(n * π / 2): 1, 0, -1, 0, …

となるので、偶数項 (0 も偶数と考える) と奇数項は、

それぞれ以下のように表すことができると考えられる。

偶数項: s * cos(n * π / 2) + t

奇数項: x * sin(n * π / 2) + y

この2 式より、

n = 0 の時: s + t = u

n = 1 の時: x + y = v

n = 2 の時: -s + t = w - u

n = 3 の時: -x + y = w - v

これらから、以下が分かる。

s = (2 * u - w) / 2

t = w / 2

x = (2 * v - w) / 2

y = w / 2

ここで、t = y なので、一般項は、

a(n) = ((2 * u - w) * cos(n * π / 2) + (2 * v - w) * sin(n * π / 2) + w) / 2

になりそうなことが分かる。

実際に、

a(0) = ((2 * u - w) * (1) + 0 + w) / 2 = u

a(1) = (0 + (2 * v - w) * (1) + w) / 2 = v

a(2) = ((2 * u - w) * (-1) + 0 + w) / 2 = w - u

a(3) = (0 + (2 * v - w) * (-1) + w) / 2 = w - v

となり、三角関数の性質上、

上の式が周期 4 であることは自明なので、

この式が一般項となることが確認できる。

このことから、33^p を 10 で割った余りの関数 r(p) は、

a(0) = 3, a(1) = 9, a(n) = 10 - a(n)

とすれば、

r(p) = a(p - 1)

と表すことでができ、以下、

a(p - 1) = ((2 * 3 - 10) * cos((p - 1) * π / 2) + (2 * 9 - 10) * sin((p - 1) * π / 2) + w) / 2 = (-4 * (sin(p * π / 2)) + 8 * (-cos(p * π / 2)) + 10) / 2 = (-4 * sin(p * π / 2) - 8 * cos(p * π / 2) + 10) / 2 = -2 * sin(p * π / 2) - 4 * cos(p * π / 2) + 5

となる。

実際、値を計算してみると、

r(1) = -2 * (1) - 4 * (0) + 5 = -2 + 5 = 3

r(2) = -2 * (0) - 4 * (-1) + 5 = 4 + 5 = 9

r(3) = -2 * (-1) - 4 * (0) + 5 = 2 + 5 = 7

r(4) = -2 * (0) - 4 * (1) + 5 = -4 + 5 = 1

となり、合同式の結果とも一致。

【問題２】

p = 1 の時、33 になることは明らか。

p >= 2 の時、問題１と同様のアプローチもあるが、

33^p が 9 の倍数になることに着目して考える。

33^p = 33 * 33 * 33^(p - 2) = 9 * 121 * 33^(p - 2)

ここで、問題１で求めた r(p) の値は、うまいことに p = 0 の時 1 となるので、

自然数 n を適切に選べば、

33^(p - 2) = 10 * (n - 1) + r(p - 2)

となる。

これを元に、90 を法とする合同式において、

33^p ≡ 9 * 121 * 33^(p - 2)

≡ 9 * 121 * (10 * (n - 1) + r(p - 2))

≡ (9 * 121 * 10 * (n - 1)) + (9 * 121 * r(p - 2))) ≡ 90 * (121 * (n - 1)) + (9 * (120 + 1) * r(p - 2)) ≡ 0 + (9 * 120 * r(p - 2)) + (9 * 1 * r(p - 2)) ≡ 90 * (12 * r(p - 2)) + (9 * r(p - 2)) ≡ 0 + (9 * r(p - 2)) ≡ 9 * r(p - 2)

よって、関数 q(p) の値を、33^p を 90 で割った余りとすれば、

q(1) = 33

p >= 2の時は、

q(p) = 9 * r(p - 2)

= 9 * (-2 * sin((p - 2) * π / 2) - 4 * cos((p - 2) * π / 2) + 5) = 9 * (2 * sin(p * π / 2) + 4 * cos(p * π / 2) + 5) = 18 * sin(p * π / 2) + 36 * cos(p * π / 2) + 45

実際の値を計算すると、以下のようになる。

q(2) = 18 * (0) + 36 * (-1) + 45 = -36 + 45 = 9

q(3) = 18 * (-1) + 36 * (0) + 45 = -18 + 45 = 27

q(4) = 18 * (0) + 36 * (1) + 45 = 36 + 45 = 81

q(5) = 18 * (1) + 36 * (0) + 45 = 18 + 45 = 63

以降繰り返し。

念のため、90 を法とする合同式で確認してみる。

まず、33 = 3 * 11 で、11 と 90 は互いに素なので、

33^n ≡ 3^n

が成立する。これを利用して順次計算すると、

33^2 ≡ 3^2 ≡ 9 = q(2)

33^3 ≡ 3^3 ≡ (3^2) * 3 ≡ 9 * 3 ≡ 27 = q(3)

33^4 ≡ 3^4 ≡ (3^3) * 3 ≡ 27 * 3 ≡ 81 = q(4)

33^5 ≡ 3^5 ≡ (3^4) * 3 ≡ 81 * 3 ≡ 243 ≡ 63 = q(5)

33^6 ≡ 3^6 ≡ (3^5) * 3 ≡ 63 * 3 ≡ 189 ≡ 9 = q(6) = q(2)

となり、先に得られた式の値と一致。

また、問題１と同様に、以下が成り立つので、

q(2) = 9, q(3) = 27, q(p) = 90 - q(p - 2)

p >= 2 の時、この形の漸化式の一般項から、

q(p) = ((2 * 9 - 90) * cos((p - 2) * π / 2) + (2 * 27 - 90) * sin((p - 2) * π / 2) + 90) / 2 = ((-72) * (-cos(p * π / 2)) + (-36) * (-sin(p * π / 2)) + 90) / 2 = (72 * cos(p * π / 2)) + 36 * sin(p * π / 2) + 90) / 2 = 36 * cos(p * π / 2) + 18 * sin(p * π / 2) + 45

となり、先に求めた式と同じ結果が得られる。

【感想】

最初、問題２は計算量が多くなり面倒そうだなと思っていましたが、

33^2 が 9 の倍数になることや、合同式の簡約化が可能になること

が分かり解答を応募してみました。

NO5「にいばりZ12」　　　05/17 00時53分　受信 更新 6/12

問題１ｐを自然数としたとき、３３^ｐを１０で割った余りを求めよ

33≡3（mod10）

∴

33^p≡3^p（mod10）

∵

33^p=(30+3) ^p=30^p+_pC₁30^p-13¹+ _pC₂30^p-23²+ _pC₃30^p-33³+・・・_pC_p-130¹3^p-1+3^p

右辺最終項以外は10で割り切れる

pを自然数1,2,3,4・・・としたとき

3^p=3,9,27,81（以下一桁目が同じ）・・・

従って

3≡3¹（mod10）

9≡3¹⁺¹（mod10）

27≡7≡3¹⁺²（mod10）

81≡1≡3¹⁺³（mod10）

よってn=1,2,3・・（自然数）とし

p =4n-3のときあまり3

p =4n-2のときあまり9

p =4n-1のときあまり7

p =4nのときあまり1

・・・回答

問題２　ｐを自然数としたとき、３３^ｐを９０で割った余りを求めよ。

p>1

33^p≡3^p（mod90）

∵

33^p=(30+3) ^p=30^p +    _pC₁30^p-13¹+    _pC₂30^p-23²+    _pC₃30^p-33³+・・・ _pC_p-130¹3^p-1+3^p

=90・10・30^p-2+90・_pC₁30^p-23⁰+ 90・_pC₂30^p-33¹+90・_pC₃30^p-43²+・・・90・_pC_p-130⁰3^p-2+3^p

右辺最終項以外は90で割り切れる

p =1

33^p=(30+3) ^p=30^p+3^p

=33

よって

p =1のとき

あまり33

p>1のとき

33^p≡3^p（mod90）

なので

p =2のとき、あまり9

p =3のとき、あまり27

p =4のとき、あまり81

p =5のとき、あまり63

p =6のとき、あまり9

以降剰余系は循環するので

p =1のときあまり33

p>1のときnを自然数とし

p =4n-2のときあまり9

p =4n-1のときあまり27

p =4nのときあまり81

p =4n+1のときあまり63

・・・・・回答

NO6「二度漬け白菜」 06/05 13時10分　受信 更新 6/12

(問題1)
33^pを10で割った余りは，
p≡0(mod 4) のとき  1，
p≡1(mod 4) のとき　3，
p≡2(mod 4) のとき　9，
p≡3(mod 4) のとき　7． (答)

(問題2)
33^pを90で割った余りは，
p=1 のとき  33，
p≡0(mod 4) のとき  81，
p≡1(mod 4) かつ p≧5 のとき　63，
p≡2(mod 4) のとき　9，
p≡3(mod 4) のとき　27． (答)

[主張]：
一般に，n，p を任意の正整数とするとき，
n^(p+4) - n^p ≡0 (mod 10)
である．

[証明]：
n^(p+4) - n^p
=((n-2)*(n-1)*n*(n+1)*(n+2)+5*(n-1)*n*(n+1))*n^(p-1) ---(♯)
ここで，
(n-2)*(n-1)*n*(n+1)*(n+2) は2の倍数かつ5の倍数であるので，
これは10の倍数．
また，
(n-1)*n*(n+1) は2の倍数であるので，
5*(n-1)*n*(n+1)は10の倍数．
よって(♯)より， n^(p+4) - n^p は10の倍数  [証明終]

以上より，
n^p と n^(p+4)は10で割ったときの余りが等しいことがわかる．

また，特に p≧2 かつ nが3の倍数のときには，
n^(p-1)が3の倍数であり，
(n-2)*(n-1)*n*(n+1)*(n+2) および 5*(n-1)*n*(n+1)
がいずれも30の倍数であることとから，(♯)より，
n^(p+4) - n^p は90の倍数となる．
つまり，p≧2 かつ nが3の倍数のときには，
n^p と n^(p+4)は90で割ったときの余りが等しい．

33^pを10で割った余りを知るためには，
p=1，2，3，4 のときを調べれば十分．

33^pを90で割った余りを知るためには，
p=1 および p=2，3，4，5 のときを調べれば十分．

--------------------------------------------------

正整数 a，b に対して，aをbで割ったときの余りは
a-b*[a/b] ([ ]はガウス記号)
と表せるので，
問題1の答えは　33^p - 10*[(33^p)/10]
というようにも表せるのではないか？
と思いました。

皆さん、問題や質問に答えてください。一部でも構いませんから、解答とペンネームを添えて、メールで送ってください。待っています。