整数問題 13 京都医大

Question

自然数 n に対して、f(n)=5³ʰ+5²ʰ+5ʰ+1 とおく.
(1) n が 4 の倍数でないとき、f(n)は 13 で割り切れることを示せ.
(2) n が 4 の倍数のとき、f(n)を 13 で割った余りを求めよ .

補足

取り敢えず 4 を法にとって考えるしかなさそうですけど、、
難問集から引っ張ってきました
一筋縄では解けなさそうです
4 , 13 どちらで法をとるのよ！

識者の方々の考え方も教えてください

mtrajcp · Accepted Answer

補足2023/05/15 13:02 について

8^2=1(mod13) …③は(1は)間違いで正しくは(-1)

8^2=64=13*5-1=-1(mod13) …③

です

(i)n=1(mod4)のとき①の右辺は
　-{(8^2)^1+1}(8^1-1)=-{(-1)^1+1}(8^1-1)=0(mod13)(∵③)
(ii)n=2(mod4)のとき②
 {(8^2)^2+1}(8^2+1)={(8^2)^2+1}(-1+1)=0(mod13)(∵③)
(iii)n=3(mod4)のとき①
　-{(8^2)^3+1}(8^3-1)=-{(-1)^3+1}(8^3-1)=0(mod13)(∵③)

ありものがたり · Answer

←補足(05/15 13:04)

それでいいと思います。
あなたの答案も、私や No.1 No.4 の回答も
要は n mod 4 で場合分けして f(n) mod 13 を計算すればいい
って論旨だから、書き方の違いだけです。

あなたが一旦①②に場合分けしたことに
意味があるのかどうかはよく解らないけど。

今回の問題の場合、 n mod 4 に着目することは
小問の構成でほぼ誘導されているから、
(i)〜(iv) の場合分けさえ行えば満点でしょう。

No.2 で語りたかったのは、
f(n) の式形から自力で mod 4 を発見するには
どう考えたらよいか の部分です。
この問題を解くだけなら、必要もない議論ですが。

mtrajcp · Answer

f(n)=5^(3n)+5^(2n)+5^n+1

5^2=25=13*2-1=-1(mod13)
5^3=(5^2)5=-5(mod13)
5^4=(5^2)^2=(-1)^2=1(mod13)

(1)
nが4の倍数でないとき
n=4k+1.or.n=4k+2.or.n=4k+3となる整数kがある

n=4k+1のとき
5^n=5^(4k+1)=5(5^4)^k=5(mod13)
5^(2n)=5^2=-1(mod13)
5^(3n)=-5(mod13)
だから
f(n)=-5-1+5+1=0(mod13)…①

n=4k+2のとき
5^n=5^(4k+2)=5^2(5^4)^k=5^2=-1(mod13)
5^(2n)=1(mod13)
5^(3n)=-1(mod13)
だから
f(n)=-1+1-1+1=0(mod13)…②

n=4k+3のとき
5^n=5^(4k+3)=5^3(5^4)^k=5^3=-5(mod13)
5^(2n)=5^2=-1(mod13)
5^(3n)=5(mod13)
だから
f(n)=5-1-5+1=0(mod13)

↓これと①,②から

f(n)は 13 で割り切れる

(2)
nが4の倍数のとき
n=4k
となる自然数kがある
5^n=5^(4k)=(5^4)^k=1(mod13)
5^(2n)=1(mod13)
5^(3n)=1(mod13)
だから
f(n)=1+1+1+1=4(mod13)
だから
f(n)を13で割った余りは
4

ありものがたり · Answer

誤字訂正：

g(u) を mod 13 で計算してみると、
u　　g(u)
1　　4
5　　0
-1　　0
-5　　0

ありものがたり · Answer

f(n) = g(5^n)　　；ただし g(u) = u^3 + u^2 + u + 1.

mod 13 において 5^n の表を作ってみる。
フェルマーの小定理より 5^12 ≡ 1 (mod 13) は判っているが、
n　　5^n
0　　1
1　　5
2　　-１
3　　-5
4　　1
5　　(以下略)
となって 5^4 ≡ 1 (mod 13) であることが判る。

この表に現れる 5^n (mod 13) の値に対して
g(u) を mod 13 で計算してみると、
u　　g(u)
1　　1
5　　0
-1　　0
-5　　0
である。

表を連結すると、
n (mod4)　f(n)=g(5^n) (mod13)
0　　　　　4
1　　　　　0
2　　　　　0
3　　　　　0
となる。

よって、(1) は示され、
(2) は 4 であると判った。

kantansi · Answer

3 / 3

問題を解く前に、次の恒等式が成り立つことに注意しましょう。

54 ≡1(mod13)

(1) n が 4 の倍数でないとき、f(n)は 13 で割り切れることを示すには、n を 4 の倍数でない自然数と仮定し、n を 4 で割った余りによって場合分けを行います。つまり、n=4k, 4k+1, 4k+2, 4k+3 の場合についてそれぞれ f(n) を計算して、13 で割り切れることを示せばよいです。

n=4k の場合、f(n) を計算すると、

\begin{aligned}
f(n) &= 5^{4k+3} + 5^{4k+2} + 5^{4k+1} + 1 \
&= (5^4)^k \cdot 5^3 + (5^4)^k \cdot 5^2 + (5^4)^k \cdot 5 + 1 \
&\equiv 1 \cdot 5^3 + 1 \cdot 5^2 + 1 \cdot 5 + 1 \pmod{13} \
&\equiv 0 \pmod{13}
\end{aligned}

となり、f(n) は 13 で割り切れます。

n=4k+1 の場合、f(n) を計算すると、

\begin{aligned}
f(n) &= 5^{4k+4} \cdot 5^{-1} + 5^{4k+3} \cdot 5^{-1} + 5^{4k+2} \cdot 5^{-1} + 5^{4k+1} \cdot 5^{-1} \
&\equiv 1 \cdot 5^{-1} + (-2) \cdot 5^{-1} + (-1) \cdot 5^{-1} + 1 \cdot 5^{-1} \pmod{13} \
&\equiv 0 \pmod{13}
\end{aligned}

となり、f(n) は 13 で割り切れます。

同様にして、n=4k+2, 4k+3 の場合も f(n) が 13 で割り切れることが示せます。

(2) n が 4 の倍数のとき、f(n) を 13 で割った余りを求めるには、n を 4 の倍数と仮定し、f(n) を計算して 13 で割った余りを求めればよいです。

n=4k の場合、f(n) を計算すると、
\begin{aligned}
f(n) &= 5^{4k+3} + 5^{4k+2} + 5^{4k+1} + 1 \
&= (5^4)^k \cdot 5^3 + (5^4)^k \cdot 5^2 + (5^4)^k \cdot 5 + 1 \

(1) n が 4 の倍数でない場合、n = 4k + r (ただし、r = 1, 2, 3) と書けます。ここで、f(n) を 13 で割った余りを求めるために、f(n) を mod 13 で考えます。f(n) を mod 13 で計算すると、

f(n) ≡ 5³ʰ+5²ʰ+5ʰ+1 ≡ (5³)ʰ+(5²)ʰ+5ʰ+1 ≡ 1 + 3ʰ + 9ʰ + 1 ≡ 4(3ʰ + 2ʰ + 1) ≡ 0 (mod 13)

となります。したがって、f(n) は 13 で割り切れます。

(2) n が 4 の倍数の場合、n = 4k (ただし、k は自然数) と書けます。f(n) を mod 13 で計算すると、

f(n) ≡ 5³ʰ+5²ʰ+5ʰ+1 ≡ (5³)ʰ+(5²)ʰ+5ʰ+1 ≡ 1 + 3ʰ + 9ʰ + 1 ≡ 4(3ʰ + 2ʰ + 1) ≡ 4(3ᵏ) (mod 13)

となります。ここで、3³ ≡ 1 (mod 13) であることに着目すると、

3ʰ ≡ 3³ᵏʰ ≡ (3³)ᵏʰ ≡ 1ᵏʰ ≡ 1 (mod 13)

となります。したがって、f(n) ≡ 4(3ᵏ) ≡ 4(1) ≡ 4 (mod 13) となります。したがって、f(n) を 13 で割った余りは 4 です。

整数問題 13 京都医大

補足2023/05/15 13:02 について

←補足(05/15 13:04)

f(n)=5^(3n)+5^(2n)+5^n+1

誤字訂正：

f(n) = g(5^n) ；ただし g(u) = u^3 + u^2 + u + 1.

3 / 3

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング

f(n) = g(5^n)　　；ただし g(u) = u^3 + u^2 + u + 1.