回りながら進む

数学/語学/プログラミングなどに興味があります

有理数のmodを駆使して数オリの有名整数問題を解く

数学 整数論 数オリ

こんばんは、simulo_yuiです。

simulo_yui (@simulo_yui) | Twitter

今回は、有理数のmodに関する記事です。合同式の基本的な知識を前提にします。 合同式をご存じでない方は下の記事をご覧ください。

 

問題

数列a_nをa_n=2^n+3^n+6^n-1で定義する。このとき、a_nの全ての項と互いに素となるような自然数を全て求めよ。(IMO 2005 problem 4)

一般的な解答

pを2と3以外の素数とする。以下、法は明記されない限りpとする。

ここで、2^{p-2} + 3^{p-2} + 6^{p-2}\equiv 1を示す。

(i)p \equiv 1 \mod 6のとき

Fermatの小定理より、2^{p-1}\equiv 3^{p-1}\equiv 6^{p-1}\equiv 1 である。2*2^{p-2}\equiv 1を解き、2^{p-2}\equiv \frac{p+1}{2}である。
同様に、
3^{p-2}\equiv \frac{2p+1}{3}
6^{p-2}\equiv \frac{5p+1}{6}
であり、

2^{p-2} + 3^{p-2} + 6^{p-2}\equiv \frac{p+1}{2} + \frac{2p+1}{3} + \frac{5p+1}{6} \equiv 2p + 1 \equiv 1
が確かに成立する。

(ii)p \equiv 5 \mod 6のとき

(i)と同様に、2^{p-2} + 3^{p-2} + 6^{p-2}\equiv \frac{p+1}{2} + \frac{p+1}{3} + \frac{p+1}{6} \equiv p + 1 \equiv 1

pは2,3を除く素数であるので、(i),(ii)の場合で尽くされている。よって、a_{p-2}\equiv0が2,3を除くすべての素数pで成り立ち、a_1=10\equiv 0 \mod 2, a_2=48 \equiv 0 \mod 3より、全ての素数について、それと互いに素でない項が存在する。つまり、2以上の全ての整数についても同様にそれと互いに素でない項が存在する。
また、1については、全ての整数と互いに素なので、要件を満たす。よって、求める自然数は、1のみである。

解説

まず、多くの素数についてそれと互いに素でないa_nの項が存在するならば、それらを素因数に持つ全ての整数もその項と互いに素ではない上、素数は扱いやすい様々ないい性質を持つので、素数のみについて考えようと思うのは自然でしょう。つまり、素数pと互いに素でない項の存在を具体的な構成をするなりして示せばいいのです。すると、整数のn乗と素数pに関する問題に変わるので、似た形である、Fermatの小定理を使いたくなるのは自然でしょう。でもなぜ、p-1乗でなく、p-2乗を考えるのでしょうか。

ある人は、様々な素数pで試していった結果p-2乗でうまくいくことに気づくのだ、というのかもしれません。実際、試験でこの問題が出てきたのならば、それが一番現実的でしょう。しかし、何か理由を考えたくなるのが、数学が好きな人の定めではないでしょうか。考えていきましょう。

Fermatの小定理について

ご存じの方はこの項を読み飛ばしていただいて結構です。
Fermatの小定理とは以下のようなものです。

Fermatの小定理

pを素数、aをpと互いに素な数とすると、
a^{p-1}\equiv 1 \mod p - (1) が成立する。

 

簡単な証明をします。

一般に、nを自然数とするとき、a \equiv b \mod p \Rightarrow a^n \equiv b^n \mod pなので、1 \leq a \leq p-1の場合を考える。

1\leq k \leq p-1について、{}_p C_k=\frac{p!}{(p-k)!k!}\equiv 0 \mod p
(\because 分子はpの倍数、分母はpの倍数でない)
なので、a^p=((a-1)+1)^n=\sum_{k=0}^p {}_{p}C_{k} (a-1)^k\equiv (a-1)^p+1 \mod p であり、これを繰り返し用いて、a^p\equiv (a-1)^p+1\equiv (a-2)^p+1+1=\cdots \equiv a \mod pであり、aとpは互いに素なので、最左辺と最右辺をaで割ると(1)が得られる。証明終。

有理数のmodについて

合同式の概念は整数の世界で導入され、整数の合同式をご存じの方は多いと思います。実は、合同式は有理数の世界にも拡張できるのです。具体的には、

nを整数として、有理数rが、r=\frac{a}{b}とa,b \in \mathbb{Z}, \gcd (a,b) = 1, \gcd (b,n)=1を満たすa,bを用いて表されるとき、bc\equiv a \mod nをみたすc \in \mathbb{Z}を以て、r \equiv c \mod nと定義されます。

つまり、既約分数の形で表したとき、分母がnと互いに素になる有理数について、合同式が定義されました。このようなcが合同な数を除いて一意に存在することは簡単に示せます。

このように定義された有理数のmodにおいても、整数の世界で成り立つ合同室の性質、つまり、法をn、a,b,c,dを定義に出てきた条件を満たす有理数として、
a \equiv c \land b \equiv d \Rightarrow a+b \land c +d
a \equiv c \land b \equiv d \Rightarrow a-b \land c -d
a \equiv c \land b \equiv d \Rightarrow ab \land c d
mをnと互いに素な整数とするとき、a\equiv b \Rightarrow \frac{a}{m} \equiv \frac{b}{m}
a \equiv b \Rightarrow a^m \equiv b^m
f(x)を整数、または分母がnと互いに素な係数をもつ多項式とするとき、a \equiv b \Rightarrow f(a) \equiv f(b)
などといった性質がなりたちます。これは簡単に証明できます。

また、参考として、分母がnと互いに素でない有理数に拡張してしまうと次のような問題が生じることも書いておきます。 その問題というのは、上の定義で、bがnと互いに素でないとき、bc\equiv a \mod nとなるようなcが一般には存在しないことです。a=1,b=2,n=4などとすると、分かると思います。bとnが互いに素でないとき、\mod nの世界ではbは0の要素(=nの素因数)を含んでいるから、こんな不都合が生じる、という感覚的な説明もできます。

問題への適用

先程の問題に有理数のmodを適用してみましょう。
フェルマーの小定理より、a^{p-1}\equiv 1 \mod pより、a^{p-2}\equiv \frac{1}{a} \mod pが成立します。 すると、a_{p-2}=2^{p-2}+3^{p-2}+6^{p-2}-1\equiv \frac{1}{2}+\frac{1}{3}+\frac{1}{6}-1=0 \mod pとなります。この式を見ると、なぜp-2乗を考えるのか、なんとなくわかった気になりませんか？つまり、a_nの式にn=-1を代入すると、a_{-1}=0になることに気づくので、\mod pの世界でも逆元(=かけて1になるもの。ここでは2に対する\frac{1}{2})である、p-2乗を考えよう、というモチベーションがあったのです。

こうやって書くと、何だか数オリの問題が可愛く見えますね。とても可愛い。綺麗でかわいいなんて最高ですね。

終わりに

誤りなどありましたら教えてください。
こうやって記事を書き終わってみると、この問題の作問者はきっと、小学生でも知っている\frac{1}{2}+\frac{1}{3}+\frac{1}{6}=1という等式をどれだけドラマチックなものに昇華できるかを考えていたんじゃないかな、と思います。最後に、改悪した問題を貼って記事を終わりにします。

冒頭の問題のa_nをa_n=2^n+4^n+7^n+14^n+28^n-1と定義して、a_nの全ての項と互いに素となるような自然数を全て求めよ。
Hint(なのか？):6も28も嬉しい性質が成り立っているので、この問題はうまくいきます。