合同式の証明では、通常の等号とは異なる「同じ余りを持つ」という考え方を使います。そのため、不等式による大小関係だけを示して合同式を導こうとすると、思わぬ間違いが起こります。
この記事では、f(p)≡g(p) (mod p) を示すときに必要な条件、不等式による証明方法がなぜ成立しないのか、そして合同式を正しく扱うための基本的な考え方を解説します。
合同式 f(p)≡g(p) (mod p) が意味すること
合同式の定義は、整数a,bについてa≡b (mod n)であるとは、a-bがnの倍数であることです。
つまり、f(p)≡g(p) (mod p)を示したい場合は、次の条件を証明する必要があります。
f(p)-g(p)=mpとなる整数mが存在すること。
言い換えると、f(p)とg(p)をpで割ったときの余りが同じであることを示せばよく、大小関係は合同式の本質ではありません。
質問の不等式による証明方法で問題になる点
考え方では、
f(p)≧g(p)-kp
かつ
g(p)+lp≧f(p)
を満たす整数k,lが存在すると仮定し、
g(p)+lp≧f(p)≧g(p)-kp
だから合同式が成立すると考えています。
しかし、この条件だけではf(p)-g(p)がpの倍数であるとは限りません。
不等式は「どの範囲に入っているか」を表しているだけであり、「必ずpの倍数だけ離れている」ということを保証していないためです。
具体例で見る不等式条件の不足
例えば、p=5、f(p)=7、g(p)=3として考えます。
この場合、差はf(p)-g(p)=4です。4は5の倍数ではないため、
7≢3 (mod 5)
となります。
しかし、不等式条件は満たすことができます。
例えばk=1なら、
7≧3-5
となり成立します。またl=1なら、
3+5≧7
となり成立します。
つまり、不等式を満たしていても合同式は成立しない例が存在します。
合同式を示すために必要なのは整数倍の関係
合同式を証明する場合には、大小関係ではなく差に注目します。
具体的には、
f(p)-g(p)=kp
となる整数kを見つけることが最も基本的な方法です。
例えば、
f(p)=p²+3p+2
g(p)=2
の場合、
f(p)-g(p)=p²+3p=p(p+3)
となります。
p+3は整数なので、差はpの整数倍です。したがって、
p²+3p+2≡2 (mod p)
が示せます。
合同式で不等式が使える場合はあるのか
合同式そのものを証明する場面では不等式は基本的な道具ではありません。しかし、補助的に使われることはあります。
例えば、ある数が特定の範囲に入ることを示して、その範囲内に同じ余りを持つ数が一つしかないことを利用する場合があります。
ただし、その場合でも最後には「差が法の倍数である」という合同式の定義につなげる必要があります。
合同式の証明で覚えておきたいポイント
合同式は普通の等号とは違い、「完全に同じ値」を意味しません。mod nの世界では、nの倍数だけ離れている数を同じものとして扱います。
そのため、証明では以下の考え方を意識すると分かりやすくなります。
- 大小関係ではなく差を見る
- 差が法の倍数になることを示す
- 整数倍を表す文字は必ず整数であることを確認する
不等式による範囲指定は便利ですが、それだけでは合同関係を証明する条件として不足しています。
まとめ
f(p)≡g(p) (mod p)を示すには、f(p)とg(p)の差がpの整数倍になることを証明する必要があります。
質問のような不等式による方法では、f(p)とg(p)の距離がpの倍数であることを保証できないため、合同式の証明にはなりません。
合同式を扱うときは「大小」ではなく「差が法の倍数か」という視点で考えることが重要です。この考え方を身につけると、整数論や数学オリンピックなどで登場する合同式の問題にも対応しやすくなります。
コメント