* 問1:$m = 20$ のとき、$\sum_{d|m} \phi(d) = m$ が成り立つことを確認する。 * 問2:$\phi(36)$ と $\phi(25)$ を計算する。 * 問3:以下の連立合同式を解く。 1. $x \equiv 2 \pmod{5}$ $x \equiv 3 \pmod{11}$ 2. $x \equiv 2 \pmod{6}$ $x \equiv 3 \pmod{9}$ * 問4:おはじきの個数を求める。3個ずつ分けると1個余り、5個ずつ分けると2個余り、11個ずつ分けると3個余る。総数は500個以下である。

数論オイラー関数合同式中国剰余定理
2025/7/14
以下に、画像に写っている数学の問題の解答を示します。

1. 問題の内容

* 問1:m=20m = 20 のとき、dmϕ(d)=m\sum_{d|m} \phi(d) = m が成り立つことを確認する。
* 問2:ϕ(36)\phi(36)ϕ(25)\phi(25) を計算する。
* 問3:以下の連立合同式を解く。

1. $x \equiv 2 \pmod{5}$

x3(mod11)x \equiv 3 \pmod{11}

2. $x \equiv 2 \pmod{6}$

x3(mod9)x \equiv 3 \pmod{9}
* 問4:おはじきの個数を求める。3個ずつ分けると1個余り、5個ずつ分けると2個余り、11個ずつ分けると3個余る。総数は500個以下である。

2. 解き方の手順

* 問1:m=20m = 20 の約数は 1, 2, 4, 5, 10, 20 である。それぞれの ϕ\phi を計算する。
* ϕ(1)=1\phi(1) = 1
* ϕ(2)=1\phi(2) = 1
* ϕ(4)=2\phi(4) = 2
* ϕ(5)=4\phi(5) = 4
* ϕ(10)=4\phi(10) = 4
* ϕ(20)=8\phi(20) = 8
d20ϕ(d)=1+1+2+4+4+8=20=m\sum_{d|20} \phi(d) = 1 + 1 + 2 + 4 + 4 + 8 = 20 = m となり、成り立つ。
* 問2:

1. $\phi(36) = \phi(2^2 \cdot 3^2) = 36(1 - \frac{1}{2})(1 - \frac{1}{3}) = 36 \cdot \frac{1}{2} \cdot \frac{2}{3} = 12$

2. $\phi(25) = \phi(5^2) = 25(1 - \frac{1}{5}) = 25 \cdot \frac{4}{5} = 20$

* 問3:

1. $x \equiv 2 \pmod{5}$ より $x = 5k + 2$ と書ける。

これを x3(mod11)x \equiv 3 \pmod{11} に代入すると 5k+23(mod11)5k + 2 \equiv 3 \pmod{11}
5k1(mod11)5k \equiv 1 \pmod{11}
5k1+22(mod11)5k \equiv 1 + 22 \pmod{11}
5k23(mod11)5k \equiv 23 \pmod{11}なので、k235(mod11)k \equiv \frac{23}{5} \pmod{11}は整数にならない。
代わりに5k1(mod11)5k \equiv 1 \pmod{11}99 をかけると
45k9(mod11)45k \equiv 9 \pmod{11}
k9(mod11)k \equiv 9 \pmod{11}。したがって、k=11l+9k = 11l + 9
x=5(11l+9)+2=55l+45+2=55l+47x = 5(11l + 9) + 2 = 55l + 45 + 2 = 55l + 47
よって、x47(mod55)x \equiv 47 \pmod{55}

2. $x \equiv 2 \pmod{6}$ より $x = 6k + 2$ と書ける。

これを x3(mod9)x \equiv 3 \pmod{9} に代入すると 6k+23(mod9)6k + 2 \equiv 3 \pmod{9}
6k1(mod9)6k \equiv 1 \pmod{9}
6k=1+9n6k = 1 + 9n
2k=1+9n3=13+3n2k = \frac{1 + 9n}{3} = \frac{1}{3} + 3nとなり、整数にならないため解なし。
* 問4:
おはじきの個数を xx とすると、
x1(mod3)x \equiv 1 \pmod{3}
x2(mod5)x \equiv 2 \pmod{5}
x3(mod11)x \equiv 3 \pmod{11}
x1(mod3)x \equiv 1 \pmod{3} より x=3k+1x = 3k + 1
これを x2(mod5)x \equiv 2 \pmod{5} に代入すると 3k+12(mod5)3k + 1 \equiv 2 \pmod{5}
3k1(mod5)3k \equiv 1 \pmod{5}3k6(mod5)3k \equiv 6 \pmod{5} より k2(mod5)k \equiv 2 \pmod{5}
したがって、k=5l+2k = 5l + 2
x=3(5l+2)+1=15l+6+1=15l+7x = 3(5l + 2) + 1 = 15l + 6 + 1 = 15l + 7
これを x3(mod11)x \equiv 3 \pmod{11} に代入すると 15l+73(mod11)15l + 7 \equiv 3 \pmod{11}
15l47(mod11)15l \equiv -4 \equiv 7 \pmod{11}
4l7(mod11)4l \equiv 7 \pmod{11}
12l21(mod11)12l \equiv 21 \pmod{11}
l10(mod11)l \equiv 10 \pmod{11}
したがって、l=11m+10l = 11m + 10
x=15(11m+10)+7=165m+150+7=165m+157x = 15(11m + 10) + 7 = 165m + 150 + 7 = 165m + 157
x157(mod165)x \equiv 157 \pmod{165}
x500x \leq 500 より、m=0,1,2m = 0, 1, 2
x=157,322,487x = 157, 322, 487

3. 最終的な答え

* 問1:成り立つ
* 問2:

1. $\phi(36) = 12$

2. $\phi(25) = 20$

* 問3:

1. $x \equiv 47 \pmod{55}$

2. 解なし

* 問4:おはじきの個数は157個、322個、または487個である。

「数論」の関連問題

自然数 $N$ を5進法で表すと3桁の数 $abc_{(5)}$ となり、7進法で表すと3桁の数 $cab_{(7)}$ となる。このとき、自然数 $N$ と、整数 $a, b, c$ を求める問題で...

進法整数方程式数の表現
2025/7/18

(1) 整数 $m$ に対して、$m^2$ を4で割った余りは0または1であることを示す。 (2) 自然数 $n, k$ が $25 \times 3^n = k^2 + 176$ を満たすとき、$n...

整数の性質合同式二次不定方程式
2025/7/18

問題は、整数 $x$ について、「$x$ が 6 の倍数ならば、$x$ は 3 の倍数である」という命題の真偽を判定するものです。

倍数整数の性質命題真偽判定
2025/7/18

$5^{100}$ を $7$ で割ったときの余りを求めます。

合同式剰余累乗
2025/7/18

20の倍数で、正の約数の個数が15個である自然数nをすべて求めよ。

約数倍数素因数分解整数の性質
2025/7/18

問題は以下の2つです。 (1) $5^{105}$ は何桁の整数であるか。また、その最高位の数字は何か。 (2) $(\frac{1}{5})^{105}$ は小数第何位に初めて0でない数が現れるか。...

対数桁数最高位の数字常用対数
2025/7/17

整数 $a, b$ があり、$a$ を7で割ると1余り、$b$ を7で割ると2余るとき、以下の数を7で割った余りを求めよ。 (1) $a+b$ (2) $ab$ (3) $a^2-b^2$

合同式剰余整数の性質
2025/7/17

問題1は、4つの1次不定方程式の全ての整数解を求める問題です。 問題2は、3で割ると2余り、5で割ると4余る2桁の正の整数のうち、最大のものを求める問題です。

一次不定方程式合同式整数解最大公約数
2025/7/17

(5) 5で割ると3余り、8で割ると1余る自然数の中で最も小さいものを求める。 (6) 14で割ると3余り、21で割ると12余るような整数が存在しないことを示す。

合同式剰余不定方程式
2025/7/17

(5) 5で割ると3余り、8で割ると1余る自然数のうち、最も小さいものを求める。 (6) 14で割ると3余り、21で割ると12余るような整数が存在しないことを示す。

合同式中国剰余定理剰余最大公約数
2025/7/17