投稿者: shotasasaki

投稿日:

フェルマーの小定理

\(p\)を素数とする．整数\(a\)が\(a \not\equiv 0 \pmod p\)をみたすならば，\[a^{p-1} \equiv 1 \pmod p\]が成り立つ．

証明

\[1a,~2a,~3a,~\cdots,(p-1)a\]を考える．これらを\(p\)で割った余りはすべて異なることを以下に示す．\(p\)で割って余りが等しくなるような\(2\)数が存在すると仮定し，それらを\(ia,ja~(1 \leq i,j \leq p-1,~i\neq j )\)とおけば\[ia\equiv ja \pmod p \Longleftrightarrow (i-j)a\equiv 0 \pmod p\]が得られるが，\(a \not\equiv 0 \pmod p\)により\(i-j \equiv 0 \pmod p\)でなくてはならない．しかし，\(1 \leq i,j \leq p-1\)であったから，\(i-j\)は\(p-1\)以下であり，矛盾する．

したがって\(1a,~2a,~3a,~\cdots,(p-1)a\)を\(p\)で割った余りはすべて異なる．また\(a\not \equiv 0 \pmod p\)よりこれらは\(p\)では割り切れない（\(p\)で割っても余りが\(0\)にはならない）から，\(1a,~2a,~3a,~\cdots,(p-1)a\)を\(p\)で割ると余りとして\(1,2,\cdots,p-1\)がそれぞれ\(1\)回ずつ現れることになる．これを\[1a\equiv n_{1}~,2a\equiv n_{2}~,~\cdots~,(p-1)a\equiv n_{p-1}\]と表すことにする（ただし\((n_{1},~n_{2},~\cdots~,n_{p-1})\)は\(1,2,~\cdots~,p-1\)の適当な順列）．辺々掛けることで
\begin{align*}
&1\cdot 2 \cdot \cdots \cdot (p-1) a^{p-1}\equiv n_{1}n_{2}\cdots n_{p-1} \pmod p \\
\Longleftrightarrow ~&(p-1)! a^{p-1}\equiv (p-1)! \pmod p
\end{align*}ここで，\(\gcd(p,(p-1)!)=1\)であるから（実際，\(p\)と\((p-1)!\)に共通な素因数が存在すると仮定すると，\(p\)が素数であることからその共通の素因数は\(p\)であるが，\(1,2,\cdots,p-1\)はいずれも\(p\)では割り切れず，矛盾する），両辺を\((p-1)!\)で割ることができて\[a^{p-1} \equiv 1 \pmod p\]が得られる．

証明終

投稿日:

「分からない」の大切さ

\(11^{10}\)を\(9\)で割った余りを求めよ．

合同式の問題でよく見る問題です。

解答

\begin{align*}
11^{10}&\equiv 2^{10}\\
&\equiv 2\cdot 2^9\\
&\equiv 2\cdot 8^3\\
&\equiv 2\cdot (-1)^3\\
&\equiv -2\\
&\equiv 7 \pmod 9
\end{align*}よって\[11^{10}\equiv 7 \pmod 9\]したがって求める余りは\(7\)

解答終

授業でこの解説をしたところ「\(\equiv\)を\(=\)の同じような使い方をしてよいのかどうかがいまいちしっくりこない」という感想が。そう言われてみれば確かにこの解説はちょっと乱暴過ぎます（理解に必要な準備が足らない）。以下，この解答の理解のために知識を追加します。

まず一つ目。\[a_1 \equiv a_2 \equiv a_3 \equiv \cdots \equiv a_n \pmod p\]を\[a_1 \equiv a_2 \pmod p,~a_2 \equiv a_3\pmod p,~\cdots~,a_{n-1} \equiv a_n \pmod p\]を意味するものと規約します。これはただの記法なので問題なし。

二つ目。\[a_1 \equiv a_2 \equiv a_3 \equiv \cdots \equiv a_n \pmod p~\text{ならば}~a_1 \equiv a_n \pmod p\]であることを確認します。これは結局，次の性質（推移律）があるのか？という問題に帰着します。

\[a\equiv b\pmod p \land b \equiv c \pmod p \Longrightarrow a\equiv c \pmod p\]

証明

仮定により\(a-b=pk,b-c=pk^{\prime}\Longleftrightarrow a=b+pk,~b=c+pk^{\prime}\)．このとき，
\begin{align*}
a-c&=b+pk-c\\
&=c+pk^{\prime}+pk-c\\
&=p(k^{\prime}+k)
\end{align*}よって\[a\equiv c\pmod p\]

証明終

以上により，上の解答の式は
\begin{align*}
&11^{10}\equiv 2^{11}\pmod 9\\
&2^{11}\equiv 2\cdot 2^9\pmod 9\\
&2\cdot2^9\equiv 2\cdot 8^3\pmod 9\\
&2\cdot 8^3\equiv 2\cdot (-1)^3\pmod 9\\
&2\cdot (-1)^3\equiv -2\pmod 9\\
&-2\equiv 7 \pmod 9
\end{align*}を意味し，上で示した性質（推移律）を繰り返し適用することにより\(11^{10}\equiv 7 \pmod 9\)という結論が得られることになります（つまりこの解答の略記が上の解答）。

「わからない」「しっくりこない」という素直な感覚は，理解を深めるひとつの起点であると改めて思ます。

 

投稿日:

合同式の種々の公式

\(a\equiv b\pmod p,~c\equiv d\pmod p\)のとき，\[a\pm c \equiv b \pm d\pmod p,~ac \equiv bd\pmod p,~a^n \equiv b^n\pmod p\]が成り立つことは教科書や問題集等でよく証明されているので，ここではあまり紹介されないもののよく使う次の式を証明してみます。前半は片方のみに法の整数倍を加えるという\(=\)の世界では決して許されなかった計算が許されるという性質，後半は逆に\(\equiv\)の世界では禁じ手であった「両辺を割る」という操作ががある仮定のもとに限り許されるという面白い性質です。

\(a \equiv b\pmod p\)のとき，\[a\equiv b+pk \pmod p~(k\in \mathbb{Z})\]

証明

仮定により\(a-b=pk\)であるから
\begin{align*}
a-(b+kp)&=pk+b-(b+kp)\\
&=pk+kp=p(k+1)
\end{align*}よって\[a\equiv b+pk \pmod p~(k\in \mathbb{Z})\]

証明終

\(\gcd(c,p)=1\)（\(c\)と\(p\)が互いに素）のとき，
\[ac \equiv bc \pmod p\Longrightarrow a \equiv b \pmod p\]

証明

仮定により\[ac-bc=pk \Longleftrightarrow (a-b)c=pk\]右辺が\(p\)の倍数であるから左辺も\(p\)の倍数．ここで，\(c\)が\(p\)の倍数（\(c=pk^{\prime}\)）であると仮定すると，\(c(=pk^{\prime})\)と\(p\)が互いに素であることに反する（合同式の定義により\(p\)は\(2\)以上のの整数であることに注意）．したがって\(a-b\)が\(p\)の倍数，すなわち\[a\equiv b \pmod p\]
証明終

投稿日:

不定方程式

次の不定方程式の整数解を求めよ．\[(1)~7x-17y=1 \qquad (2)~52x+539y=19 \]

教科書と同じ解法はつまらないので，合同式を用いて解いてみます。

解答

\((1)\)
\[7x-17y\equiv1\pmod{7}\]
左辺に\(7(-x)\)を加えて（ア）
\[-17y\equiv1\pmod{7}\]
左辺に\(14y\)を加えて
\[-3y\equiv1\pmod{7}\]
両辺を\(2\)倍して（イ）
\[-6y\equiv2\pmod{7}\]
左辺に\(7y\)を加えて
\[y\equiv2\pmod{7}\]
よって\[y=7k+2~(k\in\mathbb{Z})\]
もとの式にこれを代入して
\[x=17k+5~(k\in\mathbb{Z})\]

\((2)\)
\[52x+539y\equiv19\pmod{52}\]
左辺に\(52(-x)\)を加えて
\[539y\equiv19\pmod{52}\]
左辺に\(52(-10y)\)を加えて
\[19y\equiv19\pmod{52}\]
\(19\)と\(52\)は互いに素であるから，両辺を\(19\)で割ることができて（ウ）
\[y\equiv1\pmod{52}\]
よって\[y=52k+1~(k\in\mathbb{Z})\]
もとの式にこれを代入して
\[x=-539k-10~(k\in\mathbb{Z})\]

解答終

このように合同式を利用すればゴチャゴチャ計算しなくとも簡潔に記述できます。
ただし（ア）（イ）（ウ）の操作は証明が必要です。

投稿日:

★P106

…その場合，\((W_{\lambda},\leq _{\lambda}),(W_{\lambda^{\prime}},\leq _{\lambda^{\prime}})\)のいずれか一方は他方の切片，したがって部分順序集合であるから…

 

松坂先生の集合・位相入門，理解できない箇所はところどころあるけどここもその一つ。周回後のレベルアップした（であろう）自分に期待するんだけど読むたびにやっぱりなんか釈然としない。多分しょーもないことなんだろうけど…。色々考えた末，以下の理解に落ち着いた：

理解

たとえば\((W_{\lambda},\leq _{\lambda})\)が\((W_{\lambda^{\prime}},\leq _{\lambda^{\prime}})\)の切片であるとする．切片\[(W_{\lambda^{\prime}},\leq _{\lambda^{\prime}})\langle a \rangle(= \{x|x \in W_{\lambda^{\prime}},x \leq_{\lambda^{\prime}} a\})\]これ自体は（あくまで\(W^{\prime}\)の元から順序\(\leq_{\lambda^{\prime}}\)で\(a\)よりも小さい元を集めたものに過ぎないから）ただの\(W_{\lambda^{\prime}}\)の部分集合であり，順序は定義されていない．しかし，一般に，順序集合\(A\)の空でない任意の部分集合\(M\)は，順序が与えれれていなくても，「\(A\)における順序を\(M\)上に制限した」と考えることで\(A\)と同じ順序が与えれられる（※）．したがって，部分集合\((W_{\lambda^{\prime}},\leq _{\lambda^{\prime}})\langle a \rangle\)は順序集合\[((W_{\lambda^{\prime}},\leq _{\lambda^{\prime}})\langle a \rangle , \leq_{\lambda^{\prime}})\]となる．これが\((W_{\lambda},\leq _{\lambda})\)に等しいから\[\leq_{\lambda^{\prime}}=\leq _{\lambda}\]となる．

理解終

※は89,90ページの部分順序集合についての記述から判断したもののちょっと自信ない。
…まあ，さしあたりこの理解でいいや＾＾；

投稿日:

「存在することを示せ」と言われたら（その２）（★P105問題2 ）

順序集合\(A\)の元の列\((a_n)_{n\in\mathbb{N}}\)で，\(a_1<a_2<\cdots<a_n<\cdots\)となるものを\(A\)における昇鎖という．これと相対的に\(A\)における降鎖が定義される．\(A\)が全順序集合であるとき，\(A\)が整列集合であるための必要十分条件は，\(A\)において降鎖が存在しないことであることを示せ．

存在を追え！

証明

（\(\Rightarrow\)）
\(A\)が整列集合で，\(A\)において降鎖が存在すると仮定する．このとき，\(A\)の元の列\((a_n)_{n\in\mathbb{N}}\)で，\[a_1>a_2>\cdots>a_n>\cdots\]となるものが存在するが，\(\{a_n\}_{n\in\mathbb{N}}\)には最小元が存在せず，矛盾である．

（\(\Leftarrow\)）
\(A\)が整列集合でないならば\(A\)において降鎖が存在することを示す（対偶）．
仮定により，\(A\)は整列集合でないから

\begin{align*}
\neg (A\text{が整列集合})\Longleftrightarrow~&\neg (\text{空でない任意の部分集合が最小元をもつ})\\
\Longleftrightarrow~&\neg (M\neq \phi,M \subset A \Rightarrow M\text{は最小元をもつ})\\
\Longleftrightarrow~&\exists M[M\neq \phi,M \subset A, M\text{は最小元をもたない}\cdots (\ast)]
\end{align*}

\begin{align*}
\neg (M\text{が最小元をもつ})~\Longleftrightarrow~&\neg(\exists a\in M \forall x \in M [a\leq x])\\
\Longleftrightarrow~&\forall a\in M \exists x \in M [x < a]\cdots(\ast\ast)\\
\end{align*}

したがって\((\ast)\)を満たす\(M\)が存在する．この\(M\)の任意の元\(a\)に対して，\((\ast\ast)\)により，\( x <a\)となる\(x\in M\)が存在する．そこで，\(M\)の元を任意に\(1\)つとり（これを\(a_1\)とおく），それに応じて定まる（\(x <a_1\)を満たす）\(x\in M\)を\(a_2\)とおくと\[a_2 < a_1\]となる．さらにこの\(a_2\in M\)に対して，再び\((\ast\ast)\)により，上と同様に\(x < a_2\)となる\(x \in M\)が存在する．これを\(a_3\)とおけば，\[a_3 < a_2\]が成り立つ．これを繰り返して\(A\)の元の列\((a_n)_{n\in \mathbb{N}}\)を定めれば，これが示すべきものとなる．

証明終

\(\overline{a+b=c\text{日本語入力するとなんかはみ出すので，}}\)
なので上では\(\neg\)を使いました。

投稿日:

2次方程式の共通解問題（その2・つづき）

\[(P\Rightarrow Q \lor R) \land \overline{Q\Rightarrow P} \land (R \Rightarrow P)\Rightarrow~(P \Leftrightarrow R)\]

証明

\(P\Rightarrow Q \lor R,\overline{Q\Rightarrow P},R \Rightarrow P\)となる行，すなわち\(P\rightarrow Q \lor R,\overline{Q\rightarrow P},R \rightarrow P\)が真となる行（上から6行目）に着目すると，\((P\rightarrow Q \lor R) \land \overline{Q\rightarrow P} \land (R \rightarrow P)\)と\(P \leftrightarrow R\)の真理値（青〇）が一致している．したがって\[(P\Rightarrow Q \lor R) \land \overline{Q\Rightarrow P} \land (R \Rightarrow P)\Longrightarrow~(P \Leftrightarrow R)\]を得る．

証明終

（関連：2次方程式の共通解問題（その2））

投稿日:

2次方程式の共通解問題（その2）

\(2\)つの\(2\)次方程式\(x^2-3x+m-1=0,x^2+(m-2)x-2=0\)が共通な実数解をただ\(\)1つもつとき，定数\(m\)の値とその共通解を求めよ．

解答

\begin{align*}
&x^2-3x+m-1=0,x^2+(m-2)x-2=0\text{が共通な実数解をただ1つもつ}\\
\Longrightarrow~&x^2-3x+m-1=0,x^2+(m-2)x-2=0\text{が共通な実数解をもつ}\\
\Longleftrightarrow~&\exists x
\begin{cases}
x^2-3x+m-1=0\\
x^2+(m-2)x-2=0
\end{cases}\\
\Longleftrightarrow~&\exists x
\begin{cases}
x^2-3x+m-1=0\\
x^2+(m-2)x-2-(x^2-3x+m-1)=0
\end{cases}\\
\Longleftrightarrow~&\exists x
\begin{cases}
x^2-3x+m-1=0\\
(m+1)(x-1)=0\end{cases}\\
\Longleftrightarrow~&\exists x
\begin{cases}
x^2-3x+m-1=0\\
m=-1\lor x=1
\end{cases}\\
\Longleftrightarrow~&\exists x [x^2-3x+m-1=0 \land (m=-1 \lor x=1)]\\
\Longleftrightarrow~&\exists x [(x^2-3x+m-1=0 \land m=-1) \lor (x^2-3x+m-1=0 \land x=1)]\\
\Longleftrightarrow~&\exists x (x^2-3x-2=0 \land m=-1) \lor \exists x(1^2-3\cdot 1+m-1=0 \land x=1)]&\\
\Longleftrightarrow~&\exists x \left[x=\frac{3\pm \sqrt{17}}{2} \land m=-1\right] \lor \exists x[m=3 \land x=1]\\
\Longleftrightarrow~&\left(\exists x \left[x=\frac{3\pm \sqrt{17}}{2}\right] \land m=-1 \right) \lor (m=3 \land \exists x[x=1])\\
\Longleftrightarrow~&m=-1 \lor m=3
\end{align*}
（\(\exists x \left[x=\frac{3\pm \sqrt{17}}{2}\right]，\exists x[x=1]\)は恒真命題）二行目が同値変形でないことに注意すると，結局，
\begin{align*}
x^2-3x+m-1=0,x^2+(m-2)x-2=0\text{が共通な実数解をただ1つもつ}&\\
\Longrightarrow~m=-1 \lor m=3&
\end{align*}
つまり得られた条件は必要条件に過ぎないので，十分性を調べる必要があります。そこで，逆に\(m=-1\)のときと\(m=3\)のときそれぞれの場合において「与えられた\(2\)次方程式が共通な実数解をただ1つもつ」ことを調べることにします。

\(m=-1\)のとき，与えられた\(2\)つの方程式は\(x^2-3x-2=0\)と\(x^2-3x-2=0\)となり，どちらの解も\(x=\frac{3\pm\sqrt{17}}{2}\)であり「ただ\(1\)つの」共通解を持つとは当然いえません。他方，\(m=3\)のときは\(x^2-3x+2=0\)と\(x^2+x-2=0\)となり，これらを解くとそれぞれの解は\(x=-2\)と\(x=-1\)，そして\(x=-2\)と\(x=1\)となりこれなら「ただ\(1\)つの」共通解\(x=-2\)をもつと言えます。したがって答えは\[m=3\]（で，共通解は\(x=-2\)）となります。

解答終

結局これは，①必要条件を調べ，次に②その条件が十分条件となっているかどうかを調べる，という２つの段階に分けるというのが大まかなシナリオです（①は同値性を気にすることなくとりあえず右向きの矢印だけ気にすればいいから気楽）。このような方針は問題を解く際にしばしば見られるものです。実際，教科書の軌跡の解説などではお馴染みですね。僕は受験生時代，この問題の解説にはどことない気持ち悪さを感じつつもただただ解法パターンとして覚えることしかできず，細かいことは見て見ぬふりをしていました。今思えばその「気持ち悪さ」は結局論理を理解していなかったのが原因だと思います。とはいえ，学校で扱わないのだからこの手の話が分からんのはアタリマエ。ってかそもそも扱ってないことを問題にする時点でおかしくないか…？

先日，授業でこの\(2\)次方程式の共通解問題を扱い，例によって上のような解説を（もちろん論理式でなく日本語で）していてふと思いました。上の議論はつまり「\(P\Longrightarrow Q \lor R\)が言えました，そして\(Q\rightarrow P\)が偽（\(\overline{Q\rightarrow P}\)が真）で，\(R \rightarrow P\)が真であることが分かりました，だから\(P \Longleftrightarrow R\)と言えるよね」というもの，つまり\[(P\Rightarrow Q \lor R) \land \overline{Q\Rightarrow P} \land (R \Rightarrow P)\Longrightarrow~(P \Leftrightarrow R)\]ですが（※），そもそもこの命題は正しいのでしょうか…？僕自身この変形を普段から無意識に行っていましたが…よくよく考えれば疑問です。このことを調べてみます。（つづく）

（関連：2次方程式の共通解問題（その1））

※(21/9/16) \(\Leftrightarrow\)を\(\Rightarrow\)に訂正しました。R君ご指摘ありがとうございます。

投稿日:

倍数の判定法

\(N\)を自然数とする．

\(N\)の下\(2\)桁が\(4\)の倍数\(~\Longleftrightarrow~\)\(N\)が\(4\)の倍数

証明

\(N\)を\(i\)桁目が\(a_{i-1}~(i=1,\cdots,n,a_{i-1}\in\mathbb{N})\)であるような自然数とする．
\begin{align*}
N&=a_0+a_1\times 10^{1}+a_2\times 10^{2}+\cdots+a_{n-1}\times 10^{n-1}\\
&=a_0+a_1\times 10^{1}+10^2(a_2+ a_3 \times 10 + \cdots + a_{n-1}\times 10^{n-3})\\
&=a_0+a_1\times 10^{1}+4 \times 25(a_2+ a_3 \times 10 + \cdots + a_{n-1}\times 10^{n-3})\tag{\(\ast\)}
\end{align*}

\(\Rightarrow\)について：
\(N\)の下\(2\)桁が\(4\)の倍数であるとする．\((\ast)\)により，
\[N=a_0+a_1\times 10^{1}+4 \times 25(a_2+ a_3 \times 10 + \cdots + a_{n-1}\times 10^{n-3})\]仮定により，\(N\)の下\(2\)桁が\(4\)の倍数，すなわち\(a_0+a_1\times 10^{1}\)が\(4\)の倍数であるから\(N\)は\(4\)の倍数である．

\(\Leftarrow\)について：
\(N\)が\(4\)の倍数であるとする．\((\ast)\)により，
\begin{align*}
&N=a_0+a_1\times 10^{1}+4 \times 25(a_2+ a_3 \times 10 + \cdots + a_{n-1}\times 10^{n-3})\\
\Longleftrightarrow~&a_0+a_1\times 10^{1} = N – 4 \times 25(a_2+ a_3 \times 10 + \cdots + a_{n-1}\times 10^{n-3})
\end{align*}仮定により，\(N\)は\(4\)の倍数であるから\(a_0+a_1\times 10^{1}\)すなわち\(N\)の下\(2\)桁は\(4\)の倍数である．

証明終

教科書の記述だと「\(4\)の倍数…下\(2\)桁が\(4\)の倍数である」というような記述をしており，必要条件なのか十分条件なのか曖昧なのでここにまとめておきます。他の倍数の判定もまったく同様の方針で証明できます。ちなみに合同式を使うともっと簡潔に記述できます。

投稿日:

かつとまたは，どっち？

不等式\[4x^2+5x-12\leq 3|x|\]を解け．

解答１

\((\mathrm{i})~\)\(x \geq 0\)のとき\(|x|=x\)であるから，
\begin{align*}
&4x^2+5x-12\leq 3x\\
&4x^2+2x-12\leq 0\\
&2x^2+x-6\leq 0\\
&(2x-3)(x+2)\leq 0\\
&-2\leq x \leq \frac{3}{2}\\
\end{align*}\(x \geq 0\)との共通部分を考え，\(0 \leq x \leq \frac{3}{2}\tag{1}\)

\((\mathrm{ii})~\)\(x < 0\)のとき\(|x|=-x\)であるから，
\begin{align*}
&4x^2+5x-12\leq -3x\\
&4x^2+8x-12\leq 0\\
&x^2+2x-3\leq 0\\
&(x+3)(x-1)\leq 0\\
&-3\leq x \leq 1\\
\end{align*}\(x < 0\)との共通部分を考え，\(-3 \leq x < 0\tag{2}\)

\((1),(2)\)との和集合を考え，\(-3 \leq x \leq \frac{3}{2}\)

解答終

よく見るいたって普通の解答ですが，生徒に「なぜ\((\mathrm{i}),(\mathrm{ii})\)では『かつ』なのに最後は『または』なんですか？『かつ』じゃだめなんですか？」と問われたらなんと答えらたいいのだろう？教科書にはもちろんそれらしい記述は一切はないから例によって頼りにならない。説明がないのだから，結局「そういうものだから覚えろ」と言うかそもそも（生徒の感覚に任せ）触れないかのどちらかになると思う。

解答２

\begin{align*}
&4x^2+5x-12\leq 3|x|\\
\Longleftrightarrow~&4x^2+5x-12\leq 3|x| \land ( x \geq 0 \lor x < 0)\\ \Longleftrightarrow~&(4x^2+5x-12\leq 3|x| \land x \geq 0) \lor (4x^2+5x-12\leq 3|x| \land x < 0)\\ \Longleftrightarrow~&(4x^2+5x-12\leq 3x \land x \geq 0) \lor (4x^2+5x-12\leq -3x \land x < 0)\\ \Longleftrightarrow~&(2x^2+x-6 \leq 0 \land x \geq 0) \lor (x^2+2x-3\leq 0 \land x < 0)\\ \Longleftrightarrow~&( -2\leq x \leq \frac{3}{2} \land x \geq 0) \lor (-3 \leq x \leq 1 \land x < 0)\\ \Longleftrightarrow~& 0 \leq x \leq \frac{3}{2}\lor -3 \leq x < 0\\ \Longleftrightarrow~&-3 \leq x \leq \frac{3}{2} \end{align*} 解答終

結局，やっていることが，恒真命題の追加と分配法則と分かり，これなら先のような疑問を挟む余地がありません。

\(*\)\(*\)\(*\)

教科書ってこの種のその先はいう必要ないですよね的な部分があるからいまいち信用できないし，またそれを妄信する人も理解できない。教科書の解答こそが理想の解答だとかほんと勘弁。

© 2024 佐々木数学塾, All rights reserved.