modをみる
まず合同式の記法は使えるようになってください. 大前提です.
不定方程式をみたら, 慣れないうちはとりあえず $\bmod 2,3,4,5,7,8,9$ を一通り見てみましょう (なお $\bmod 6$ を弾いたのは, $\bmod 2$ と $\bmod 3$ をそれぞれ調べることと同値であるからで, 分けて考えたほうが見通しがいいと思います). $\bmod 2$ はすなわち偶奇ということで, 軽視されがちですが重要です. 例えば素数は $2$ または奇数であるという性質もありますからね.
$\bmod 3$ や $\bmod 4$ も特に多いです. これらの $\bmod$ で平方数が $0$ または $1$ に合同であることは非常に重要な性質です. したがって, 平方数が登場したら, まずこれらの $\bmod$ を考えることは有用です. 例えば以下の問題を考えてみましょう.
非負整数の組 $(a, b, c)$ であって $4^a-3^b+c^2=579$ をみたすものをすべて求めよ.
$b \geq 1$ を仮定すると $c^2 =579 -4^a +3^b \equiv 0-1+0 \equiv 2 \pmod 3$であるが, これを満たすような 整数 $c$ は存在しない. よって $b=0$ が必要であり, このとき与式は $4^a +c^2 =580$ と同値である. $4^a \leq 4^a +c^2 =580 < 4^5$ より $a=0, 1, 2, 3, 4$ のいずれかであり, $c^2= 580-4^a$ が平方数となるのは $a=1, 4$ のときである. $a=1$ のとき $c=24$, $a=4$のとき $c=18$ であるから, 求める組は $(a,b,c) =(1, 0, 24), (4, 0, 18)$ のみである.
$\bmod 3$ をみるのが正解です. でもほかの $ \bmod $ を調べたあなたも立派です. どの $\bmod$ が刺さるかなんて やってみないと分かりません. さて, $\bmod 3$ を調べると, $ 4^a \equiv 1, 3^b \equiv 0,1, c^2 \equiv 0,1 \pmod 3$ が成り立ちますが, $4^a -3^b+c^2 =579 \equiv 0 \pmod 3$ を満たすには $3^b \equiv 1, c^2 \equiv 0 \pmod 3$ の組み合わせが必要です. よって $ b=0$ が成り立ちます. 問題は $4^a +c^2 =580 $ を解くことに帰着され, ここから解を求めていきたいのですが, $a$ や $c$ が大きすぎると式の値が $580$を超えてしまって不適です. よって, 既に有限通りだけ調べればいい段階になっていて, 具体的には $ 580 < {25}^2 < 4^5$ より $a \leq 4$ や $ c \leq 24$ が必要だと分かります. $a=0, 1, 2, 3, 4$ の場合を調べることで解が求まります. $c$ を変えて調べてももちろん解けますが計算が増えます.
具体的な整数を法とした剰余も使いますが, 文字定数を法とすることもあります. たとえば問題文に $n$ という整数がでてきたときに, $\bmod n, \bmod{n-1}, \bmod{n+1}$ などの考察が効くことがあります.
$(1)$ $n^2+n \mid (n^n-1)^n+4n-1$ をみたす正の整数 $n$ をすべて求めよ.
$(2)$ $n^2+n \mid (n^n-1)^n+3n-1$ をみたす正の整数 $n$ をすべて求めよ.
$(1)$ $n^2 +n$ は偶数であるから, \[ (n^n-1)^n +4n-1 \equiv (n-1)^n -1 \equiv n-1-1 \equiv 0 \pmod 2 \] が成り立ち, $n$は偶数である. $n^2+n$ は $n+1$ の倍数であるから, \[(n^n-1) ^n +4n-1 \equiv ((-1)^n -1)^n +4 \cdot(-1)-1 \equiv (1-1)^n -5 \equiv -5 \pmod {n+1} \] が成り立ち, $n+1$ は $5$ の約数である. よって $n=4$ が必要であり, これが条件をみたすことは確認できる.
$(2)$ $n$ が奇数のとき, $n^2 +n$ は $n$ の倍数であるから, \[ (n^n-1)^n +4n-1 \equiv (-1)^n -1 \equiv -2 \pmod n\] が成り立ち, $n$ は $2$ の約数である. よって $n=1$ が必要であり, これが条件をみたすことは確認できる.
$n$ が偶数であるとき, $n^2+n$ は $n+1$ の倍数であるから, \[(n^n-1) ^n +3n-1 \equiv ((-1)^n -1)^n +3 \cdot(-1)-1 \equiv (1-1)^n -4 \equiv -4 \pmod {n+1} \] が成り立ち, $n+1$ は $4$の約数である. しかし, $n+1$ は $3$ 以上の奇数であるからこれは矛盾である. 以上より, 解は $n=1$ である.
$(1)$ では $ \bmod 2$ が使えます. $\bmod 2$ においては $n^k \equiv n$ が無条件に使え, 場合分けなしに 計算できるのが強力です. しかし, $(2)$ で $ \bmod 2$ を調べても $0 \equiv 0$ という虚無しか得られません. それに対して $ \bmod n$ は $(1)$ を解くのにも使えますが, $\bmod 2$ より少しだけステップが増えます. このように式の細かい値が方針に本質的に関わることが不定方程式ではよくあります.
ここまでが一番基本的です. 有名定理を使うとできることが増えたりします.
この定理は累乗が入った式における $\bmod$ の考察に役立ちます.
もちろん $\bmod$ を見て何もわからないときもあります. $\bmod$ にこだわって沼にはまらないようにしましょう. どの方針にも言える話ですが.
不等式評価
整数には次のすごい性質があります.
整数の離散性などと表現されるもので, 要するに整数は「とびとび」に存在しているということです. 有理数や実数では使えない性質です. 整数の離散性は次のような形でも現れます.
- $a \neq 0$ かつ $a \mid b$ のとき, $b=0$ または $|a| \leqq |b|$.
- $n \geq 0$ として $n^2 \lt x\lt (n+1)^2$ をみたす平方数 $x$ は存在しない.
- $a\lt b$ がともに平方数ならば $b-a \geqq 2\sqrt{a}+1$.
$1$ 番目の性質は「$X$ が $Y$ の倍数である」という形式の条件があるときに頭に入れておきたい性質です. $2, 3$ 番目の性質は平方数が絡む問題で意識しておきたいです. $3$ 番目は少し非自明なので証明してみましょう.
素因数をとる
これができるとかっこいい. 工事中.
互いに素
$2$ つの $0$ でない整数 $(a, b)$ の最大公約数が $1$ のとき, すなわち $a$ と $b$ に共通の素因数が存在しないとき, $a$ と $b$ は互いに素であるといいます. 以下 $(a, b)$ を互いに素な整数, $m, n$ を整数とします. このとき, 以下のような性質が成り立ちます.
- $m$ と $m+1$ は互いに素.
- $a$ と $ma+b$ は互いに素. 特に $a$ と $a+b$ は互いに素.
- $b \mid am \iff b \mid m$.
- $a \mid m$ かつ $b \mid m $ $\iff$ $ab \mid m$
- $m \equiv n \pmod a$ かつ $m \equiv n \pmod b$ $\iff$ $m \equiv n \pmod {ab}$
- $ka \equiv 1 \pmod b$ をみたす整数 $k$ が存在する.
- $ka+lb=1$ をみたす整数 $k,l$ が存在する.
上二つは互除法を適用しているだけですが, 互いに素な $2$ 整数を見つけるのに使えます. $3$ 番目は割られる数を小さくして不等式評価につなげるのがよくある使い道です. $6$ 番目は $\bmod b$ で「逆元」がとれるというやつです. いつか使います.
演習問題
$p, q$ を相異なる素数として $p^{q}+q^{p} \equiv p+q \pmod {pq}$ を示せ.
Fermatの小定理より $p^{q-1} \equiv 1 \pmod q$ だから $p^q+q^p \equiv 1\cdot p+0 \equiv p+q \pmod q$ が成り立つ. 同様に $p^q+q^p \equiv p+q \pmod p$ も成り立つから, これらより $p^q+q^p \equiv p+q \pmod {pq} $ が成り立つ.
$n^3+3n-2 \mid 3n^2+n+4$ をみたす正の整数 $n$ をすべて求めよ.
$n^3+3n-2, 3n^2+n+4 >0$ より$ n^3+3n-2 \leq 3n^2+n+4$ が必要である. よって $ (n-3)(n^2+2) \leq 0$ が成り立ち, $n \leq 3$ が必要である. $n =1, 2, 3$ のうち条件をみたすものは $n=1, 3$のみである.
すべての正の整数 $m$ について $n+m \mid n^3+2nm$ となるような正の整数 $n$ をすべて求めよ.
$ n^3+2nm \equiv n^3+2n(-n) \equiv n^3-2n^2 \pmod {n+m}$ である. $m >|n^3-2n^2|$ のとき, $ n+m > |n^3-2n^2| $ であり, $ n+m \mid n^3-2n^2$ とあわせて $n^3-2n^2=0$ が必要である. よって $n=2$ がしたがい, このときすべての正の整数 $m$ について $n^3-2n^2=0$ は $n+m$ の倍数であり, 条件はみたされる.
$n^2+3n+8$ が平方数となるような正の整数 $n$ をすべて求めよ.
$(n+1)^2 =n^2+2n+1 < n^2+3n+8 < n^2+6n+9 =(n+3)^2$ より 条件は $n^2 +3n+8 =(n+2)^2$ と必要十分であり, 解は $n=4$ である.
$3^n-2 \mid 2 \cdot 4^n +3 \cdot 6^n $ をみたす正の整数 $n$ をすべて求めよ.
\[ 2 \cdot 4^n +3 \cdot 6^n \equiv 2 \cdot 4^n +3 \cdot 2^n \cdot 3^n \equiv 2 \cdot 4^n +3 \cdot 2^n \cdot 2 \equiv 2^{n+1}(2^{n} +3)\pmod {3^n-2} \] であることと, 奇数 $3^n-2$ は$2^{n+1}$ と互いに素であることより $3^n-2 \mid 2^n+3$ が成り立つ. よって, $3^n-2, 2^n+3>0$ とあわせて $3^n -2 \leq 2^n +3$, すなわち $3^n-2^n \leq 3^2-2^2$ を得る. $3^n-2^n$ は 自然数 $n$ について狭義単調増加だから $n \leq 2$ が必要であり, $n=1,2$ が条件をみたすことは確認できる.