合同式ごうどうしきcongruenceと余あまり-基本演習きほんえんしゅう

date2026-07-11document_iddoc_e17c70c5da1c9c78b9f6ca8adddc1b0adescription合同式の定義、演算保存、累乗周期、逆元の条件を用いて余りを追跡する基本演習である。prerequisites整数の割り算 / 最大公約数 / 累乗type問題演習content_typeexercisestatusactive

mathalgebranumber-theorycongruenceexercise

1対応講義たいおうこうぎ

data/lecture/math/algebra/congruences-and-remainders.lecture.n.md

2演習方針えんしゅうほうしん

大おおきい整数せいすうを直接計算ちょくせつけいさんせず、必要ひつような法ほうのもとで小ちいさい代表だいひょうへ置換ちかんする。ただし割わり算さんの前まえには逆元ぎゃくげんの存在そんざいを確認かくにんする。

3問題もんだい 1：定義ていぎによる判定はんてい

$137 \equiv - 3 [PARSE ERROR: Undefined("Command(\"pmod\")")] 10$ と $137 \equiv 2 [PARSE ERROR: Undefined("Command(\"pmod\")")] 5$ を定義ていぎから判定はんていせよ。

3.1解答例かいとうれい

$137 - (- 3) = 140$ は $10$ の倍数ばいすうなので前者ぜんしゃは成立せいりつする。 $137 - 2 = 135$ は $5$ の倍数ばいすうなので後者こうしゃも成立せいりつする。

3.2診断しんだん

負ふの代表だいひょうを避さけず、 $m ∣ (a - b)$ という定義ていぎへ戻もどれるかを確認かくにんする。

4問題もんだい 2：大おおきい累乗るいじょうの余あまり

$7^{100}$ を $5$ で割わった余あまりを求もとめよ。

4.1解答例かいとうれい

$7 \equiv 2 [PARSE ERROR: Undefined("Command(\"pmod\")")] 5$ であり、 $2^{4} \equiv 1 [PARSE ERROR: Undefined("Command(\"pmod\")")] 5$ である。 $100 = 4 \cdot 25$ だから

7^{100} \equiv (2^{4})^{25} \equiv 1 [PARSE ERROR: Undefined("Command(\"pmod\")")] 5.

したがって余あまりは $1$ である。

4.2診断しんだん

累乗るいじょうの余あまりに周期しゅうきを発見はっけんし、指数しすうを周期しゅうきで整理せいりする技能ぎのうを確認かくにんする。

5問題もんだい 3：多項式たこうしきへの代入だいにゅう

$n \equiv 3 [PARSE ERROR: Undefined("Command(\"pmod\")")] 7$ のとき、 $n^{3} + 2 n^{2} - 5$ を $7$ で割わった余あまりを求もとめよ。

5.1解答例かいとうれい

合同式ごうどうしきは加法かほうと乗法じょうほうで保存ほぞんされるので、

n^{3} + 2 n^{2} - 5 \equiv 27 + 18 - 5 = 40 \equiv 5 [PARSE ERROR: Undefined("Command(\"pmod\")")] 7.

余あまりは $5$ である。

5.2診断しんだん

整数係数多項式せいすうけいすうたこうしきなら代表だいひょうを代入だいにゅうしてよい理由りゆうを、演算保存えんざんほぞんから説明せつめいする。

6問題もんだい 4：漸化式ぜんかしきの余あまり

$a_{0} = 0$ 、 $a_{n + 1} = 3 a_{n} + 2$ とする。 $a_{n}$ の $5$ による余あまりを $n = 0$ から追おい、周期しゅうきを求もとめよ。

6.1解答例かいとうれい

余あまりは

0 \to 2 \to 3 \to 1 \to 0

と遷移せんいする。したがって周期しゅうきは $4$ であり、 $a_{n} \equiv 0, 2, 3, 1 [PARSE ERROR: Undefined("Command(\"pmod\")")] 5$ が $n \equiv 0, 1, 2, 3 [PARSE ERROR: Undefined("Command(\"pmod\")")] 4$ に対応たいおうする。

6.2診断しんだん

数列全体すうれつぜんたいではなく有限個ゆうげんこの剰余状態じょうよじょうたいだけを追跡ついせきできるかを確認かくにんする。

7問題もんだい 5：割わり算さんの可否かひ

$6 x \equiv 9 [PARSE ERROR: Undefined("Command(\"pmod\")")] 15$ を解かいけ。また、両辺りょうへんを単純たんじゅんに $3$ で割わる際さいに法ほうも変更へんこうする必要ひつようがある理由りゆうを説明せつめいせよ。

7.1解答例かいとうれい

$15 ∣ (6 x - 9) = 3 (2 x - 3)$ だから $5 ∣ (2 x - 3)$ 、すなわち

2 x \equiv 3 [PARSE ERROR: Undefined("Command(\"pmod\")")] 5.

$2^{- 1} \equiv 3 [PARSE ERROR: Undefined("Command(\"pmod\")")] 5$ より $x \equiv 9 \equiv 4 [PARSE ERROR: Undefined("Command(\"pmod\")")] 5$ である。元もとの法ほう $15$ では $x \equiv 4, 9, 14 [PARSE ERROR: Undefined("Command(\"pmod\")")] 15$ に相当そうとうする。

7.2診断しんだん

$3$ は法ほう $15$ のもとで逆元ぎゃくげんを持もたないため、法ほうを保たもったままの約分やくぶんはできない。解かいの個数こすうが変化へんかしない形かたちで条件じょうけんを書かき換かえる。

8誤答診断ごとうしんだん

問題もんだい	分類ぶんるい	典型誤答てんけいごとう	戻もどる内容ないよう
1	前提理解不足ぜんていりかいぶそく	負ふの代表だいひょうを合同ごうどうでないと判断はんだんする	$m ∣ (a - b)$ という定義ていぎ
2–4	計算けいさんミス	周期しゅうきの開始点かいしてんまたは指数しすうを 1 つずらす	剰余状態じょうよじょうたいの遷移せんい
5	適用条件てきようじょうけんミス	逆元ぎゃくげんを確認かくにんせず法ほうを保たもって 3 で割わる	逆元ぎゃくげんと gcd